106

我知道向左折叠会产生向左倾斜的树，向右折叠会产生向右倾斜的树，但是当我伸手去折叠时，我有时会发现自己陷入了令人头痛的想法，试图确定哪种折叠是合适的。我通常最终会展开整个问题并逐步执行折叠功能，因为它适用于我的问题。

所以我想知道的是：

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

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

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

4

4 回答 4

114

您可以将折叠转换为中缀运算符符号（写在两者之间）：

此示例使用累加器功能折叠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))

示例：缺点运算符

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

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

于 2009-09-18T19:40:11.747 回答
66

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

((1 + 2) + 3) + 4

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

1 + (2 + (3 + 4))

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

所以我提出了一个经验法则：如果它看起来像一个列表迭代，一个很容易以尾递归形式编写的，foldl 就是要走的路。

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

于 2009-09-18T20:55:27.493 回答
29

其他海报已经给出了很好的答案，我不会重复他们已经说过的话。正如您在问题中给出了一个 Scala 示例，我将给出一个 Scala 特定示例。正如Tricks已经说过的那样，foldRight需要保留n-1堆栈帧，n列表的长度在哪里，这很容易导致堆栈溢出 - 甚至尾递归也不能让你摆脱这种情况。

AList(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 这样严格评估的语言中，afoldRight可以轻松地将堆栈用于大型列表，而 afoldLeft不会。

例子：

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 中是这样。否则，请参考答案中给出的其他建议；）。

于 2009-09-19T21:10:58.627 回答
4

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

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

foldr： (1 + (2 + (3 + 4)))需要在计算之前打开一个堆栈帧，1 + ?然后它需要返回并为每个进行计算。2 + ?3 + 4

对于函数式语言或编译器优化方面的专家，我还不足以说这是否真的会有所作为，但使用带有可交换运算符的 foldl 肯定看起来更干净。

于 2009-09-18T20:20:05.957 回答