haskell - 为什么 sum 在 haskell 中比 foldl' 慢？

Question

怎么默认sum在 ghc 中比它的 foldl' 慢约 10 倍(foldl 的 stricter equivalent )等效？如果是这样，为什么不使用 foldl' 来实现？ ?

import Data.List
> foldl' (+) 0 [1..10^7]
50000005000000
(0.39 secs, 963,528,816 bytes)

> sum [1..10^7]
50000005000000
(4.13 secs, 1,695,569,176 bytes)

为了完整起见，这里还有 foldl 的统计数据和 foldr .

> foldl (+) 0 [1..10^7]
50000005000000
(4.02 secs, 1,695,828,752 bytes)

> foldr (+) 0 [1..10^7]
50000005000000
(3.78 secs, 1,698,386,648 bytes)

看起来像 sum使用 foldl 实现因为它们的运行时间是相似的。在 ghc 7.10.2 上测试。

Answer 1

sum函数使用 foldl 实现在 GHC 中:

-- | The 'sum' function computes the sum of a finite list of numbers.
sum                     :: (Num a) => [a] -> a
{-# INLINE sum #-}
sum                     =  foldl (+) 0

可以看到 in the source .

必须这样，因为它是规范 in the Haskell report .

理由很可能是对于列表的某些惰性元素类型， foldl是正确的做法。 (我个人认为 foldl 几乎总是错误的，应该只使用 foldl'。)

通过充分优化，GHC 将内联该定义，将其专门化为手头的元素类型，注意循环是严格的，并在每次迭代中强制评估累加器；有效地将其变成 foldl' ，正如@AndrásKovács 所观察到的。

从 GHC-7.10 开始， sum itself是 Foldable 的一种方法类型类，默认定义通过 foldMap . instance Foldable []但是用上面的 sum 的定义覆盖它.