懒惰的评估-空间泄漏

Question

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

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

教授。Richard Bird评论：

现在我们准备看看mean到底出了什么问题：它有太空泄漏。计算mean [1..1000]将导致列表在求和后被扩展并保留在内存中，因为有第二个指针指向它，即在计算它的长度时。

如果我正确理解了这篇文章，他说，如果在长度计算中没有指向xs的指针，那么在计算sum之后，xs内存可能会被释放？

我的困惑是——如果xs已经在内存中了，那么length函数不就是要使用已经占用的内存吗？

我不明白这里的太空泄漏。

Answer 1

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

因为Haskell默认情况下具有惰性求值，所以如果您有一个创建列表的函数，sum可以在没有整个列表的情况下使用它（每次生成函数生成新元素时，它都会被sum消耗，然后释放）。

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

另一方面，mean函数将列表提供给sum和length。因此，在评估sum时，我们需要将列表保存在内存中，以便稍后由length处理。

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

Answer 2

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

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

Answer 3

如果在length计算中没有指向xs的指针，那么在计算sum之后，xs内存本可以被释放？

不，您在这里错过了懒惰评估的重要方面。您说得对，length将使用与sum调用期间分配的内存相同的内存，我们在该内存中扩展了整个列表。

但这里的重点是，为整个列表分配内存应该根本没有必要。如果没有length计算，而只有sum，则内存可以在计算sum期间释放。请注意，列表[1..1000]只有在被消耗时才被延迟生成，因此实际上mean [1..1000]应该在恒定空间中运行。

您可以编写如下函数，以了解如何避免这种空间泄漏：

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

其应当仅遍历CCD_ 27一次。然而，Haskell非常懒惰，只在计算sum时才计算第一个元组组件，而第二个元组组件只在稍后计算len时计算。我们需要使用更多的技巧来强制进行评估：

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

它确实在恒定空间中运行，正如您可以在ghci中使用:set +s确认的那样。

Answer 4

空间泄漏是指整个计算的xs都保存在内存中用于length函数。这是浪费，因为在评估sum之后，我们不会使用列表的实际值，也不需要同时将它们全部存储在内存中，但Haskell并不知道这一点。

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

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

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

length也是如此。它生成的thunks可以立即标记为删除，因为其他任何东西都不可能希望对其进行进一步评估。

编辑：

sum在前奏曲中的实现

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