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

我正在研究 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

Note我只想知道这段代码中出现问题的原因是什么，任务本身并不重要。

问题是 Control.Monad.State.Lazy 的 (>>=) 太懒了，甚至 ($!) 也帮不了你。
尝试 Control.Monad.State.Strict，它应该达到 ($!)。

惰性状态 monad 的 (>>=) 根本不考虑 (value,state) 对，因此在到达结束之前完成一些评估的唯一方法是让f in m >>= f解构这对。这在这里不会发生，所以当 runState 最终想要结果时，你会得到一个巨大的重击，这对于堆栈来说太大了。

好吧，我已经吃过了，现在我可以详细说明了。让我使用惰性的旧（mtl-1.x）定义State smonad，在没有内部 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'

Now, 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.

In replicateM r tick，计算与 (>>) 链接在一起，因此k(>>=) 的定义是const tick。作为一个常量函数，它绝对不需要检查它的参数。所以tick >> tick becomes

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

the seq直到blobN必须进行评估。但需要将其评估为最外层的构造函数 - 对构造函数(,)- 足以触发 seq，进而导致此处完成评估。现在，在million，在最终之前不需要任何评估snd之后runState到达了。到那时，一个百万层的thunk已经建成了。评估那个重击需要推动很多let m' = m+1 in seq m' ((),m')在堆栈上直到达到初始状态，如果堆栈足够大可以容纳它们，那么它们就会被弹出并应用。所以这将是三个遍历，1.构建thunk，2.从thunk中剥离层并将它们推入堆栈，3.消耗堆栈。

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.
With 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，每次绑定时都会对所有内容进行全面评估，没有重击，没有堆栈。

但是，您仍然需要小心。在这种情况下，由于seq (resp. ($!)）以及所涉及类型的浅层结构，评估跟上应用(>>)。一般来说，具有更深层次的结构化类型和/或不具有seqs、C.M.S.Strict 还会构建大型 thunk，这可能导致堆栈溢出。在这些情况下，与 C.M.S.Lazy 生成的 thunk 相比，thunk 更简单，也更少纠缠。

另一方面，C.M.S.Lazy 的惰性允许进行 C.M.S.Strict 不可能进行的其他计算。例如，CMSLazy 提供了极少数的 monad 之一

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

终止。 [但请注意，此时状态将无法使用；在使用它之前，它必须遍历整个无限列表。因此，如果您执行类似操作，则在恢复状态相关计算之前，您必须put新鲜的状态。]