你如何知道何时使用fold-left和何时使用fold-right？

Question

我知道fold-left会生成左倾树，而fold-right会生成右倾树，但是当我需要使用fold时，有时会陷入令人头痛的思考中，试图确定哪种类型的fold是合适的。通常情况下，我会将整个问题解开，并逐步通过fold函数的实现来解决我的问题。

因此，我想知道：

- 有哪些经验法则可以确定何时使用fold-left或fold-right？ - 如何快速决定在面临的问题中使用哪种类型的fold？

在Scala by Example（PDF）中有一个例子，使用fold编写了一个名为flatten的函数，该函数将元素列表的列表连接成单个列表。在这种情况下，正确的选择是右折叠（考虑到列表的连接方式），但我不得不稍微思考一下才能得出这个结论。

由于折叠在（函数式）编程中是如此常见的操作，所以我希望能够快速自信地做出这些决策。那么...有什么建议吗？

- Jeff

---

类似于 https://dev59.com/g3RC5IYBdhLWcg3wMd5S - Steven Huwig

这个问题比那个更普遍，那个问题是关于Haskell的。惰性计算对问题的答案有很大影响。 - Chris Conway

哦。奇怪，我以为这个问题有Haskell标签，但看来不是... - ephemient

Answer 1

你可以将fold转换为中缀运算符表示法（写在中间）：

这个例子使用累加器函数x来进行折叠。

fold x [A, B, C, D]

因此等于

A x B x C x D

现在，您只需要考虑您的运算符的结合性（通过添加括号！）。

如果您有一个左关联的运算符，则应设置括号如下：

((A x B) x C) x D

这里使用了左折叠（left fold）。举个例子（哈斯克尔风格的伪代码）：

foldl (-) [1, 2, 3] == (1 - 2) - 3 == 1 - 2 - 3 // - is left-associative

如果您的运算符是右结合的（右折叠），则括号应该设置如下：

A x (B x (C x D))

例子：Cons运算符

foldr (:) [] [1, 2, 3] == 1 : (2 : (3 : [])) == 1 : 2 : 3 : [] == [1, 2, 3]

一般来说，算术运算符（大多数运算符）是左结合的，因此 foldl 更为普遍。但在其他情况下，使用中缀表示法 + 括号非常有用。

- Dario

---

你描述的其实是 Haskell 中的 foldl1 和 foldr1（foldl 和 foldr 需要提供一个初始值），而 Haskell 中的“cons”被称为 (:) 而不是 (::)，除此之外你的描述是正确的。你可能需要补充说明，Haskell 还提供了 foldl'/foldl1'，它们是 foldl/foldl1 的严格版本，因为懒惰算术并不总是可取的。 - ephemient

抱歉，我之前以为这个问题有“Haskell”标签，但实际上没有。如果不是关于 Haskell 的话，我的评论其实并没有太大意义... - ephemient

@ephemient，你看到了。这是“Haskell风格的伪代码”。 :) - laughing_man

我所见过的关于fold之间差异的最佳答案。 - AleXoundOS

Answer 2

Olin Shivers认为“foldl是基本的列表迭代器”，而“foldr是基本的列表递归运算符”。如果你看一下foldl的工作方式:

((1 + 2) + 3) + 4

你可以看到累加器（类似于尾递归迭代）被构建。相比之下，foldr的处理方式是：

1 + (2 + (3 + 4))

您可以看到遍历到基本情况4并从那里构建结果。

因此，我提出一个经验法则：如果它看起来像列表迭代，而且在尾递归形式中编写起来很简单，那么foldl就是最好的选择。

但实际上，这可能最明显的表现是您使用的运算符的结合性。如果它们是左结合的，请使用foldl。如果它们是右结合的，则使用foldr。

- Steven Huwig

Answer 3

其他回答者已经给出了很好的答案，我不会重复他们已经说过的内容。由于您在问题中提供了一个Scala示例，我将给出一个特定于Scala的示例。正如Tricks已经说过的那样，foldRight需要保留n-1个堆栈帧，其中n是您的列表长度，这很容易导致堆栈溢出 - 即使尾递归也无法拯救您。
List(1,2,3).foldRight(0)(_ + _)将简化为：

1 + List(2,3).foldRight(0)(_ + _)        // first stack frame
    2 + List(3).foldRight(0)(_ + _)      // second stack frame
        3 + 0                            // third stack frame 
// (I don't remember if the JVM allocates space 
// on the stack for the third frame as well)

当 List(1,2,3).foldLeft(0)(_ + _) 被归约时，其结果为:

(((0 + 1) + 2) + 3)

可以像在List的实现中一样进行迭代计算。

在Scala这样的严格求值语言中，对于大型列表，foldRight很容易导致堆栈溢出，而foldLeft不会。

示例：

scala> List.range(1, 10000).foldLeft(0)(_ + _)
res1: Int = 49995000

scala> List.range(1, 10000).foldRight(0)(_ + _)
java.lang.StackOverflowError
        at scala.List.foldRight(List.scala:1081)
        at scala.List.foldRight(List.scala:1081)
        at scala.List.foldRight(List.scala:1081)
        at scala.List.foldRight(List.scala:1081)
        at scala.List.foldRight(List.scala:1081)
        at scala.List.foldRight(List.scala:1081)
        at scala.List.foldRight(List.scala:1081)
        at scala.List.foldRight(List.scala:1081)
        at scala.List.foldRig...

因此，我的经验法则是 - 对于没有特定结合性的运算符，在Scala中始终使用foldLeft。否则，请按答案中给出的其他建议进行操作 ;).

- Flaviu Cipcigan

---

这是以前的情况，但在当前版本的Scala中，foldRight已经被更改为在列表的反向副本上应用foldLeft。例如，在2.10.3中，https://github.com/scala/scala/blob/v2.10.3/src/library/scala/collection/immutable/List.scala#L305。看起来这个改变是在2013年初期实施的 - https://github.com/scala/scala/commit/6db4db93a7d976f1a3b99f8f1bffff23a1ae3924。 - Dhruv Kapoor

Answer 4

值得注意的是（我意识到这有点显而易见），在交换运算符的情况下，两者几乎是等价的。在这种情况下，foldl可能是更好的选择：

foldl: (((1 + 2) + 3) + 4) 可以计算每个操作并将累加值向前传递

foldr: (1 + (2 + (3 + 4))) 需要打开一个堆栈帧来计算 1 + ? 和 2 + ?，然后它需要返回并为每个计算执行计算。

我不是函数语言或编译器优化方面的专家，无法确定这是否会产生影响，但使用具有可交换性的运算符时，使用foldl似乎更清洁。

- Tricks

---

额外的堆栈帧对于大型列表肯定会产生影响。如果您的堆栈帧超过处理器缓存的大小，则缓存未命中将影响性能。除非列表是双向链接的，否则很难使foldr成为尾递归函数，因此除非有理由不使用，否则应该使用foldl。 - A. Levy

Haskell的懒惰特性使得这种分析变得模糊不清。如果被折叠的函数在第二个参数上不是严格的，那么foldr很可能比foldl更有效率，并且不需要任何额外的堆栈帧。 - ephemient

抱歉，我以为这个问题有“Haskell”标签，但实际上没有。如果不是关于Haskell的话，我的评论就没有太多意义了... - ephemient