map runSTArray sobre una lista de STArrays?

Question

Tengo una función que crea recursivamente una lista aplanada de matrices de un árbol que tienen que ser mutables ya que sus elementos se actualizan con frecuencia durante su creación. Hasta ahora he llegado a una solución recursiva que tiene la firma:

doAll :: .. -> [ST s (STArray s (Int, Int) Int)] 

La razón por la que no devuelva el [UArray (Int,Int) Int] directamente es porque doAll se llama de forma recursiva, modifica los elementos de las matrices en la lista y añade nuevas matrices . No quiero congelar y descongelar las matrices innecesariamente.

Hasta ahora todo bien. Puedo inspeccionar la matriz -ésimo n (de tipo Array (Int, Int) Int) en ghci

runSTArray (matrices !! 0) 
runSTArray (matrices !! 1) 

y de hecho puedo obtener los resultados correctos para mi algoritmo. Sin embargo, no he encontrado una manera de asignar runSTUArray sobre la lista que se devuelve por doAll:

map (runSTArray) matrices 

Couldn't match expected type `forall s. ST s (STArray s i0 e0)' 
      with actual type `ST s0 (STArray s0 (Int, Int) Int)' 

El mismo problema ocurre si se intenta evaluar de forma recursiva sobre la lista o tratar de evaluar los elementos individuales envueltos en una función

¿Podría alguien explicar qué está pasando (no entendí realmente las implicaciones de la palabra clave forall) y cómo podría evaluar las matrices en la lista?

Answer 1

Ésta es una consecuencia desafortunada de la truco tipo que hace ST seguro. Primero, necesitas saber cómo funciona ST. La única manera de obtener desde la mónada ST hasta el código puro es con la función runST u otras funciones basadas en ella como runSTArray. Estos son todos del formulario forall s.. Esto significa que, para construir un Array desde una STArray, el compilador debe poder determinar que puede sustituir cualquier tipo que le guste por la variable de tipo s dentro de runST.

Considere ahora la función map :: (a -> b) -> [a] -> [b]. Esto muestra que cada elemento de la lista debe tener exactamente el mismo tipo (a) y, por lo tanto, también el mismo s. Pero esta restricción adicional viola el tipo de runSTArray, que declara que el compilador debe poder sustituir libremente otros valores por s.

Puede solucionar esto mediante la definición de una nueva función de congelar primero las matrices dentro de la mónada ST, a continuación, ejecutar la acción resultante ST:

runSTArrays :: Ix ix => (forall s. [ST s (STArray s ix a)]) -> [Array ix a] 
runSTArrays arrayList = runST $ (sequence arrayList >>= mapM freeze) 

Nota del forall requiere la extensión RankNTypes.

Answer 2

Acaba de rebotar contra las limitaciones del sistema de tipos.

The runSTArray tiene un mayor ranking. Debe pasarle una acción ST cuya variable de tipo de estado sea única. Sin embargo, en Haskell normalmente no es posible tener tales valores en las listas.

Todo es un esquema ingenioso para asegurarse de que los valores que produce en una acción ST no puedan escapar de allí. Lo que significa que parece que su diseño se ha roto de alguna manera.

Una sugerencia: no puede procesar los valores en otra acción ST, como

sequence [ ... your ST s (STArray s x) ...] >>= processing 
    where 
    processing :: [STArray s x] -> ST s (your results)