22

Haskell 有两个用于列表的左折叠函数：foldl和一个“严格”版本，foldl'. 非严格的问题foldl在于它构建了一个 thunk 塔：

    foldl (+) 0 [1..5]
--> ((((0 + 1) + 2) + 3) + 4) + 5
--> 15

这会浪费内存，如果列表中的项目太多，可能会导致堆栈溢出。 foldl'，另一方面，在每个项目上强制累加器。

但是，据我所知，foldl'在语义上等同于foldl. 评估foldl (+) 0 [1..5]头部正常形式需要在某个点强制累加器。如果我们不需要一个 head-normal 形式，我们就不会foldl (+) 0 [1..5]开始评估。

是否有任何令人信服的理由想要 的 行为foldl超过 的foldl'？

4

2 回答 2

26

foldl并且foldl'在语义上不等价。微不足道的反例：

Prelude Data.List> foldl (\x y -> y) 0 [undefined, 1]
1
Prelude Data.List> foldl' (\x y -> y) 0 [undefined, 1]
*** Exception: Prelude.undefined

foldl'但是，在实践中，由于您提到的原因，您通常需要严格。

于 2011-11-23T00:37:37.573 回答
14

什么时候foldl和foldl'不会产生相同的结果，就像在哈马尔的例子中一样，必须根据期望的结果做出决定。除此之外，您将使用foldl而不是foldl'折叠函数是构造函数（应用构造函数在 WHNF 中创建一个值，再次将其强制为 WHNF 是没有意义的），并且在foldl (.) id functions强制 WHNF 不会获得任何东西的情况下。除了这些例外情况，foldl'是选择的方法。

于 2011-11-23T00:46:50.130 回答