ST es una mónada en la que se permiten un tipo limitado de efectos secundarios, a saber, las referencias mutables y las matrices mutables. Por lo tanto, le permite implementar funciones que son puras como se ven desde el mundo exterior, pero que usan la mutación internamente.
Esto es diferente de State, que solo falsifica la mutación al enhebrar el estado a través de su computación como entradas y salidas adicionales. La diferencia es importante cuando se implementan algunos algoritmos imperativos, porque a veces es necesario implementar la mutación de manera eficiente. Por ejemplo, usando una matriz regular en una mónada State, solo puede modificarla haciendo una copia, mientras que con ST puede tener una mutación verdadera en el lugar.
La razón por la que tenemos tanto ST y IO es que ST ofrece garantías más fuertes que IO, a saber:
ST no permite efectos secundarios arbitrarias, como por ejemplo el acceso al sistema de archivos.- Podemos garantizar que los efectos secundarios
STpermiten permitir que no se escape el alcance de runST, por lo que puede verse como puro del mundo exterior.
La razón por la que podemos garantizar que los efectos secundarios no pueden escapar está relacionada con la variable de tipo s. Como cualquier acción ST debe ser polimórfica en s, no puede escribir código que permita que cualquier referencia mutable ingrese o salga del alcance de un runST, porque el verificador de tipos se quejará de que no puede garantizar que s de su acción y la de la referencia o array son los mismos a menos que vengan del mismo alcance runST.
Como un ejemplo del uso de la mónada ST con matrices mutables, aquí es una implementación de la Criba de Eratóstenes:
import Control.Monad
import Control.Monad.ST
import Data.Array.ST
import Data.Array.Unboxed
primesUpto :: Int -> [Int]
primesUpto n = [p | (p, True) <- assocs $ sieve n]
sieve :: Int -> UArray Int Bool
sieve n = runSTUArray $ do
sieve <- newArray (2, n) True
forM_ [2..n] $ \p -> do
isPrime <- readArray sieve p
when isPrime $ do
forM_ [p*2, p*3 .. n] $ \k -> do
writeArray sieve k False
return sieve
runSTUArray es una forma especializada de runST que le permite construir una matriz mediante mutación en el interior, antes de congelarlo y devolverlo como una matriz inmutable. newArray, readArray y writeArray haga lo que usted esperaría.
Como puede ver, el tipo de firma de sieve indica que es una función pura, y lo es. Sin embargo, utiliza una gran mutación en el interior para implementarlo de manera eficiente.
Por lo general, los vectores son más fáciles de usar que los arrays, si quieres echarles un vistazo. – alternative