延迟评估 - Space 泄漏

Question

Thinking Functionally with Haskell 提供以下代码用于计算 Float 列表的 mean。

mean :: [Float] -> Float
mean [] = 0
mean xs = sum xs / fromIntegral (length xs)

教授。理查德伯德评论：

Now we are ready to see what is really wrong with mean: it has a space leak. Evaluating mean [1..1000] will cause the list to be expanded and retained in memory after summing because there is a second pointer to it, namely in the computation of its length.

如果我对这段文字的理解正确，他是说，如果在长度计算中没有指向 xs 的指针，那么 xs 内存可能已经被释放计算 sum?

之后

我的困惑是 - 如果 xs 已经在内存中，那么 length 函数是否会简单地使用已经被占用的相同内存？

我不明白 space 这里的漏洞。

Answer 1

sum函数不需要将整个列表保存在内存中；它可以一次查看一个元素，然后在移动到下一个元素时忘记它。

因为 Haskell 默认情况下有惰性求值，如果你有一个创建列表的函数，sum 可以在整个列表不在内存中的情况下使用它（每次一个新元素是由生产函数生成，它将被 sum 消耗然后释放。

length 也发生了完全相同的事情。

另一方面，mean 函数将列表提供给 sum 和 length。所以在 sum 的评估期间，我们需要将列表保存在内存中，以便稍后 length 可以处理它。

[更新]要清楚，列表最终将被垃圾收集。问题是它停留的时间比需要的时间长。在这种简单的情况下，这不是问题，但在对无限流进行操作的更复杂的函数中，这很可能会导致内存泄漏。

Answer 2

space 泄漏是整个评估的 xs 都保存在 length 函数的内存中。这是浪费，因为我们不会在评估 sum 后使用列表的实际值，也不会同时需要它们全部在内存中，但是 Haskell 不知道那。

消除 space 泄漏的一种方法是每次都重新计算列表：

sum [1..1000] / fromIntegral (length [1..1000])

现在，应用程序可以在计算 sum 时立即开始丢弃第一个列表中的值，因为表达式中的其他任何地方都没有引用它。

length也是如此。它生成的 thunk 可以立即标记为删除，因为没有其他东西可能需要它进一步评估。

编辑：

sum 在 Prelude 中的实施：

sum l = sum' l 0
  where
    sum' []     a = a
    sum' (x:xs) a = sum' xs (a+x)

Answer 3

if there was no pointer to xs in the length computation, then the xs memory could've been freed after calculating the sum?

不，您在这里错过了惰性求值的重要方面。没错，length 将使用与 sum 调用期间分配的内存相同的内存，即我们在其中扩展整个列表的内存。

但这里的要点是根本不需要为整个列表分配内存。如果没有 length 计算而只有 sum，那么内存可以在计算 sum[ 期间被释放 =44=]。请注意，列表 [1..1000] 仅在使用时 延迟生成 ，因此实际上 mean [1..1000] 应该运行常量 space .

您可以像下面这样编写函数，以了解如何避免这种 space 泄漏：

import Control.Arrow mean [] = 0 mean xs = uncurry (/) $ foldr (\x -> (x+) *** (1+)) (0, 0) xs -- or more verbosely mean xs = let (sum, len) = foldr (\x (s, l) -> (x+s, 1+l)) (0, 0) in sum / len

应该只遍历xs一次。然而，Haskell 是该死的懒惰 - 仅在评估 sum 时才计算第一个元组组件，而仅在稍后对 len 计算第二个元组组件。我们需要 use some more tricks 来实际强制评估：

{-# LANGUAGE BangPatterns #-} import Data.List mean [] = 0 mean xs = uncurry (/) $ foldl' (\(!s, !l) x -> (x+s, 1+l)) (0,0) xs

实际上运行常量 space，您可以使用 :set +s.
在 ghci 中确认

Answer 4

其他人已经解释了问题所在。最干净的解决方案可能是使用 Gabriel Gonzalez 的 foldl package。具体来说，您需要使用

import qualified Control.Foldl as L
import Control.Foldl (Fold)
import Control.Applicative

meanFold :: Fractional n => Fold n (Maybe n)
meanFold = f <$> L.sum <*> L.genericLength where
  f _ 0 = Nothing
  f s l = Just (s/l)

mean :: (Fractional n, Foldable f) => f n -> Maybe n
mean = L.fold meanFold

延迟评估 - Space 泄漏

Lazy Evaluation - Space Leak

haskell