foldl如何工作？

Question

有人能解释一下foldl是如何工作的吗？
我知道，例如，foldr(-)0[1,2,3]会产生(1 - (2 - (3 - 0)))，而foldl(-)0[1,2,3]会产生(((0 - 1) - 2) - 3)，但我仍然有一些问题：

• 第一个例子（使用foldr/foldl计算列表长度）：
  foldr(\_ acc -> acc + 1)0[1,2,3,4,5]会得到5，与预期相同。
  foldl(\_ acc -> acc + 1)0[1,2,3,4,5]会得到6。:|
  foldl(\_ acc -> acc + 1)0[2]会得到3。:|
  foldl如何处理这些给定的例子？

• 第二个例子：
  foldr(:)[] [1,2,3,4]会得到[1,2,3,4]，没有问题，但是foldl(:)[] [1,2,3,4]会报错：Occurs check: cannot construct the infinite type: a ~ [a]
  foldl出了什么问题？

- laurentiupiciu

---

对于 foldl，您需要交换 acc 和 _ 的参数顺序，因为 foldr 在逻辑上将初始参数放在序列的末尾，而 foldl 在逻辑上将其放在开头。这意味着累加器是 foldl 折叠函数的第一个（！）参数（对于 foldr 是第二个参数）。由于这个错误，您的累加器在 foldl 中从 1 开始，而不是从 0 开始。如果您将列表更改为 ["a", "b", "c", "d", "e"]，那么您将在 foldl 示例中得到一个很好的类型检查错误。 - MicroVirus

如果您尝试运行foldl (\_ acc -> acc + 1) 0 [0,0,0,0]，也许您就能看到您的错误。 - pdexter

谢谢你，@MicroVirus！ - laurentiupiciu

@MicroVirus 你应该考虑把那个评论变成一个答案！ - jkeuhlen

@pdexter 是的，那可能是我的措辞有点混乱，但我是指“元素”1。我把所有信息都压缩在了一个评论里，所以这并不是一个完整的答案。欢迎大家撰写完整的答案。 - MicroVirus

Answer 1

在foldr中，累加器是您正在折叠的函数的第二个参数，但在foldl中，累加器是第一个参数。如果您仔细查看问题的介绍段落，就可以自己解决这个问题...

“第一个示例”代码是误导性的，因为acc参数（其名称表明它应该是累加器）始终是lambda的第二个参数，而对于foldl来说，它应该是第一个参数。此外，它还会让人感到困惑，因为示例列表元素的类型和值与累加器值的类型和值相同...正如评论所提到的那样，最好使用其他值，最好使用其他类型！

对于“第二个示例”，您会得到一个类型错误，因为参数被交换了（您不能有一个元素为其本身的列表）。要么手动交换参数顺序：

foldl (\xs x -> x:xs)

否则可以使用flip，这是专为此设计的库函数：

foldl (flip (:))

注意，对于foldl的情况，结果应该是一个反转的列表（而不是复制的列表），因为foldl的迭代方向与foldr相反。

- comingstorm