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

Question

我当时玩的是国家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的（>> =）在（值，状态）对上没有看到全部，所以在达到结束之前完成一些评估的唯一方法是让f在m >>= f解构这一对。这在这里没有发生，所以你会得到一个巨大的thunk，当runState最终需要结果时，这对于堆栈来说太大了。

好吧，我吃过了，现在我可以详细说明了。让我使用懒惰State s单元的旧（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，则仅需要评估。 （>>），因此（>> =）的定义中的k为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中，在达到runState之后的最终snd之前，不需要任何评估。到那时，已经建成了一个拥有一百万层的thunk。评估该thunk需要推动堆栈上的许多let m' = m+1 in seq m' ((),m')，直到达到初始状态，并且如果堆栈足够大以容纳它们，则会弹出并应用它们。所以这将是三次遍历，1.建立thunk，2.从thunk中剥离层并将它们推入堆栈，3.消耗堆栈。

Control.Monad.State.Strict的（>> =）严格得足以在每个绑定上强制seq，因此只有一次遍历，没有（非平凡）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')评价[到（，）构造]，由该被绑定到的s' = s+1评价的seq，一切都完全评估上每个绑定，没有thunk，没有堆栈。

但是，您仍然需要小心。在这种情况下，由于seq（分别为($!)）和相关类型的浅层结构，评估与应用(>>)保持一致。一般来说，对于更深层次的结构类型和/或没有seq s，C.M.S.Strict也会构建可能会导致堆栈溢出的大型thunk。在这些情况下，thunk只是比C.M.S.Lazy所产生的更简单和更少纠缠。

另一方面，C.M.S.Lazy的懒惰允许其他计算在C.M.S.Strict中是不可能的。例如，C.M.S.Lazy提供了极少数单子之一，其中

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

终止。 [但请注意，国家是无法使用的;在它可以被使用之前，它将不得不遍历整个无限列表。所以，如果你这样做，在恢复状态依赖计算之前，你必须将put作为一个新的状态。]