为什么简单地使用State monad会导致堆栈溢出？

Question

我正在玩State monad,我不知道在这段简单的代码中是什么导致了堆栈溢出.

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

注意 我只想知道在这段代码中导致问题的原因,任务本身本身并不重要.

Answer 1

问题是Control.Monad.State.Lazy(>> =)是如此懒惰,即使($!)也没有帮助你.
尝试Control.Monad.State.Strict,它应该到达($!).

慵懒状态单子的(>> =)不看都在(值,状态)对,所以达到的具有月底前得到一些评价做的唯一途径f在m >>= f解构对.这不会发生在这里,所以你得到一个巨大的thunk,当runState最终想要一个结果时,它对于堆栈来说太大了.

好的,我已经吃了,现在我可以详细说明了.让我使用懒惰State smonad 的旧(mtl-1.x)定义,没有内部monad就更容易看到它.新的(mtl-2.x)定义type State s = StateT s Identity表现相同,只是更多的写作和阅读.(>> =)的定义是

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

现在,let绑定是懒惰的,因此这是

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

只是更具可读性.所以(>> =)让blob完全没有评估.只有在k需要检查fst blob以确定如何继续或k a需要检查时才需要进行评估snd blob.

在replicateM r tick,计算用(>>)链接,所以kin(>> =)的定义是const tick.作为一个常数函数,它绝对不需要检查它的论点.因此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

在seq没有触及到blobN必须进行评估.但是需要将它评估到最外层的构造函数 - 对构造函数(,)- 足以触发seq,这反过来会导致完整的评估.现在,在到达之后million,没有任何东西需要任何评估.到那时,已经建造了一个拥有一百万层的thunk.评估thunk需要在堆栈上推送许多直到达到初始状态,并且如果堆栈足够大以容纳它们,则它们将被弹出并应用.所以它是三次遍历,1.构建thunk,2.从thunk剥离层并将它们推到堆栈上,3.消耗堆栈.sndrunStatelet m' = m+1 in seq m' ((),m')

Control.Monad.State.Strict的(>> =)严格到足以seq在每个绑定上强制s,因此只有一个遍历,没有(非平凡)thunk被构建并且计算在恒定空间中运行.定义是

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

重要的区别在于case表达式中的模式匹配是严格的,这里blob必须对最外层的构造函数进行求值,以使其与中的模式匹配case.
随着m = tick = State (\m -> let m' = m+1 in seq m' ((),m'))必要的部分成为

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

模式匹配要求((), s')[对(,)构造函数] seq的评估,通过与评估相关联s' = s+1,对每个绑定,没有thunks,没有堆栈进行全面评估.

但是,你仍然需要小心.在这种情况下,由于所涉及类型的seq(相应的($!))和浅层结构,评估保持应用(>>).通常,对于更深层次的结构化类型和/或没有seqs,CMSStrict也会构建大的thunk,这可能导致堆栈溢出.在这些情况下,thunk比CMSLazy生成的更简单,更少纠缠.

另一方面,CMSLazy的懒惰允许CMSStrict无法进行的其他计算.例如,CMSLazy提供了极少数monad之一

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

终止.[但请注意,该州无法使用; 在它可以使用之前,它必须遍历整个无限列表.所以,如果你做了类似的事情,在恢复依赖状态的计算之前,你必须put处于一个新的状态.