arrays - Documentación de Starray para novatos y preguntas relacionadas con State/ST

haskell higher-rank-types

Question

Tengo dificultades para entender STArray partir de la documentación y otros howtos / debates que he encontrado a través de Google. Tengo algunas preguntas más relacionadas a continuación.

De acuerdo con la documentación, STArray s son

Matrices mutables en caja y sin caja en la mónada ST.

Esto me dio la impresión de que STArray está destinado a ser utilizado como un estado que se transmite entre funciones (imagine que tiene un vector que debe actualizarse a menudo).

Aparentemente, esto se usa de manera diferente:

ST s (STArray s a e)

¿Cuál es el estado aquí? Si se usa internamente, ¿por qué no está oculto para el usuario?

Esto también significa que, si queremos utilizar un STArray s Int Int se transmite como estado, uno definiría

type StateArray a = Control.Monad.State (ST s (STArray s Int Int)) a

que parece bastante engorroso.

Finalmente,

• ¿Cuál es la diferencia entre ST y State ?
• ¿ STArray es la diferencia entre STArray e IOArray , si el ST y el IO están diseñados para un uso "interno"?

¡¡Gracias!!

Answer 1

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 del 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 de 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 como IO es que ST proporciona garantías más sólidas que IO , a saber:

1. ST no permite efectos secundarios arbitrarios como, por ejemplo, acceder al sistema de archivos.
2. Podemos garantizar que los efectos secundarios que ST permite no pueden escapar del 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 puedan 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 la s de su acción y la de la referencia o array son lo mismo a menos que provengan del mismo alcance de runST .

Como ejemplo del uso de la mónada ST con matrices mutables, aquí hay una implementación de Sieve of Erathostenes:

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 te permite construir una matriz usando una mutación en el interior, antes de congelarla y devolverla como una matriz inmutable. newArray , readArray y writeArray hacen lo que cabría esperar.}

Como puede ver, la firma tipo 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.