Fugas de espacio, y escritores, y sumas (¡oh!)

Question

He estado jugando con el escritor Mónada recientemente, y me he encontrado con lo que parece ser una fuga de espacio. No puedo decir que aún entiendo completamente estas cosas , así que me gustaría saber qué está pasando aquí y cómo solucionarlo.

En primer lugar, aquí es cómo puedo desencadenar este error:

import Control.Monad.Writer 
import Data.Monoid 

foo :: Integer -> Writer (Sum Integer) Integer 
foo 0 = return 0 
foo x = tell (Sum x) >> foo (pred x) 

main = print $ runWriter $ foo 1000000 

me sale:

Stack space overflow: current size 8388608 bytes. 
Use `+RTS -Ksize -RTS' to increase it. 

Para entender esto mejor, he vuelto a implementar una funcionalidad similar sin Writer o Suma, y ​​si Mantengo las cosas bien y perezoso, obtengo el mismo error :

bar :: Integer -> (Integer, Integer) 
bar x = bar' 0 x 
    where bar' c 0 = (0, c) 
      bar' c x = bar' (c + x) (pred x) 

Pero puedo remediar esto mediante la adición seq a la ecuación:

bar' c x = c `seq` bar' (c + x) (pred x) 

He intentado seq ing varios trozos de mi función foo, pero eso no parece para ayudar. Además, traté de usar Control.Monad.Writer.Strict, pero tampoco hace la diferencia.

¿Tiene que ser estricto de alguna manera? O me estoy perdiendo algo completamente diferente?

Notas

• que pueda tener mi terminología mal aquí. De acuerdo con Space leak zoo, mi problema se clasificaría como un "desbordamiento de pila", y si es , ¿cómo convertiría foo a un estilo más iterativo? ¿Es mi manual recursion el problema?
• Después de leer Haskell Space Overflow, tuve la idea de compilar con -O2, solo para ver qué pasa. Esto puede ser un tema para otra pregunta, pero con optimizaciones, incluso mi seq 'd bar función no se ejecuta. Actualización: Este problema desaparece si agrego -fno-full-laziness.

Answer 1

El problema con la mónada escritor es que es >>= no es recursiva de cola:

instance (Monoid w, Monad m) => Monad (WriterT w m) where 
m >>= k = WriterT $ do 
    (a, w) <- runWriterT m 
    (b, w') <- runWriterT (k a) 
    return (b, w `mappend` w') 

Como se puede ver que tiene que evaluar tanto m y k a para evaluar mappend lo que significa que toda la pila de llamadas recursivas tiene ser forzado antes de que se pueda evaluar el primer mappend. Creo que, independientemente de la rigurosidad, la mónada Writer provocará el desbordamiento de la pila en su definición (¿o puede evitarse de alguna manera con la versión de?).

Si aún quiere usar mónadas, puede probar State, que es recursivo por la cola. Ya sea la versión estricta de la misma con estricta put:

import Control.Monad.State.Strict 

foo :: Integer -> State (Sum Integer) Integer 
foo 0 = return 0 
foo x = do 
    w <- get 
    put $! w `mappend` (Sum x) 
    foo (pred x) 

main = print $ (`execState` Sum 0) $ foo 1000000 

o la versión perezoso con el estilo de continuación paso (CPS):

import Control.Monad.Cont 
import Control.Monad.State.Lazy 

foo :: Integer -> ContT Integer (State (Sum Integer)) Integer 
foo 0 = return 0 
foo x = do 
    w <- get 
    put $! w `mappend` (Sum x) 
    foo (pred x) 

main = print $ ((`execState`Sum 0) . (`runContT`return)) $ foo 1000000 

analógico Práctico para tell:

stell :: (MonadState w m, Monoid w) => w -> m() 
stell a = get >>= \w -> put $! w `mappend` a 

Sospecho que si era posible usar ContT con Writer CPS nos ayudaría con Writer también, pero parece que no es p posible a define ContT for MonadWriter:

Answer 2

mirada a la fuente para la estricta mónada escritor: http://hackage.haskell.org/packages/archive/transformers/0.2.2.0/doc/html/src/Control-Monad-Trans-Writer-Strict.html#line-122

La diferencia de la escritura diferida es que en este último, las coincidencias de patrones son perezosos - pero en ninguno de los casos es la operación o el mappend "estado" del escritor hasta ahora forzado. Para resolver su problema, necesitaría un escritor "súper estricto".

Answer 3

Creo que su comprensión es correcta.

estoy interesado en cómo estas funciones:

bar :: Integer -> (Integer, Integer) 
bar x = bar' 0 x 
    where bar' c 0 = (0, c) 
      bar' c x = c `seq` bar' (c + x) (pred x) 
     -- bar' c x = let c' = c+x in c' `seq` bar' c' (pred x) 
     -- bar' !c !x = bar' (c+x) (pred x) 

produce un desbordamiento de pila cuando se compila con optimizaciones, aunque las funciones relacionadas:

bar2 :: Integer -> (Integer, Integer) 
bar2 x = bar' 0 x 
    where bar' c 0 = (0, c) 
      bar' !c !x = let c' = c+x in c' `seq` bar' c' (pred x) 

bar3 :: Integer -> Integer 
bar3 x = bar' 0 x 
    where bar' c 0 = c 
      bar' c x = c `seq` bar' (c + x) (pred x) 

bar4 :: Integer -> (Integer, Integer) 
bar4 x = (0, bar' 0 x) 
    where bar' c 0 = c 
      bar' c x = c `seq` bar' (c + x) (pred x) 

no lo hacen.

Creo que esto parece un error en el optimizador de GHC, y debería report it. Al mirar el núcleo (producido con -ddump-simpl), el argumento c no se evalúa estrictamente en todos los casos para las funciones de desbordamiento. bar2 es la versión de trabajo más cercana que encontré al original, y parece estar sobre especificada para mí.

Dado que tiene un caso de prueba muy simple, hay una buena posibilidad de que se solucione.