11

我正在学习 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 中进行评估时，我的直觉完全失败了。

4

2 回答 2

5

罪魁祸首隐藏在内心深处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) }

特别是，看一下 in 的单个foldr展开sequence

foldr k (return []) (replicate n roll')

do x  <- roll'
   xs <- foldr k (return []) (replicate n roll')
   return (x:xs)

换句话说，除非我们可以(x : ... thunk ... )提前延迟返回，否则我们将在返回第一个值之前展开整个复制。关于我们是否可以返回该值的答案与(>>=)我们 monad 中的定义有关。

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.StateLazy(>>=)

m >>= k  = StateT $ \s -> do
    ~(a, s') <- runStateT m s
    runStateT (k a) s'

所以我们可以看到显式的无可辩驳的绑定发生，这让我们可以继续懒惰地返回结果。

值得一看Joachim Breitner 最近对这个问题的评论。pipes在生态系统中也有很多这方面的工作conduit可能值得研究。

replicateM通常，由于我们在上面看到的排序概念，值得怀疑：“先构建头部，然后构建尾部，然后返回缺点”。

于 2013-12-19T20:13:34.367 回答
5

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

它溢出的原因是严格的，State或者需要递归地运行动作时间，然后才能构建列表。说得通俗一点，就是要把它所复制的所有动作的“效果”“组合”成一个巨大的“效果”。“结合”和“效果”这两个词非常模糊，可以表示无数种不同的事物，但它们是我们谈论这些抽象事物时所能得到的最好的东西。在几乎所有的 monad 选择中，具有较大值的最终都会溢出堆栈。奇怪的是，它没有懒惰。IOreplicateMiterationsreplicateMreplicateMState

要了解为什么它不会因 lazy 溢出State，您需要查看(>>=)for lazyState和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密切取决于做什么(>>=)。

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

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

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

于 2013-12-19T20:18:12.253 回答