问题是 Control.Monad.State.Lazy 的 (>>=) 太懒了,甚至 ($!) 也无济于事。
试试 Control.Monad.State.Strict,它应该达到 ($!)。
惰性状态单子的 (>>=) 根本不查看 (value,state) 对,因此在到达结束之前完成一些评估的唯一方法是让f
inm >>= f
解构对。这不会发生在这里,所以你会得到一个巨大的 thunk,当 runState 最终想要一个结果时,这对于堆栈来说太大了。
好的,我已经吃过了,现在我可以详细说明。让我使用惰性State s
单子的旧(mtl-1.x)定义,没有内部单子更容易看到。新的 (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
中,计算与 (>>) 链接在一起,因此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
但是需要将它评估到最外层的构造函数 - pair 构造函数(,)
- 就足以触发 seq ,这反过来又会导致在这里完成评估。现在,在 中,在达到之后million
的最终结果之前不需要任何评估。到那时,已经构建了具有一百万层的thunk。评估这个 thunk 需要在堆栈上推送许多,直到达到初始状态,如果堆栈大到足以容纳它们,它们就会被弹出并应用。所以这将是三个遍历,1. 构建 thunk,2. 从 thunk 中剥离层并将它们推送到堆栈上,3. 消耗堆栈。snd
runState
let 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')
[to the (,) 构造函数] 的求值,通过seq
与 的求值相关联的s' = s+1
,在每次绑定时对所有内容进行完全求值,没有 thunk,没有堆栈。
但是,您仍然需要小心。在这种情况下,由于所涉及类型的seq
(resp. ($!)
)和浅层结构,评估跟上了(>>)
. 通常,对于更深层次的结构化类型和/或没有seq
s,CMSStrict 还会构建可能导致堆栈溢出的大型 thunk。在这些情况下,与 CMSLazy 生成的 thunk 相比,thunk 更简单且更少纠缠。
另一方面,CMSLazy 的惰性允许使用 CMSStrict 无法进行的其他计算。例如,CMSLazy 提供了为数不多的单子之一,其中
take 100 <$> mapM_ something [1 .. ]
终止。[但请注意,此时状态将无法使用;在使用它之前,它必须遍历整个无限列表。所以,如果你做这样的事情,在你可以恢复依赖于状态的计算之前,你必须进入put
一个新的状态。]