¿Por qué este uso simple de la mónada de estado causa un desbordamiento de pila?

Question

Estaba jugando con la mónada de estado, y no sé qué está causando el desbordamiento de pila en esta simple pieza de código.

import Control.Monad.State.Lazy 

tick :: State Int Int 
tick = do n <- get 
     put $! (n+1) 
     return n 

million :: Int 
million = snd $ runState (mapM_ (const tick) [1..1000000]) 0 

main = print million 

Nota Me gustaría saber lo que está causando el problema de esta pieza de código, la tarea en sí no es importante per se.

Answer 1

El problema es que Control.Monad.State.Lazy's (>> =) es tan vago que incluso el ($!) No lo ayuda.
Pruebe Control.Monad.State.Strict, que debería alcanzar el ($!).

La (>> =) de la mónada de estados perezosos no se ve en absoluto en el par (valor, estado), por lo que la única forma de realizar una evaluación antes de alcanzar el final es teniendo f en m >>= f deconstruir el par Eso no sucede aquí, así que obtienes un gran thunk, que es demasiado grande para la pila cuando runState finalmente quiere un resultado.

Bien, he comido, ahora puedo dar más detalles. Permítanme usar la antigua definición (mtl-1.x) de la mónada State s perezosa, es un poco más fácil de ver allí sin la mónada interna. La nueva definición (mtl-2.x) type State s = StateT s Identity se comporta de la misma manera, es solo más escritura y lectura. La definición de (>> =) era

m >>= k = State $ \s -> let 
    (a, s') = runState m s 
    in runState (k a) s' 

Ahora, let fijaciones son perezosos, por lo tanto, esto es

m >>= k = State $ \s -> let 
    blob = runState m s 
    in runState (k $ fst blob) (snd blob) 

sólo es más legible

. Entonces, el (>> =) deja el blob completamente sin evaluar. La evaluación solo es necesaria si k necesita inspeccionar fst blob para determinar cómo continuar o k a necesita inspeccionar snd blob.

En replicateM r tick, los cálculos están encadenados con (>>), por lo que la definición k en (>> =) es const tick. Como función constante, definitivamente no necesita inspeccionar su argumento. Así se convierte en tick >> tick

State $ \s -> 
    let blob1 = (\n -> let n' = n+1 in seq n' ((),n')) s 
     blob2 = (\m -> let m' = m+1 in seq m' ((),m')) (snd blob1) 
    in blob2 

la seq no se toca hasta blobN tiene que ser evaluado. Pero la necesidad de evaluarlo al constructor más externo, el constructor de pares (,), sería suficiente para activar el seq y eso a su vez llevaría a una evaluación completa aquí. Ahora, en million, nada requiere ninguna evaluación hasta que se alcanza el snd final después del runState. En ese momento, se ha construido un procesador con un millón de capas. La evaluación de ese procesador requiere empujar muchos let m' = m+1 in seq m' ((),m') en la pila hasta que se alcance el estado inicial, y si la pila es lo suficientemente grande como para contenerlos, se abrirán y aplicarán. Así que serían tres recorridos, 1. construyendo el procesador, 2. quitando capas del procesador y empujándolos en la pila, 3. consumiendo la pila.

El (>> =) de Control.Monad.State.Strict es sólo lo suficientemente estrictas para obligar a los seq s en cada unen, por tanto, sólo hay un recorrido, no (no trivial) de procesador está construido y el cálculo se ejecuta en constante espacio. La definición es

m >>= k = State $ \s -> 
    case runState m s of 
     (a, s') -> runState (k a) s' 

La diferencia importante es que la coincidencia de patrones en case expresiones es estricta, aquí la blob tiene que ser evaluado para el constructor más externa para que coincida con el patrón en el case.
Con m = tick = State (\m -> let m' = m+1 in seq m' ((),m')) la parte esencial se convierte en

case let s' = s+1 in seq s' ((),s') of 
    (a, s'') -> runState (k a) s'' 

El patrón de adaptarse a las demandas de la evaluación de ((), s') [a la (,) constructor], por el seq que está ligado a la evaluación de s' = s+1, todo está completamente evaluado en cada enlace, no thunks, no stack.

Sin embargo, todavía debe tener cuidado. En este caso, debido a seq (resp. ($!)) y la estructura superficial de los tipos involucrados, la evaluación se mantuvo con la aplicación (>>). En general, con tipos estructurados más profundos y/o sin seq s, C.M.S.Strict también crea grandes thunk que pueden conducir al desbordamiento de la pila. Los thunk son simplemente un poco más simples y menos enredados que los generados por C.M.S.Lazy en esas circunstancias.

Por otro lado, la pereza de C.M.S.Lazy permite otros cálculos que son imposibles con C.M.S.Strict. Por ejemplo, C.M.S.Lazy proporciona una de las pocas mónadas donde

take 100 <$> mapM_ something [1 .. ] 

termina. [Pero tenga en cuenta que el estado es entonces inutilizable; antes de poder usarse, debería viajar por toda la lista infinita. Entonces, si hace algo como eso, antes de poder reanudar los cálculos dependientes del estado, tiene que put un nuevo estado.]