您如何知道何时使用左折叠和右折叠？

Question

我知道向左折叠会产生左倾树，而向右折叠会产生右倾树，但是当我伸手去寻找折叠时，有时我会发现自己陷入了令人头痛的想法中，试图确定哪种折叠是合适的。我通常最终会展开整个问题，并逐步完成适用于我的问题的折叠函数的实现。

所以我想知道的是：

• 确定向左折叠还是向右折叠的一些经验法则是什么？
• 鉴于我面临的问题，如何快速决定使用哪种类型的折叠？

Scala by Example (PDF) 中有一个使用折叠的示例编写一个名为 flatten 的函数，它将元素列表的列表连接成单个列表。在这种情况下，正确的折叠是正确的选择（考虑到列表的连接方式），但我必须考虑一下才能得出这个结论。

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

Answer 1

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

此示例折叠使用累加器函数 x

fold x [A, B, C, D]

因此等于

A x B x C x D

现在您只需推理运算符的结合性（通过放入括号！ ）。

如果您有一个左关联运算符，您将像这样设置括号。

((A x B) x C) x D

在这里，您使用左折叠。示例（haskell 风格的伪代码）

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

如果您的运算符是右关联的（右折叠），则括号将如下设置：

A x (B x (C x D))

示例：Cons-Operator

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

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

Answer 2

Olin Shivers 通过说“foldl 是基本的列表迭代器”来区分它们”和“foldr 是基本的列表递归运算符。”如果您查看 Foldl 的工作原理：

((1 + 2) + 3) + 4

您可以看到正在构建累加器（如尾递归迭代）。相比之下，foldr 继续：

1 + (2 + (3 + 4))

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

因此，我提出了一条经验法则：如果它看起来像一个列表迭代，并且可以很容易以尾递归形式编写，那么 Foldl 就是最佳选择。

但实际上，这可能从您所使用的运算符的关联性中最为明显。如果它们是左关联的，请使用foldl。如果它们是右关联的，则使用foldr。

Answer 3

其他博主已经给出了很好的答案，我不再重复他们已经说过的内容。正如您在问题中给出的 Scala 示例一样，我将给出一个 Scala 特定示例。正如技巧已经说过的，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...

因此，我的经验法则是 - 对于没有特定关联性的运算符，请始终使用 foldLeft，至少在 Scala 中是这样。否则，请遵循答案中给出的其他建议；）。

Answer 4

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

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

折叠：
(1 + (2 + (3 + 4))) 需要先为 1 + ? 和 2 + ? 打开堆栈帧计算3 + 4，然后需要返回并计算每个。

我不是函数式语言或编译器优化方面的专家，无法判断这是否真的会产生影响，但使用带有交换运算符的 Foldl 看起来确实更干净。