foldl是否比它的严格版本foldl'更可取？

Question

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

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

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

然而，据我所知，foldl'在语义上等价于foldl。将foldl (+) 0 [1..5]求解为头范式需要在某个点上强制使用累加器。如果我们不需要一个头范式，那么我们根本不需要开始计算foldl (+) 0 [1..5]。

是否有任何令人信服的理由使得foldl的行为优于foldl'？

- Joey Adams

Answer 1

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'。

- hammar

Answer 2

当 foldl 和 foldl' 产生不同的结果时，如 hammar 的例子，在决策时必须根据所需的结果做出决定。除此之外，如果折叠函数是构造函数（应用构造函数会创建一个 WHNF 值，强制将其再次转换为 WHNF 没有意义），以及在 foldl (.) id functions 中强制 WHNF 也无济于事，则使用 foldl 而不是 foldl'。除了这些特殊情况，foldl' 是首选方法。

- Daniel Fischer

---

我不相信有任何理由使用foldl (.) id functions而不是foldr (.) id functions。它们在语义上是等价的，只有当前者不是_|_时，后者才允许惰性消耗函数。我错了吗？ - luqui

@luqui：我认为恰恰相反。foldr版本看起来像：(\x acc -> x . acc)，这基本上意味着：首先执行最右边的函数，从而禁止了惰性消耗。我错了吗？ :) - Dan Burton

如果函数可以在不知道它们的参数的情况下开始产生输出，那么foldr允许惰性消耗（考虑foldr (.) id [(string++) | string <- strings]）。现在你提到了它，我也不知道为什么要使用foldl (.) id函数。 - Daniel Fischer

@DanBurton，信息流顺序与按值调用语言可能相反。在你的脑海中，f (g x) 只是先执行 g。实际上，f 有第一次产生信息的机会。考虑 f x = 1:x; g x = g x。 - luqui

@luqui：啊，是的，那很有道理。玩弄这个想法让我提出了一个新问题（https://dev59.com/7msy5IYBdhLWcg3w4x_c）。 - Dan Burton