为什么简单使用State monad导致堆栈溢出？ [英] Why does this simple use of the State monad cause a stack overflow?

问题描述

我正在玩国家monad，我不知道这个简单的代码中是什么导致了堆栈溢出。

  import Control.Monad.State.Lazy 
 
 tick :: State Int Int 
 tick = do n<  -  get 
 put $！ （n + 1）
返回n 
 
 million :: Int 
 million = snd $ runState（mapM_（const tick）[1..1000000]）0 
 
 main =印记百万
  

注意
I只是想知道是什么原因导致了这段代码中的问题，本身并不重要。

问题在于Control.Monad.State.Lazy（>> =）很懒，甚至连（$！）都不能帮助你。

尝试Control.Monad.State.Strict，应该达到（$！）。

懒惰状态monad的（>> =）在（值，状态）对中并不全是，所以唯一在达成目标之前完成一些评估的方法是在 m>>> = f deconstruct中具有 f 这对。这不会发生在这里，所以你会得到一个巨大的thunk，这对于runState最终需要结果的堆栈来说太大了。

好吧，我吃过了，现在我可以详细阐述。让我使用懒惰 State monad的旧（mtl-1.x）定义，在没有内部monad的情况下看到它更容易一些。新的（mtl-2.x）定义类型State s = StateT s Identity 的行为相同，只是更多的写入和读取。 （>> =）的定义是

  m>>> = k = State $ \s  - >在runState（ka）中设置
（a，s'）= runState ms 
'
  

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

  m>> = k = State $ \ s  - >让
 blob = runState ms 
在runState（k $ fst blob）（snd blob）
  

只有更多的可读性。所以（>> =）让blob完全没有评价。如果 k 需要检查 fst blob 以确定如何继续，或者 ka 需要检查 snd blob 。

在 replicateM （>>），因此（>> =）的定义中的 k 是 const tick 。作为一个常数函数，它绝对不需要检查它的参数。所以 tick>> tick 变成



  State $ \s  - > 
 let blob1 =（\ n  - > let n'= n + 1 in seq n'（（），n'））s 
 blob2 =（\ m  - > let m' =（），m'）（snd blob1）
 in blob2 
  

seq 直到 blobN 必须被评估。但是需要将它评估到最外层的构造函数 - 构造函数（，） - 足以触发seq，这将导致完整的评估。现在，在 million 中，在 runState 之后的最后 snd code>已到达。到那时，已经建成了一个拥有一百万层的thunk。评估thunk需要在堆栈上推送许多 let m'= m + 1，直到达到初始状态，并且如果堆叠足够大以容纳它们，然后它们将被弹出并施加。所以它会进行三次遍历，1.构建thunk，2.从thunk中剥离层并将它们推入堆栈，3.消耗堆栈。

（>> =）的Control.Monad.State.Strict足够严格，可以强制每个绑定上的 seq s，因此只有一个遍历，没有（非平凡）thunk被构建并且计算在恒定空间中运行。
定义为：

  m>>> = k = State $ \s  - > 
案例runState m s 
（a，s'） - > runState（ka）s'
  

重要的区别在于中的模式匹配表达式是严格的，这里 blob 必须被计算到最外层的构造函数中，以便与中的模式匹配（（），m（m，m）= m + 1） '））主要部分变为

  case let s'= s + 1 in seq s' （（），s'）
（a，s''） - > runState（ka）s''
  

模式匹配要求评估通过 seq 对<$ c $（$，$ s）） [到（，）构造函数] c> s'= s + 1 ，一切都在每一个绑定上完全评估，没有thunk，没有堆栈。

然而，你仍然需要要小心。在这种情况下，由于 seq （分别为（$！））和相关类型的浅层结构，使用（>>）进行评估。一般来说，对于更深的结构化类型和/或没有 seq s，C.M.S.Strict也会构建可导致堆栈溢出的大型thunk。在这些情况下，thunk只是比CMSLazy生成的那些简单一些和较少纠结。

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

 取100 $< $> mapM_ [1 ..] 
  

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

中。

I was playing around with the State monad, and I don't know what's causing the stack overflow in this simple piece of code.

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 I would just like to know what's causing the problem in this piece of code, the task itself is not important per se.

解决方案

The problem is that Control.Monad.State.Lazy's (>>=) is so lazy that even the ($!) doesn't help you.
Try Control.Monad.State.Strict, that should reach the ($!).

The (>>=) of the lazy state monad doesn't look at all at the (value,state) pair, so the only way to get some evaluation done before the end is reached is having the f in m >>= f deconstruct the pair. That doesn't happen here, so you get a huge thunk, that is too large for the stack when runState finally wants a result.

Okay, I've eaten, now I can elaborate. Let me use the old (mtl-1.x) definition of the lazy State s monad, it's a bit easier to see there without the inner monad. The new (mtl-2.x) definition type State s = StateT s Identity behaves the same, it's just more writing and reading. The definition of (>>=) was

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

Now, let bindings are lazy, hence this is

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

only more readable. So the (>>=) lets the blob completely unevaluated. Evaluation is only required if k needs to inspect fst blob to determine how to continue, or k a needs to inspect snd blob.

In replicateM r tick, the computations are chained with (>>), so the k in (>>=)'s definition is const tick. As a constant function, it most definitely doesn't need to inspect its argument. So 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 isn't touched until blobN has to be evaluated. But needing to evaluate it to the outermost constructor - the pair constructor (,) - would be enough to trigger the seq and that would in turn lead to complete evaluation here. Now, in million, nothing requires any evaluation until the final snd after the runState is reached. By that time, a thunk with a million layers has been built. Evaluating that thunk requires pushing many let m' = m+1 in seq m' ((),m') on the stack until the initial state is reached, and if the stack is large enough to hold them, they'd then be popped and applied. So it'd be three traversals, 1. building the thunk, 2. peeling layers from the thunk and pushing them on the stack, 3. consuming the stack.

The (>>=) of Control.Monad.State.Strict is just strict enough to force the seq s on each bind, thus there's only one traversal, no (nontrivial) thunk is built and the computation runs in constant space. The definition is

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

The important difference is that pattern matching in case expressions is strict, here the blob has to be evaluated to the outermost constructor to match it against the pattern in the case.
With m = tick = State (\m -> let m' = m+1 in seq m' ((),m')) the essential part becomes

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

The pattern-match demands the evaluation of ((), s') [to the (,) constructor], by the seq that is tied to the evaluation of s' = s+1, everything is fully evaluated on each bind, no thunks, no stack.

However, you still need to be careful. In this case, due to the seq (resp. ($!)) and the shallow structure of the involved types,evaluation kept up with application of (>>). In general, with deeper structured types and/or without seqs, C.M.S.Strict also builds large thunks which can lead to stack overflow. The thunks are just a bit simpler and less entangled than those generated by C.M.S.Lazy in those circumstances.

On the other hand, the laziness of C.M.S.Lazy allows other computations that are impossible with C.M.S.Strict. For example, C.M.S.Lazy provides one of the very few monads where

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

terminates. [But be aware that the state is then unusable; before it could be used, it would have to travel through the entire infinite list. So, if you do something like that, before you can resume state-dependent computations, you have to put a fresh state.]

这篇关于为什么简单使用State monad导致堆栈溢出？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！