Haskell: mapa runST

Question

He una unión para un tipo [ST s (Int, [Int])] y estoy tratando de aplicar runST a cada elemento en el mapa de la siguiente manera:

name :: [ST s (Int, [Int])] --Of Course there is a real value here 
map runST name 

Esto me da un mensaje de error

Couldn't match expected type `forall s. ST s b0' 
    with actual type `ST s0 (Int, [Int])' 
Expected type: [forall s. ST s b0] 
    Actual type: [ST s0 (Int, [Int])] 
In the second argument of `map', namely `name' 
In the expression: map runST name 

Debe haber algo que estoy malentendiendo. Soy consciente de runST and function composition, pero no estoy seguro si esto aplica.

¡Gracias por el tiempo de todos!

Answer 1

Cada vez que ejecuta un transformador de estado con runST, opera en un estado local que está separado de todos los demás transformadores de estado. runST crea un nuevo tipo de estado y llama a su argumento con ese tipo. Así, por ejemplo, si se ejecuta

let x = runST (return()) 
    y = runST (return()) 
in (x, y) 

entonces la primera y la segunda return()return() tendrá diferentes tipos: ST s1() y ST s2(), para algunos tipos desconocidos s1 y s2 que son creados por runST.

Está intentando llamar al runST con un argumento que tiene estado tipo s. Ese no es el tipo de estado que crea runST, ni ningún otro tipo puede elegir. Para llamar al runST, debe pasar un argumento que puede tener cualquier tipo de estado. Aquí está un ejemplo:

r1 :: forall s. ST s() 
r1 = return() 

Debido r1 es polimórfico, su estado puede tener cualquier tipo, incluyendo cualquier tipo es seleccionado por runST. Puede asignar runST más de una lista de polimórficas r1 s (con -XImpredicativeTypes):

map runST ([r1, r1] :: [forall t. ST t()]) 

Sin embargo, no se puede asignar runST más de una lista de no-polimórficas r1 s.

map runST ([r1, r1] :: forall t. [ST t()]) -- Not polymorphic enough 

El tipo forall t. [ST t()] dice que todos los elementos de la lista tienen el tipo de estado t. Pero todos deben tener tipos de estado independientes porque se llama a runST en cada uno. Eso es lo que significa el mensaje de error.

Si está bien dar el mismo estado a todos los elementos de la lista, entonces puede llamar al runST una vez como se muestra a continuación. La firma de tipo explícita no es obligatoria.

runST (sequence ([r1, r1] :: forall t. [ST t()])) 

Answer 2

Su name no es lo suficientemente polimórfico. Su estado de

name :: [ST s (Int, [Int])] 

significa 'una lista de cómputos con estado volviendo (Int, [Int]), que tienen exactamente el mismo s'.Pero mira el tipo de runST:

runST :: (forall s. ST s a) -> a 

Este tipo significa 'una función que toma un cómputo con estado donde spuede ser cualquier cosa que pueda imaginar'. Este tipo de cálculos no es lo mismo. Y finalmente:

map runST :: [forall s. ST s a] -> [a] 

Verá, su lista debe contener más valores polimórficos de lo que lo hace ahora. s tipo podría ser diferente en cada elemento de la lista, puede no ser del mismo tipo que en name. Cambie la firma de tipo name, y todo debería estar bien. Puede requerir la activación de algunas extensiones, pero GHC debería poder decirle cuáles.

Answer 3

Voy a tratar de explicar el razonamiento para runST 's Tipo:

runST :: (forall s. ST s a) -> a 

Y por qué no es así simple:

alternativeRunST :: ST s a -> a 

Tenga en cuenta que este alternativeRunST le habían trabajado para tu programa

alternativeRunST También habría habían permitido a filtrarse las variables fuera de la mónada ST:

leakyVar :: STRef s Int 
leakyVar = alternativeRunST (newSTRef 0) 

evilFunction :: Int -> Int 
evilFunction x = 
    alternativeRunST $ do 
    val <- readSTRef leakyVar 
    writeSTRef leakyVar (val+1) 
    return (val + x) 

entonces usted podría ir en ghci y hacer:

>>> map evilFunction [7,7,7] 
[7,8,9] 

evilFunction no es referencialmente transparente!

Por cierto, a lo pruebe aquí es el marco "malo ST" necesario para ejecutar el código anterior:

{-# LANGUAGE GeneralizedNewtypeDeriving #-} 
import Control.Monad 
import Data.IORef 
import System.IO.Unsafe 
newtype ST s a = ST { unST :: IO a } deriving Monad 
newtype STRef s a = STRef { unSTRef :: IORef a } 
alternativeRunST :: ST s a -> a 
alternativeRunST = unsafePerformIO . unST 
newSTRef :: a -> ST s (STRef s a) 
newSTRef = ST . liftM STRef . newIORef 
readSTRef :: STRef s a -> ST s a 
readSTRef = ST . readIORef . unSTRef 
writeSTRef :: STRef s a -> a -> ST s() 
writeSTRef ref = ST . writeIORef (unSTRef ref) 

El verdadero runST no nos permiten construir tales funciones "mal". ¿Cómo lo hace? Es un poco complicado, ver más abajo:

Intentar ejecutar:

>>> runST (newSTRef "Hi") 
error: 
    Couldn't match type `a' with `STRef s [Char]' 
... 

>>> :t runST 
runST :: (forall s. ST s a) -> a 
>>> :t newSTRef "Hi" 
newSTRef "Hi" :: ST s (STRef s [Char]) 

newSTRef "Hi" no encaja (forall s. ST s a). Como puede ser visto también usando un ejemplo aún más simple, donde GHC nos da una bonita error:

dontEvenRunST :: (forall s. ST s a) -> Int 
dontEvenRunST = const 0 

>>> dontEvenRunST (newSTRef "Hi") 
<interactive>:14:1: 
    Couldn't match type `a0' with `STRef s [Char]' 
     because type variable `s' would escape its scope 

Tenga en cuenta que también podemos escribir

dontEvenRunST :: forall a. (forall s. ST s a) -> Int 

Y es equivalente a la omisión de la forall a. como hemos hecho antes

Tenga en cuenta que el alcance de a es mayor que el de s, pero en el caso de newSTRef "Hi" su valor debe depender de s. El sistema de tipo no permite esto.