Haskell 的严格折叠真的使用线性 space 吗？

Question

我以为我了解 Haskell 中的折叠性能基础知识，如 foldr, foldl, foldl' on the Haskell Wiki 和许多其他地方所述。特别是，我了解到对于累加函数，应该使用 foldl'，以避免 space 泄漏，并且编写标准库函数时考虑到了这一点。所以我假设像 length 这样的简单累加器应用于像 replicate n 1 这样的简单列表时，应该要求列表的长度保持不变 space （或至少是次线性的）。我的直觉是，在足够简单的列表上，它们的行为大致类似于命令式语言中的 for 循环。

但是今天我发现这在实践中似乎并不成立。例如，length $ replicate n 1 似乎在 n 中使用 space 线性。 在 ghci:

中

ghci> :set +s
ghci> length $ replicate (10^6) 1
1000000
(0.02 secs, 56,077,464 bytes)
ghci> length $ replicate (10^7) 1
10000000
(0.08 secs, 560,078,360 bytes)
ghci> length $ replicate (10^8) 1
100000000
(0.61 secs, 5,600,079,312 bytes)
ghci> length $ replicate (10^9) 1
1000000000
(5.88 secs, 56,000,080,192 bytes)

简单地说，我的问题是：length 和其他严格折叠真的使用线性 space 吗？如果是这样，为什么？它是不可避免的吗？ 下面是我如何尝试理解这一点的更多细节，但它们可能不值得一读——tl;dr 是线性-space 用法似乎坚持我尝试的任何变化。

（我最初使用 sum 作为示例函数。正如 Willem Van Onsem 指出的那样，这是一个错误选择的示例，因为默认实例实际上并不严格。但是，主要问题仍然存在，因为如下所述，许多其他真正基于严格折叠的函数都会发生这种情况。）

用 foldl' (\n _ -> n+1) 0 替换 length 似乎会使性能变差一个常数； space 使用似乎仍然是线性的。
用 foldl 和 foldr 定义的版本内存使用率较差（正如预期的那样），但只是一个很小的常数因子，而不是渐近变差（正如大多数讨论似乎暗示的那样）。
将 length 替换为 sum、last 或其他简单的累加器，或者使用 foldl' 的明显定义，似乎也没有改变线性 space 用法。
使用 [1..n] 作为测试列表，以及其他类似的变体，似乎也没有显着差异。
在 Data.Foldable 的 sum、foldl' 等通用版本、Data.List 中的专用版本和通过模式匹配直接定义的本地版本之间切换, 似乎也没什么区别。
编译而不是在 ghci 中工作似乎也只提高了 space 使用率一个常数。
在 GHC 的几个最新版本（8.8.4、8.10.5 和 9.0.1）之间切换似乎也没有显着差异。

Answer 1

Replacing sum with foldl' (+) 0 here, then performance improves noticeably in both time and space (which is itself a surprise; shouldn’t the standard sum be at least as efficient?) — but only by a constant factor; space usage still seems to be linear.

总和为implemented as [src]:

sum :: Num a => t a -> a
sum = getSum #. foldMap Sum

因此它利用了 Sum data type 及其 Monoid 实例，因此 mappend = (+) 和 mempty = 0。 foldMap 正确结合，确实：

Map each element of the structure into a monoid, and combine the results with (<>). This fold is right-associative and lazy in the accumulator. For strict left-associative folds consider foldMap' instead.

foldMap 因此 implemented with foldr [src]:

foldMap :: Monoid m => (a -> m) -> t a -> m
{-# INLINE foldMap #-}
-- This INLINE allows more list functions to fuse.  See #9848.
foldMap f = foldr (mappend . f) mempty

虽然 foldl' 确实会占用（小得多）内存，并且可能更高效，但使用 foldr 的一个原因是 Peano numbers 例如，可以利用惰性，因此头部范式看起来像 S(…) 其中 … 可能还没有被评估（还）。

foldr 也可以提前终止。例如，如果你对某个代数结构求和，我们可以提前终止循环。

Answer 2

“Do they use linear space”是一个不太明确的问题。通常当我们谈论算法使用的 space 时，我们谈论的是它的工作集：它同时需要的最大内存量。 “如果我的电脑只有 X 字节的内存，我可以运行这个程序吗？”但这不是 GHCI :set +s 的衡量标准。它测量所有内存分配的总和，包括中途清理的内存分配。在你的实验中最大的内存使用是什么？当然是列表本身。

所以您实际上只是测量了大小为 N 的列表占用的字节数。您可以使用 last 而不是 length 来确认这一点，我希望您同意分配没有中间结果，并且是严格的。它使用您的指标占用与 length 相同的内存量 - length 不会为总和分配额外的内存。

但更大的问题是 GHCI 不是优化编译器。如果您完全关心性能特征，GHCI 是错误的工具。相反，使用带有 -O2 的 GHC，并打开 GHC 的分析器。

import System.Environment (getArgs)

main = do
  n <- read . head <$> getArgs
  print $ length (replicate (10^n) 1)

并且运行宁它：

$ ghc -O2 -prof -fprof-auto Whosebug.hs
$ ./Whosebug 6 +RTS -p
1000000
$ grep "total alloc" Whosebug.prof
    total alloc =      54,856 bytes  (excludes profiling overheads)
$ ./Whosebug 9 +RTS -p
1000000000
$ grep "total alloc" Whosebug.prof
    total alloc =      55,008 bytes  (excludes profiling overheads)

我们可以看到，尽管输入大小增加了一千倍，space 使用率大致保持不变。

Will Ness 正确地指出 -s 是比 -p 更好的测量工具。

Haskell 的严格折叠真的使用线性 space 吗？

Do Haskell’s strict folds really use linear space?

memory

performance

haskell

lazy-evaluation

fold