haskell space-leak writer-monad

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



space-leak writer-monad (3)

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

Primero, 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

Yo obtengo:

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

Para entenderlo mejor, he reimplementado una funcionalidad similar sin Writer o Sum, y si mantengo las cosas agradables y perezosas, 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 agregando seq a la ecuación:

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

He intentado ver varios bits de mi función foo , pero eso no parece ayudar. Además, he intentado usar Control.Monad.Writer.Strict pero eso tampoco hace una diferencia.

¿ Sum necesita ser estricta de alguna manera? ¿O me estoy perdiendo algo completamente diferente?

Notas

  • Puede que mi terminología esté equivocada aquí. Según el zoológico de fugas del espacio , mi problema se clasificaría como un ''desbordamiento de pila'', y si ese es el caso, ¿cómo convertiría foo a un estilo más iterativo? ¿Es mi recursión manual el problema?
  • Después de leer Haskell Space Overflow , tuve la idea de compilar con -O2 , solo para ver qué pasa. Este puede ser un tema para otra pregunta, pero con optimizaciones, incluso la función de mi bar seguridad no se ejecuta. Actualización : este problema desaparece si agrego -fno-full-laziness .

Creo que su comprensión es correcta.

Me interesa cómo funcionan 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 haga.

Creo que esto parece un error en el optimizador de GHC, y deberías reportarlo . Al observar 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 me parece sobre especificada.

Ya que tiene un caso de prueba muy simple, hay una buena probabilidad de que se solucione.

El problema con la mónada del escritor es que es >>= no es recursivo 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 puede ver, tiene que evaluar tanto m como ka para evaluar mappend que significa que toda la pila de llamadas recursivas debe forzarse antes de que se pueda evaluar el primer mappend . Creo que, independientemente de lo estricto que sea, la mónada de Writer provocará un desbordamiento de pila en su definición (¿o puede evitarse con una versión perezosa ?).

Si aún desea usar mónadas, puede probar el State que es recursivo. Ya sea una versión estricta de la misma con una 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 versión perezosa con estilo de paso de continuación (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 fuera posible usar ContT con Writer CPS también nos ayudaría con Writer , pero parece que no es posible definir ContT para MonadWriter :