haskell - ¿Por qué este simple uso de la mónada estatal provoca un desbordamiento de pila?

stack-overflow monads

Question

Estaba jugando con la mónada estatal y no sé qué está causando el desbordamiento de pila en este simple 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 : solo me gustaría saber qué está causando el problema en este fragmento 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 te ayuda.
Intente Control.Monad.State.Strict, que debería alcanzar el ($!).

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

Bueno, ya he comido, ahora puedo elaborar. Permítanme usar la antigua definición (mtl-1.x) de la mónada del State s perezoso, es un poco más fácil de ver allí sin la mónada interna. El nuevo type State s = StateT s Identity definición (mtl-2.x) type State s = StateT s Identity 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 enlaces sean perezosos, por lo tanto esto es

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

Sólo 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 ka necesita inspeccionar snd blob .

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

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 blobN no se toca hasta que se debe evaluar blobN . Pero la necesidad de evaluarlo para el constructor más externo, el constructor de pares (,) , sería suficiente para desencadenar la secuencia y eso a su vez conduciría a una evaluación completa aquí. Ahora, en million , nada requiere una evaluación hasta que se alcance la última snd después de runState el runState . Para entonces, se ha construido un thunk con un millón de capas. Evaluar que thunk requiere presionar 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 sostenerlos, entonces estarán Estalló y se aplicó. Entonces serían tres recorridos, 1. construir el golpe, 2. quitar las capas del mango y empujarlas en la pila, 3. consumir el montón.

El (>> =) de Control.Monad.State.Strict es lo suficientemente estricto como para forzar las seq en cada enlace, por lo tanto, solo se genera un thunk transversal (no trivial) y el cálculo se ejecuta en espacio constante. La definicion 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 las expresiones de case es estricta, en este caso el blob debe evaluarse con el constructor más externo 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 coincidencia exige la evaluación de ((), s'') [al (,) constructor], por la seq que está vinculada a la evaluación de s'' = s+1 , todo se evalúa completamente en cada enlace, no gracias, no hay pila.

Sin embargo, todavía hay que tener cuidado. En este caso, debido a la seq (resp. ($!) ) Y la estructura superficial de los tipos involucrados, la evaluación se mantuvo con la aplicación de (>>) . En general, con tipos estructurados más profundos y / o sin seq s, CMSStrict también construye grandes thunk que pueden provocar un desbordamiento de la pila. Los thunks son solo un poco más simples y menos enredados que los generados por CMSLazy en esas circunstancias.

Por otro lado, la pereza de CMSLazy permite otros cálculos que son imposibles con CMSStrict. Por ejemplo, CMSLazy proporciona una de las pocas mónadas donde

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

termina [Pero ten en cuenta que el estado es entonces inutilizable; antes de que pudiera usarse, tendría que viajar a través de toda la lista infinita. Entonces, si haces algo así, antes de poder reanudar los cálculos dependientes del estado, debes put un estado nuevo.]