Haskell- foldl和foldr是什么？

Question

foldl和foldr的区别只是循环方向吗？我认为它们所做的事情不仅仅是在不同方向上循环有区别吧？

- Lethi

---

我很好奇你读了什么让你感到困惑。如果有一个链接的话，问题可能会更清晰明了。不过看起来@AndrewC已经为你提供了一个高质量的答案。 - Jamey Sharp

您也可以在此处找到一个非常好的答案 https://dev59.com/RHA75IYBdhLWcg3w0st- - Jerome

它们的区别在于它们的参数顺序被分别翻转了：适用于foldl的函数将结果与列表元素类型组合，而适用于foldr的函数将列表元素类型与结果组合。 - Will Ness

@WillNess __一个__不同之处是累加函数的类型已经颠倒了。foldr f不一定要是 foldl (flip f)。 - AndrewC

@AndrewC 谢谢，没错，就是这个意思。 - Will Ness

Answer 1

如果您的函数不是可结合的（即，括号表达式的顺序很重要），那就有所不同，例如，
foldr (-) 0 [1..10] = -5 但是 foldl (-) 0 [1..10] = -55。
这是因为前者等于 1-(2-(3-(4-(5-(6-(7-(8-(9-(10 - 0)))))))))，而后者是 (((((((((0-1)-2)-3)-4)-5)-6)-7)-8)-9)-10。

然而，因为(+)是可结合的（无论以哪种顺序添加子表达式都无所谓），
foldr (+) 0 [1..10] = 55 并且 foldl (+) 0 [1..10] = 55。 (++)是另一个可结合的操作，因为 xs ++ (ys ++ zs)的答案与 (xs ++ ys) ++ zs相同（尽管第一个更快 - 不要使用 foldl (++)）。

一些函数只能按一种方式工作：
foldr (:) :: [a] -> [a] -> [a] ，但 foldl (:) 则没有意义。

看看 Cale Gibbard 的图示（来自 维基百科文章）；您可以看到f使用真正不同的数据对进行调用：

另一个区别是，由于它匹配列表的结构，因此foldr通常更适合惰性求值，因此可以与无限列表一起使用，只要f在第二个参数中是非严格的（例如(:)或(++)）。 foldl很少是更好的选择。如果您正在使用foldl，通常值得使用foldl'，因为它是严格的并防止生成大量的中间结果。（有关此主题的更多信息，请参见此问题的答案。）

- AndrewC

---

与最后一点相关的另一个不同之处是，如果给定了无限列表，foldl永远无法返回结果，而foldr则可以（如果给定了第二个参数中非严格的函数，比如（：）或 const，...）。 - luqui

与foldr相比，foldl的参数顺序被颠倒。因此所有函数都可以双向工作：foldl (flip (:))仍然可以通过类型检查。 - nponeccop

一些附注：[1] 另一种谈论它的方式是提到 (:) :: a->[a]->[a] 或 flip (:) :: [a]->a->[a] 的 不对称性，这决定了唯一可能的组合顺序。[2] scanl 介于 foldl 和 foldr 之间，将“从左侧循环”与尽早停止的可能性相结合。 - Will Ness

不仅仅是语法上的差异，语义上也存在差别：foldr (:) "!" "Hello" 的结果为 "Hello!"，而 foldl (flip (:)) "!" "Hello" 的结果为 "olleH!"。 - AndrewC

@laiboonh，“第一个”应用数学上可能是如此，但如果组合函数在其第二个参数（如“：”）中是惰性的，则它可以使用第一个参数产生结果，然后使用其（懒惰生成的）第二个参数的“部分”来产生更多结果。 - AndrewC