Dlaczego to proste użycie monady State powoduje przepełnienie stosu?

Question

Grałem z Monadą Stanową i nie wiem, co powoduje przelew przepełnienia tego prostego kawałka kodu.

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 

Uwaga Chciałbym tylko wiedzieć, co jest przyczyną problemu w tym kawałku kodu, samo zadanie nie jest ważne per se.

Answer 1

Problem polega na tym, że Control.Monad.State.Lazy (>> =) jest tak leniwy, że nawet ($!) Nie pomaga.
Spróbuj Control.Monad.State.Strict, który powinien osiągnąć wartość ($!).

Moneta (l = l) stanu leniwy nie wygląda na wszystkich w parze (wartość, stan), więc jedynym sposobem uzyskania oceny przed osiągnięciem końca jest uzyskanie f w m >>= f dekonstruować parę. To się tutaj nie zdarza, więc dostajesz wielki thunk, który jest zbyt duży dla stosu, kiedy runState w końcu chce wyniku.

Dobra, jadłem, teraz mogę rozwinąć. Pozwól mi użyć starej (mtl-1.x) definicji monady leniwy State s, jest to nieco łatwiejsze do zobaczenia bez wewnętrznej monady. Nowa (mtl-2.x) definicja type State s = StateT s Identity zachowuje się tak samo, to po prostu więcej pisania i czytania. Definicja (>> =) był

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

Teraz let Wiązania są leniwi, a więc jest to

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

tylko bardziej czytelny

. Tak więc (>> =) pozwala na całkowitą niedoszacowanie bloba. Ocena jest wymagana tylko wtedy, gdymusi przeprowadzić inspekcję fst blob, aby ustalić, jak kontynuować, lub k a, aby dokonać inspekcji snd blob.

W obliczenia są powiązane za pomocą (>>), więc definicja k w (>> =) to const tick. Jako funkcja stała zdecydowanie zdecydowanie nie musi sprawdzać swojej argumentacji. Więc tick >> tick staje

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 

seq nie dotknął aż blobN musi być ocenione. Ale potrzeba oceny go na najbardziej zewnętrznym konstruktorze - konstruktorze pary (,) - wystarczyłoby, aby wywołać seq, a to z kolei doprowadziłoby do pełnej oceny tutaj. Teraz, w million, nic nie wymaga żadnej oceny, dopóki nie zostanie osiągnięty ostateczny snd po osiągnięciu runState. Do tego czasu zbudowano thunk z milionem warstw. Ocena tego uderzenia wymaga popychania wielu na stos, dopóki nie osiągnie stanu początkowego, a jeśli stos będzie wystarczająco duży, by je pomieścić, zostaną one popped i zastosowane. Więc to będą trzy traversale, 1. budowanie thunk, 2. obieranie warstw z thunk i popychanie ich na stosie, 3. zużywanie stosu.

(= =) Control.Monad.State.Strict jest wystarczająco rygorystyczny, aby wymusić seq s na każdym wiązaniu, dlatego istnieje tylko jedno przejście, nie (nietrywialne) thunk jest budowane i obliczenia odbywają się w sposób ciągły przestrzeń. Definicja jest

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

Ważną różnicą jest to, że wzorzec dopasowania w case wyrażeń jest ścisła, tutaj blob musi być oceniana na najdalszym konstruktora, aby dopasować go do wzorca w case.
z m = tick = State (\m -> let m' = m+1 in seq m' ((),m')) zasadniczą część staje

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

wymaga Wzór meczu ocenę ((), s') [dla (,) konstruktora] przez seq, która jest związana z oceną s' = s+1, wszystko w pełni oceniony na każde wiązanie, brak ciosów, brak stosu.

Należy jednak zachować ostrożność. W tym przypadku, ze względu na seq (względnie ($!)) i płytką strukturę zaangażowanych typów, ocena była kontynuowana z zastosowaniem (>>). Ogólnie rzecz biorąc, w przypadku typów o głębszej strukturze i/lub bez C.M.S.Strict również buduje duże tony, które mogą prowadzić do przepełnienia stosu. Uderzenia są tylko trochę prostsze i mniej zaplątane niż te generowane przez C.M.S.Lazy w tych okolicznościach.

Z drugiej strony lenistwo C.M.S.Lazy umożliwia inne obliczenia, które są niemożliwe przy C.M.S.Strict. Na przykład, C.M.S.Lazy stanowi jedną z nielicznych monad gdzie

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

zakończony. [Ale pamiętaj, że państwo nie nadaje się do użytku; zanim można go było użyć, musiałby przejechać całą nieskończoną listę. Tak więc, jeśli zrobisz coś takiego, zanim będziesz mógł wznowić zależne od stanu obliczenia, musisz put świeża.]