你怎么知道何时使用fold-left以及何时使用fold-right？

Question

我知道fold-left会产生左倾的树木,右倾的树木产生右倾的树木,但是当我伸手去拿折叠时,我有时会发现自己陷入了引发头痛的想法,试图确定哪种折叠是合适的.我通常最终会解决整个问题并逐步执行fold函数,因为它适用于我的问题.

所以我想知道的是:

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

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特定示例.正如Tricks已经说过的,foldRight需要保留n-1堆栈帧,n列表的长度在哪里,这很容易导致堆栈溢出 - 甚至尾递归都不能保存你.

A 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)可以计算每个操作并将累加值向前结转

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

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