performance - 为什么这段代码不是常数空间？

Question

我目前正在学习 Haskell(作为一名程序员，但这是我第一次尝试函数式语言)。

我想编写一个扫描列表并返回该列表的最小和最大元素的函数。前奏曲的功能minimum和 maximum做，但两者同时。我想出了以下代码:

import Data.List

-- Declaration of rand

minMax :: [Int] -> Maybe (Int, Int)
minMax []   = Nothing
minMax (x:xs) = Just (foldl' f (x, x) xs)
                where
                  f (a, b) c = (if c < a then c else a, if c > b then c else b)

rand是一个生成无限数字列表的函数。
问题是当我附加以下 main功能:

main = print $ minMax $ take 1000000 $ rand 7666532

使用分析编译和运行所有这些，它向我显示它使用了超过 200 MB 的内存，所以它绝对不是一个常量空间函数(我希望它是)。

问题是为什么以及我应该改变什么来解决它。据我了解 foldl'从左侧折叠列表(与其生成方式相同)并且不懒惰，所以我不明白为什么内存使用率如此之高。我很确定是 minMax不正确的功能，如简单地打印所述列表，使用

main = print $ take 1000000 $ rand 7666532

给我 1MB 的使用量，这是我理解和期望的。

Answer 1

请注意 foldl'强制蓄能器为弱头正常形式。由于累加器是一个元组，它确实 不是 强制评估元组的两个元素。

如果你明确地强制这两个元素，你会得到一个常数空间函数:

f (a, b) c = a `seq` b `seq` (if c < a then c else a, if c > b then c else b)

在您的原始程序中，您正在构建一个元组: (<thunk>, <thunk>)每次 f应用时，您只需构建一个具有越来越大的 thunk 的元组。当最终被 print 消耗时调用 show强制对元组进行全面评估，并在该点进行所有比较。

使用 seq你改为强制 f评估当时的比较，因此在执行比较之前评估包含在累加器中的 thunk。因此，结果是存储在累加器中的 thunk 具有恒定大小。

什么 foldl'只是避免构建thunk: f (f (f ...) y) x .

正如 Jubobs 建议的那样，一种替代解决方案可以避免显式使用 seq是使用具有严格字段的​​数据类型:

data Pair a b = Pair !a !b
    deriving Show

因此代码将变为:

minMax :: [Int] -> Maybe (Pair Int Int)
minMax []   = Nothing
minMax (x:xs) = Just (foldl' f (Pair x x) xs)
                where
                  f (Pair a b) c = Pair (if c < a then c else a) (if c > b then c else b)

这完全避免了重击。