Perché questo semplice uso della monade di stato causa uno stack overflow?

Question

Stavo giocando con la monade di stato e non so cosa stia causando l'overflow dello stack in questo semplice pezzo di codice.

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 Vorrei solo sapere che cosa sta causando il problema in questo pezzo di codice, il compito in sé non è importante di per sé.

Answer 1

Il problema è che Control.Monad.State.Lazy's (>> =) è così pigro che nemmeno il ($!) Non ti aiuta.
Prova Control.Monad.State.Strict, che dovrebbe raggiungere ($!).

Il (>> =) della monade di stato lazy non guarda affatto alla coppia (valore, stato), quindi l'unico modo per ottenere una valutazione eseguita prima della fine è il f in m >>= f decostruisci la coppia. Questo non succede qui, quindi ottieni un enorme thunk, che è troppo grande per lo stack quando runState vuole finalmente un risultato.

Ok, ho mangiato, ora posso elaborare. Consentitemi di usare la vecchia definizione (mtl-1.x) della monade pigra State s, è un po 'più facile vederla senza la monade interiore. La nuova definizione (mtl-2.x) type State s = StateT s Identity si comporta allo stesso modo, è solo più di scrittura e lettura. La definizione di (>> =) era

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

Ora, let attacchi sono pigri, quindi questa è

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

solo più leggibile

. Quindi (>> =) lascia il blob completamente non valutato. La valutazione è necessaria solo se k ha bisogno di ispezionare fst blob per determinare come continuare, oppure k a ha bisogno di ispezionare snd blob.

In replicateM r tick, i calcoli sono concatenati con (>>), quindi la definizione k in (>> =) è const tick. Come funzione costante, non ha assolutamente bisogno di esaminare la sua argomentazione. Così tick >> tick diventa

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 

il seq non viene toccato fino blobN deve essere valutata. Ma la necessità di valutarlo per il costruttore più esterno - il costruttore di coppie (,) - sarebbe sufficiente per attivare il seq e questo porterebbe a sua volta alla valutazione completa qui. Ora, in million, nulla richiede alcuna valutazione fino al snd finale dopo il raggiungimento dello runState. A quel punto, è stato costruito un thunk con un milione di strati. Valutare che thunk richiede spingere molti let m' = m+1 in seq m' ((),m') nello stack fino a quando non viene raggiunto lo stato iniziale e se lo stack è abbastanza grande da contenere, verranno quindi inseriti e applicati. Quindi sarebbero tre traversamenti, 1. costruire il thunk, 2. staccare gli strati dal thunk e spingerli sullo stack, 3. consumare lo stack.

Il (>> =) di Control.Monad.State.Strict è abbastanza rigoroso da forzare il seq s su ciascun bind, quindi c'è solo un attraversamento, nessun (non banale) thunk è costruito e il calcolo viene eseguito in modo costante spazio. La definizione è

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

La differenza importante è che il pattern matching in case espressioni è rigorosa, qui il blob deve essere valutata al costruttore esterno per abbinare contro il modello nel case.
Con m = tick = State (\m -> let m' = m+1 in seq m' ((),m')) parte essenziale diventa

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

Il pattern match richiede la valutazione di ((), s') [al (,) costruttore], dal seq che è legato alla valutazione di s' = s+1, tutto è completamente valutata ogni legame, niente thunk, niente stack.

Tuttavia, è comunque necessario fare attenzione. In questo caso, a causa dello seq (rispettivamente ($!)) e della struttura superficiale dei tipi coinvolti, la valutazione è stata mantenuta con l'applicazione di (>>). In generale, con tipi strutturati più profondi e/o senza seq s, C.M.S.Strict crea anche thunk di grandi dimensioni che possono portare a overflow dello stack. I thunk sono un po 'più semplici e meno aggrovigliati di quelli generati da C.M.S.Lazy in quelle circostanze.

D'altra parte, la pigrizia di C.M.S.Lazy consente altri calcoli impossibili con C.M.S.Strict. Ad esempio, C.M.S.Lazy fornisce una delle pochissime monadi in cui

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

termina. [Ma sii consapevole che lo stato è quindi inutilizzabile; prima che potesse essere usato, avrebbe dovuto percorrere l'intera lista infinita. Quindi, se fai qualcosa del genere, prima di poter riprendere i calcoli dipendenti dallo stato, devi put uno stato nuovo.]