Haskell中的评估和空间泄漏

本文介绍了Haskell中的评估和空间泄漏的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述 29岁程序员，3月因学历无情被辞！ 我正在学习Haskell，目前正试图将我的头围绕monads。在玩一些随机数字时，我又一次怠惰评估。为了简化以下事项： roll :: State StdGen Int roll = do $ b $ （n，newGen）= randomR（0,1）gen 放置newGen 返回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' print x' 迭代，比如说 1000 * c> 1000 * 10 ，第二个例子导致堆栈溢出。 为什么第一个版本在恒定空间中运行并且第二个版本爆炸？ 更广泛地说，你可以推荐一些阅读材料来改善哈斯克尔懒惰的心理模型评价？ （介绍中间级别，最好是）。因为当谈到在Haskell中的评估时，我的直觉完全失败了。 是因为 Control.Monad.State 重新导出 Control.Monad.State.Lazy 。如果你导入了 Control.Monad.State.Strict ，两者都会以这种方式溢出。 溢出的原因严格 State 或 IO 是 replicateM 需要运行动作迭代次递归，然后才能构建列表。放松地说， replicateM 必须将它复制的所有动作的效果组合成一个巨大的效果。术语组合和效果非常含糊，可以表示无数不同的事物，但它们是关于我们谈论这种抽象事物的最佳选择。具有大值的 replicateM 最终会在几乎所有monad选项中溢出堆栈。这是事实，它不与懒惰 State 这是奇怪的。 要看看它为什么不溢出在懒惰 State 中，您需要查看（>> =） $ c> State 和 replicateM 。 newtype State sa = State {runState :: s - > （a，s）} 实例Monad（State）其中 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 _ =返回[] replicateM n mx | n< 0 =错误不要这样做 |否则= mx>> = \ x - > replicateM（n-1）mx>> = \ xs - >返回（x：xs） 首先看 replicateM 。请注意，当 n 大于0时，它是对（>> =）的调用。因此， replicateM 的行为取决于（>> =）的行为。 当您查看（>> =）时，您会看到它会生成一个状态转换函数，用于绑定状态转换的结果函数 x 在一个let绑定中，然后返回转换函数的结果，该函数的结果是应用于参数的 f 结果那是有约束力的。 好的，这句话很清楚，但它非常重要。让我们来看看lambda的内幕。看看函数（>> =）创建的结果，您会看到 let {对某事做些什么}用f和let绑定的结果} 。这对懒惰评估很重要。这意味着当它评估（>>>< / em>）时，它可以忽略 x =），如果特定函数 f 允许。如果 State ，这意味着如果 f 可以延迟计算将来的状态值在查看状态之前生成一个构造函数。 事实证明，它可以工作。特定的方式 replicateM 可以调用（>> =），它会产生一个函数，产生（：）构造函数，然后检查传递给它们的状态。这允许增量处理列表，如果最终状态从不被检查。如果你看到最终状态，那会破坏增量运行的能力，因为最终状态需要做所有的工作来计算它。但是你使用 evalState 导致最终状态被抛弃，所以评估可以自由进行。 I'm learning Haskell and currently trying to wrap my head around monads. While playing with some random number generation I got tripped on lazy evaluation once again. In an effort to simplify something close to the:roll :: State StdGen Introll = do gen <- get let (n, newGen) = randomR (0,1) gen put newGen return nmain = do gen <- getStdGen let x = sum $ evalState (replicateM iterations roll) gen print xinto something like this:roll' :: IO Introll' = getStdRandom $ randomR (0,1)main = do x' <- fmap sum $ replicateM iterations roll' print x'on a larger number of iterations, let's say 1000 * 1000 * 10, second example results in a stack overflow.Why is the first version happily runs in constant space and the second one blows up?Speaking more broadly, can you recommend some reading to improve one's mental model of Haskell's lazy evaluation? (Introductory to intermediate level, preferably.) Because when it comes to evaluation in Haskell, my intuition completely fails me. 解决方案 This is because Control.Monad.State re-exports Control.Monad.State.Lazy. If you imported, Control.Monad.State.Strict, both would overflow that way.The reason it overflows with strict State or IO is that replicateM needs to run the action iterations times recursively, before it can build the list. To put it loosely, replicateM must "combine" the "effects" of all the actions it replicates into one giant "effect". The terms "combine" and "effect" are very vague, and can mean an infinite number of different things, but they're about the best we've got for talking about such abstract things. replicateM with a large value will end up overflowing the stack in nearly every choice of monad. It's the fact that it doesn't with lazy State that's bizarre.To see why it doesn't overflow with lazy State, you need to look into the details of (>>=) for lazy State, and replicateM. The following definitions are greatly simplified, but they reflect the details necessary to illustrate how this works.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)So first, look at replicateM. Take note that when n is greater than 0, it is a call to (>>=). So the behavior of replicateM depends closely on what (>>=) does.When you look at (>>=), you see it produces a state transition function that binds the results of the state transition function x in a let binding, then returns the result of the transition function that's the result of f applied to arguments from that binding.Ok, that statement was clear as mud, but it's really important. Let's just look inside the lambda for the moment. Looking at the result of the function (>>=) creates, you see let {something to do with x} in {something to do with f and the results of the let binding}. This is important with lazy evaluation. It means that just maybe it can ignore x, or maybe part of it, when it evaluates (>>=), if the particular function f allows it to. In the case of lazy State, it means that it might be able to delay calculating future state values, if f can produce a constructor before looking at the state.This turns out to be what allows it to work. The particular way replicateM assembles calls to (>>=), it results in a function that produces (:) constructors before examining the state passed to them. This allows incremental processing of the list, if the final state is never examined. If you ever look at the final state, that destroys the ability to function incrementally, because the final state requires doing all the work to calculate it. But your use of evalState resulted in the final state being thrown away unexamined, so evaluation was free to proceed incrementally. 这篇关于Haskell中的评估和空间泄漏的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！ 上岸，阿里云！