haskell - 为什么简单地使用 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，它应该达到 ($!)。

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

好的，我已经吃过了，现在我可以详细说明。让我使用惰性 State s 的旧 (mtl-1.x) 定义monad，没有内部 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绑定(bind)是惰性的，因此这是

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 ，计算用 (>>) 链接，所以 k in (>>=) 的定义是 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 , 在最终的 snd 之前没有任何评估需要在 runState 之后到达了。到那时，已经构建了具有一百万层的thunk。评估该 thunk 需要推送许多 let m' = m+1 in seq m' ((),m')在堆栈上直到达到初始状态，如果堆栈大到足以容纳它们，它们就会被弹出并应用。所以这将是三个遍历，1. 构建 thunk，2. 从 thunk 中剥离层并将它们推送到堆栈上，3. 消耗堆栈。

Control.Monad.State.Strict 的 (>>=) 严格到足以强制 seq s 在每个绑定(bind)上，因此只有一次遍历，没有(非平凡的)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 的评估有关，在每次绑定(bind)时都会对所有内容进行全面评估，没有 thunk，没有堆栈。

但是，您仍然需要小心。在这种情况下，由于 seq (分别为 ($!))和所涉及类型的浅层结构，评价跟上 (>>)的应用.通常，具有更深层次的结构化类型和/或没有 seq s，C.M.S.Strict 还构建可能导致堆栈溢出的大型 thunk。在这种情况下，与 C.M.S.Lazy 生成的 thunk 相比，thunk 更简单且更少纠缠。

另一方面，C.M.S.Lazy 的惰性允许 C.M.S.Strict 无法进行的其他计算。例如，C.M.S.Lazy 提供了为数不多的单子(monad)之一，其中

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

终止。 [但请注意，此时状态将无法使用；在使用它之前，它必须遍历整个无限列表。所以，如果你做这样的事情，在你可以恢复状态相关的计算之前，你必须 put一个新鲜的状态。]