我正在学习Haskell，目前正试图绕着monads。在玩一些随机数字时，我再一次被懒惰的评价绊倒了。为了简化以下内容：
roll :: State StdGen Int
roll = do
gen <- get
let (n, newGen) = randomR (0,1) gen
put newGen
return n
main = do
gen <- getStdGen
let x = sum $ evalState (replicateM iterations roll) gen
print x
变成这样的东西：
roll' :: IO Int
roll' = getStdRandom $ randomR (0,1)
main = do
x' <- fmap sum $ replicateM iterations roll'
print x'
在更多的 iterations，让我们说 1000 * 1000 * 10，第二个例子导致堆栈溢出。
为什么第一个版本在恒定空间中运行并且第二个版本爆炸？
更广泛地说，你能推荐一些阅读来改善Haskell懒惰评估的心理模型吗？ （介绍中级，最好是。）因为在Haskell的评估中，我的直觉完全让我失望。
这是因为 Control.Monad.State 转口 Control.Monad.State.Lazy。如果你导入了， Control.Monad.State.Strict，两者都会溢出。
它严重溢出的原因 State 要么 IO 就是它 replicateM 需要运行该操作 iterations 在它可以构建列表之前递归地进行。松散地说， replicateM 必须将它复制的所有行动的“效果”“结合”成一个巨大的“效果”。术语“结合”和“效果”非常模糊，可能意味着无数不同的东西，但它们是我们谈论这些抽象事物时最好的。 replicateM 具有较大的值将最终在几乎所有monad选项中溢出堆栈。这是事实，它不与懒惰 State 那很奇怪。
要知道为什么它不会溢出懒惰 State，你需要仔细研究一下 (>>=) 懒惰 State，和 replicateM。以下定义大大简化，但它们反映了说明其工作原理所需的详细信息。
newtype State s a = State { runState :: s -> (a, s) }
instance Monad (State s) where
return x = State $ \s -> (x, s)
x >>= f = State $ \s -> let (a, s') = runState x s in runState (f a) s'
replicateM :: Monad m => Int -> m a -> m [a]
replicateM 0 _ = return []
replicateM n mx | n < 0 = error "don't do this"
| otherwise =
mx >>= \x -> replicateM (n - 1) mx >>= \xs -> return (x:xs)
首先，看看 replicateM。注意什么时候 n 大于0，它是一个调用 (>>=)。所以的行为 replicateM 取决于什么 (>>=) 确实。
当你看 (>>=)，你会看到它产生一个状态转换函数，它绑定状态转换函数的结果 x 在let绑定中，然后返回结果的转换函数的结果 f 应用于该绑定的参数。
好吧，这个说法显然是泥巴，但这非常重要。让我们暂时看看lambda内部。看看功能的结果 (>>=) 你看，创造了 let {something to do with x} in {something to do with f and the results of the let binding}。这对于懒惰评估很重要。代表着 只是也许吧 它可以忽略 x在评估时，或者可能是其中的一部分 (>>=)，如果具体功能 f 允许它。在懒惰的情况下 State，这意味着它可能能够延迟计算未来的状态值，如果 f 在查看状态之前可以生成构造函数。
事实证明这是允许它工作的原因。特别的方式 replicateM 组装电话 (>>=)，它产生一个产生的功能 (:) 构造函数在检查传递给它们的状态之前。如果从未检查过最终状态，则允许对列表进行增量处理。如果您查看最终状态，则会破坏逐步运行的能力，因为最终状态需要完成所有工作来计算它。但是你的使用 evalState导致最终状态被剔除未经审查，因此评估可以自由地逐步进行。
罪魁祸首深藏在内心深处 replicateM。让我们来看看来源。
replicateM :: (Monad m) => Int -> m a -> m [a]
replicateM n x = sequence (replicate n x)
sequence :: Monad m => [m a] -> m [a]
sequence ms = foldr k (return []) ms where
k m m' = do { x <- m; xs <- m'; return (x:xs) }
特别是，看看单个展开的 foldr 在 sequence
foldr k (return []) (replicate n roll')
do x <- roll'
xs <- foldr k (return []) (replicate n roll')
return (x:xs)
换句话说，除非我们可以懒洋洋地回归 (x : ... thunk ... ) 那么我们将在返回第一个值之前展开整个复制。关于我们是否可以返回该值的答案与...的定义有关 (>>=) 在我们的单子里。
roll' >>= \x -> foldr k (return []) (replicate n roll') >>= \xs -> return (x:xs)
从那以后可以说是公平的 IO 执行它会按顺序执行的副作用 - 我们肯定要展开整个事情。 State 有两种形式， Control.Monad.Trans.State.Lazy 版本和 Control.Monad.Trans.State.Strict 版本在哪里 Control.Monad.Trans.State 默认为 Lazy 版。那里， (>>=) 被定义为
m >>= k = StateT $ \s -> do
~(a, s') <- runStateT m s
runStateT (k a) s'
所以我们可以看到显式的无可辩驳绑定发生，让我们继续懒惰地返回结果。
值得一看 Joachim Breitner最近对这个问题进行了回顾。在这方面还有很多工作要做 pipes 和 conduit 可能值得研究的生态系统。
一般来说，值得怀疑 replicateM 然而，由于我们在上面看到的排序概念：“建立头脑 然后 打造尾巴 然后 回归利弊“。