haskell - Haskell 中的评估和空间泄漏

Question

我正在学习 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 ，第二个示例导致堆栈溢出。

为什么第一个版本在恒定空间中愉快地运行，而第二个版本爆炸了？

更广泛地说，你能推荐一些阅读 Material 来改善 Haskell 懒惰评估的心智模型吗？ (最好是中级入门。)因为在 Haskell 中进行评估时，我的直觉完全失败了。

Answer 1

这是因为 Control.Monad.State转口 Control.Monad.State.Lazy .如果您导入，Control.Monad.State.Strict ，两者都会以这种方式溢出。

它溢出的原因是严格的State或 IO是replicateM需要运行操作 iterations在它可以建立列表之前，递归的次数。简单地说，replicateM必须将其复制的所有 Action 的“效果”“组合”成一个巨大的“效果”。 “结合”和“效果”这两个词非常模糊，可以表示无数种不同的事物，但它们是我们谈论这些抽象事物时所能得到的最好的东西。 replicateM在几乎所有的 monad 选择中，具有较大值的最终都会溢出堆栈。这是事实，它没有懒惰 State这很奇怪。

看看为什么它不会因为懒惰而溢出State ，您需要查看 (>>=) 的详细信息懒惰的State , 和 replicateM .以下定义已大大简化，但它们反射(reflect)了说明其工作原理所需的细节。

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 的行为密切取决于 (>>=)做。

当您查看 (>>=) ，您会看到它生成了一个状态转换函数，该函数绑定(bind)了状态转换函数 x 的结果在 let 绑定(bind)中，然后返回转换函数的结果，它是 f 的结果应用于来自该绑定(bind)的参数。

好吧，那句话很清楚，但它真的很重要。让我们暂时看一下 lambda 内部。查看函数 (>>=) 的结果创建，你看 let {something to do with x} in {something to do with f and the results of the let binding} .这对于惰性评估很重要。这意味着它也许可以忽略 x ，或者可能是其中的一部分，当它评估 (>>=) , 如果特定函数 f允许它。在懒惰的情况下 State ，这意味着它可能会延迟计算 future 的状态值，如果 f可以在查看状态之前生成构造函数。

事实证明，这是允许它工作的原因。特殊方式 replicateM集合对 (>>=) 的调用，它会产生一个产生 (:) 的函数构造函数在检查传递给它们的状态之前。如果从不检查最终状态，这允许对列表进行增量处理。如果您查看最终状态，那会破坏增量功能的能力，因为最终状态需要完成所有工作来计算它。但是你使用 evalState导致最终状态未经检查就被丢弃，因此评估可以自由地逐步进行。