腾讯云

文章/答案/技术大牛

发布

社区首页 >问答首页 >你怎么知道何时使用折叠左，何时使用折叠-右？

问你怎么知道何时使用折叠左，何时使用折叠-右？
EN

Stack Overflow用户

提问于 2009-09-18 11:22:40

回答 4查看 26.1K关注 0票数 109

我知道，左折叠产生左倾树，右产生右倾树，但当我伸手去折叠时，我有时会陷入头痛的困扰，试图确定哪种折叠是合适的。通常，我最终会解开整个问题，并逐步完成折叠函数的实现，因为它适用于我的问题。

所以我想知道的是：

决定是左折还是右折的经验法则是什么？
考虑到我面临的问题，我如何快速决定使用哪种折叠方式？

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

由于折叠是(函数式)编程中的一个常见动作，我希望能够快速而自信地做出这些决定。所以..。有小费吗？

language-agnostic

functional-programming

fold

回答 4

Stack Overflow用户

回答已采纳

发布于 2009-09-18 11:40:11

您可以将折叠转换为infix运算符表示法(在中间写入)：

此示例使用累加器函数x折叠。

fold x [A, B, C, D]

因此等于

A x B x C x D

现在，您只需对运算符的相联性进行推理(使用括号！)。

如果您有一个left-associative运算符，您将设置如下括号

((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比较普遍.但在其他情况下，infix表示法+括号是非常有用的。

票数 119

Stack Overflow用户

发布于 2009-09-18 12:55:27

奥林·希弗斯用"foldl是基本列表迭代器“和"foldr是基本列表递归运算符”来区别它们。如果你看看foldl是如何工作的：

((1 + 2) + 3) + 4

您可以看到正在构建的累加器(如尾递归迭代)。相反，foldr的收益是：

1 + (2 + (3 + 4))

在其中，您可以看到对基本大小写4的遍历，并从中构建结果。

所以我假设一个经验法则:如果它看起来像一个列表迭代，用尾递归的形式写起来很简单，那么foldl就是最好的选择。

但实际上，从你所使用的操作符的结合性来看，这可能是最明显的。如果他们是左联想，使用折叠。如果它们是正确的联想，使用foldr。

票数 68

Stack Overflow用户

发布于 2009-09-19 13:10:58

其他海报给出了很好的答案，我不会重复他们已经说过的话。正如您在问题中给出的Scala示例，我将给出一个Scala的具体示例。正如戏法已经说过的那样，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中所做的那样。

在像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...