你怎么知道何时使用折左时使用折-对不对？

Question

我知道倍左产生的左倾的树木和折叠的权利产生右翼树，但是当我到达一倍，有时我发现自己陷入痛诱导思想尝试确定这种折是适当的。我通常展开的整个问题和逐步通过执行《倍功能，因为它适用于我的问题。

所以我想知道的是：

• 什么是一些规则用于确定是否倍左或折吗？
• 我怎么可以迅速决定哪种类型的折使用的给予问题，我们面临的?

有一个例子 斯的例子 (PDF)使用一个折写一功能的所谓平平，它连接一个清单元列入一个单一的名单。在这种情况下，一个正确的折是正确的选择(给出的方式列出联)，但我不得不认为关于这一点，以抵达这一结论。

由于折是这样一个共同的行动(功能性的)编程，我希望能够让这些类型的决定迅速和自信。所以...什么建议吗？

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-操

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

在一般情况下，算术运营商(大多数运营商)是左关联的，所以 foldl 更普遍。但在其他情况下，中缀符号+括号内是很有用的。

Answer 2

奥林不寒而栗 有区别他们说"foldl是基本的迭代表"和"foldr是基本的清单递归经营者。" 如果你看看如何foldl工作：

((1 + 2) + 3) + 4

你可以看到蓄(如在一个尾递归的迭代)正在建设之中。与此相反，foldr进行：

1 + (2 + (3 + 4))

在这里你可以看到遍历的基本情况下4和建立的结果。

所以我假定一个法则:如果它看起来像一个列表迭代，一个简单的要写在结尾递归的形式，foldl是的路要走。

但是真的，这可能是最明显的关联性的经营者所使用。如果他们是左结合，使用foldl.如果他们是正确的关联，使用foldr.

Answer 3

其他的海报已经给予很好的答案而且我不会重复他们已经说。因为你已经给了卡拉的例子，在你的问题，我给一个斯卡拉的具体例子。作为 技巧 已经说了， 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.

在一个严格的评估，语言作为拉斯卡拉， 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, 至少在卡拉.否则，与其他建议中给出的答案；).

Answer 4

这也是值得注意(并且我知道这是陈述显而易见的一点)，在这种情况下的交换操作员的两个几乎是等同的。在这种情况的一个foldl可能是更好的选择：

foldl:(((1 + 2) + 3) + 4) 可以计算每个动作和进行的积累价值的前进

foldr:(1 + (2 + (3 + 4))) 需要一堆的框架可以打开 1 + ? 和 2 + ? 在计算 3 + 4, 然后它需要回去做的计算为每个。

我没有足够的专家功能性的语言或编译器优化来说这是否是实际上将使一个差异，但它当然似乎更清洁的使用foldl有可交换的运营商。