你怎么知道什么时候使用折叠和什么时候使用折叠的权利？
我知道折叠产生左倾的树木，右折产生右倾的树木，但是当我到达折叠的时候，有时我发现自己陷入头痛的思考，试图确定哪种褶皱是合适的。 我通常最终解开整个问题，并逐步实现fold函数，因为它适用于我的问题。
所以我想知道的是：
- 确定是折叠还是折叠，有哪些经验法则？
- 鉴于我面临的问题，如何快速决定使用哪种types的折叠？
在Scala中有一个例子（PDF）使用fold来写一个叫做flatten的函数，它将元素列表连接成一个列表。 在这种情况下，正确的select是正确的select（考虑到列表的连接方式），但是我必须考虑一下才能得出结论。
由于折叠在（function）编程中是一种常见的行为，所以我希望能够迅速而自信地作出这种决定。 那么…任何提示？
您可以将折叠转换为中缀运算符表示法（在中间写入）：
这个例子使用累加器函数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更为广泛。 但在其他情况下，中缀记法+括号是非常有用的。
Olin Shivers通过说“foldl是基本列表迭代器”和“foldr是基本列表recursion运算符”来区分它们。 如果你看看foldl的工作原理：
((1 + 2) + 3) + 4
您可以看到正在构build的累加器（如在尾recursion迭代中）。 相反，foldr继续：
1 + (2 + (3 + 4))
在那里你可以看到遍历基本情况4并从那里build立结果。
所以我提出一个经验法则：如果它看起来像一个列表迭代，一个简单的写尾recursionforms，foldl是要走的路。
但实际上，这可能是最明显的从你正在使用的操作员的结合性。 如果他们是左联合的，使用foldl。 如果他们是正确的联合，使用foldr。
其他海报已经给出了很好的答案，我不会重复他们已经说过的话。 正如你在你的问题中给出了一个Scala例子，我将给出一个Scala特定的例子。 正如技巧已经说过的， foldRight需要保留n-1堆栈帧，其中n是列表的长度，这很容易导致堆栈溢出 – 甚至连尾部recursion都不能解决这个问题。
List(1,2,3).foldRight(0)(_ + _)将减less到：
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)(_ + _)会减less到：
(((0 + 1) + 2) + 3)
这可以迭代计算，就像在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...
因此，我的经验法则是，对于没有特定关联性的操作符，至less在Scala中总是使用foldLeft 。 否则，请与答案中给出的其他build议;）。
这也是值得注意的（我意识到这是明显的一点），在交换运算符的情况下，两者几乎是等价的。 在这种情况下，foldl可能是更好的select：
foldl： (((1 + 2) + 3) + 4)可以计算每个操作并将累积值向前运送
foldr： (1 + (2 + (3 + 4)))需要一个堆栈帧打开1 + ? 和2 + ? 在计算3 + 4之前，需要回去做各自的计算。
我不是足够的function语言或编译器优化的专家来说这是否会实际上有所作为，但它肯定似乎更清洁使用foldl与交换操作符。
