Haskell中的评估和空间泄漏

2018-06-15 03:29:58

我正在学习Haskell，目前正试图将我的头围绕monad。在玩一些随机数字时，我又一次怠惰评估。为了简化以下几点：

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的评估时，我的直觉完全失败了。

这是因为Control.Monad.State重新导出Control.Monad.State.Lazy 。如果你导入了， Control.Monad.State.Strict ，都会以这种方式溢出。

严格的State或IO溢出的原因是， replicateM需要递归运行iterations次数，然后才能构建列表。松散地说， replicateM必须将它复制的所有动作的“效果”“组合”成一个巨大的“效果”。术语“组合”和“效果”非常含糊，可以表示无数不同的事物，但它们是关于我们谈论这种抽象事物的最佳选择。具有较大值的replicateM最终会在几乎所有的monad选项中溢出堆栈。这是事实，它不与懒惰State ，这是奇怪的。

要明白为什么它不会与懒惰State一起溢出，您需要查看lazy 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导致最终状态被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) }

具体来说，请按sequence单独展开foldr

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.State默认为Lazy版本。在那里， (>>=)被定义为

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

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

值得关注一下Joachim Breitner最近对这个问题的回顾。 pipes和conduit生态系统中还有许多工作值得研究。

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

链接地址: http://www.djcxy.com/p/43001.html

上一篇: Evaluation and space leaks in Haskell

下一篇: Why is seq bad?