你怎么知道何时使用折叠和何时使用折叠权？

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 

在这里，你使用左折叠。示例（哈斯克尔式的伪代码）

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更广泛。但在其他情况下，中缀记法+圆括号非常有用。

Answer 2

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

与foldl： (((1 + 2) + 3) + 4)可以计算出每一个操作和执行的累加值向前

foldr相似： (1 + (2 + (3 + 4)))需要一个堆栈帧计算之前打开的1 + ?和2 + ?3 + 4，那么它需要返回并为每个计算。

我不是足够的功能语言或编译器优化的专家，说这是否会实际上有所作为，但它确实似乎更清洁使用foldl与交换操作符。

Answer 3

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

((1 + 2) + 3) + 4 

你可以看到蓄电池（如在尾递归迭代）在建。相比之下，foldr相似收益：

1 + (2 + (3 + 4)) 

在这里你可以看到遍历的基本情况4，建立了从那里的结果。

所以我提出了一条经验法则：如果它看起来像一个列表迭代，那么可以简单地用尾递归形式来编写，foldl就是要走的路。

但实际上，这可能是最明显的从您正在使用的操作符的关联性。如果他们是左联合的，请使用foldl。如果它们是正确关联的，请使用foldr。

Answer 4

其他海报已经给出了很好的答案，我不会重复他们已经说过的话。正如你在你的问题中给出了一个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) 

可迭代计算，如在implementation of List完成。

在一个严格评估的语言斯卡拉，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，至少在斯卡拉运营商。否则，请与答案中给出的其他建议;）。