scala foldLeft 与 foldRight - 有关系吗？

foldLeft v. foldRight - does it matter?

提问by Kevin Meredith

Previously, Nicolas Rinaudoanswered my question on Scala's List foldRight Always Using foldLeft?

之前，Nicolas Rinaudo在 Scala 的List foldRight Always Using foldLeft?上回答了我的问题。

Studying Haskell currently, my understanding is that foldRightshould be preferred over foldLeftin cases where ::(prepend) can be used over ++(append).

目前正在学习 Haskell，我的理解是，在(prepend) 可以用于(append) 的情况下，foldRight应该优先考虑。foldLeft::++

The reason, as I understand, is performance - the former occurs in O(1), i.e. add an item to the front - constant time. Whereas the latter requires O(N), i.e. go through the whole list and add an item.

据我了解，原因是性能 - 前者发生在O(1)，即在前面添加一个项目 - 恒定时间。而后者需要O(N)，即遍历整个列表并添加一个项目。

In Scala, given that foldLeftis implemented in terms of foldRight, does the benefit of using :+over ++with foldRighteven matter since foldRightgets reversed, and then foldLeft'd?

在Scala中，因为foldLeft是在以下方面实现的foldRight，不使用的好处:+在++与foldRight连问题，因为foldRight得到扭转，然后foldLeft'd？

As an example, consider this simple fold..operation for simply returning a list's elements in order.

例如，考虑这个简单fold..的按顺序返回列表元素的简单操作。

foldLeftfolds over each element, adding each item to the list via :+.

foldLeft折叠每个元素，通过 将每个项目添加到列表中:+。

scala> List("foo", "bar").foldLeft(List[String]()) { 
                                                    (acc, elem) => acc :+ elem }
res9: List[String] = List(foo, bar)

foldRightperforms a foldLeft with ::operator on each item, but then reverses.

foldRight::对每个项目使用运算符执行 foldLeft ，然后反转。

scala> List("foo", "bar").foldRight(List[String]()) { 
                                                    (elem, acc) => elem :: acc }
res10: List[String] = List(foo, bar)

In reality, does it matter in Scala which foldLeftor foldRightto use given that foldRightuses foldRight?

在现实中，它在斯卡拉无论哪个foldLeft或foldRight要使用鉴于foldRight用途foldRight？

回答by sjrd

@Rein Henrichs' answer is indeed irrelevant to Scala, because Scala's implementation of foldLeftand foldRightis completely different (for starters, Scala has eager evaluation).

@Rein Henrichs 的回答确实与 Scala 无关，因为 Scala 的foldLeft和实现foldRight完全不同（对于初学者来说，Scala 有急切的评估）。

foldLeftand foldRightthemselves have actually very little to do wrt the performance of your program. Both are (liberally speaking) O(n*c_f) where c_f is the complexity of one call to the function fthat is given. foldRightis slower by a constant factor because of the additional reverse, though.

foldLeft并且foldRight他们自己实际上与您的程序的性能几乎没有关系。两者都是（通俗地说） O(n*c_f) 其中 c_f 是对f给定函数的一次调用的复杂性。但是foldRight，由于额外的reverse，速度慢了一个常数因子。

So the real factor that differentiates one from the other is the complexity of the anonymous function that you give. Sometimes, it is easier to write an efficient function designed to work with foldLeft, and sometimes to foldRight. In your example, the foldRightversion is best, because the anonymous function that you give to foldRightis O(1). In contrast, the anonymous function that you give to foldLeftis O(n) itself (amortized, which is what matters here), because acckeeps growing from 0 to n-1, and appending to a list of n elements is O(n).

因此，区分一个与另一个的真正因素是您提供的匿名函数的复杂性。有时，编写一个设计用于使用的高效函数更容易，有时更容易编写foldLeft用于foldRight. 在您的示例中，foldRight版本是最好的，因为您提供的匿名函数foldRight是 O(1)。相比之下，您提供的匿名函数foldLeft本身是 O(n)（摊销，这在这里很重要），因为acc不断从 0 增长到 n-1，并且追加到 n 个元素的列表是 O(n)。

So it actually matterswhether you choose foldLeftor foldRight, but not because of these functions themselves, but because of the anonymous functions given to them. If both are equivalent, choose foldLeftby default.

因此，选择或确实很重要，但不是因为这些函数本身，而是因为赋予它们的匿名函数。如果两者相等，则默认选择。foldLeftfoldRightfoldLeft

回答by Rein Henrichs

I can provide an answer for Haskell, but I doubt it will be relevant to Scala:

我可以为 Haskell 提供一个答案，但我怀疑它是否与 Scala 相关：

Let's start with the source for both,

让我们从两者的来源开始，

foldl f z []     = z
foldl f z (x:xs) = foldl f (f z x) xs

foldr f z []     = z
foldr f z (x:xs) = f x (foldr f z xs)

Now, let's look at where the recursive call to foldl or foldr appears on the right hand side. For foldl, it is outermost. For foldr, it is inside the application of f. This has a couple important implications:

现在，让我们看看对 foldl 或 foldr 的递归调用出现在右侧的位置。对于 foldl，它是最外面的。对于foldr，在f的应用里面。这有几个重要的含义：

1. If fis a data constructor, that data constructor will be left-most, outermost with foldr. This means that foldr implements guarded recursion, such that the following is possible:

   > take 5 . foldr (:) [] $ [1..]
   [1,2,3,4]
   

   This means that, e.g., foldr can be both a good producer and a good consumer for short-cut fusion. (Yes, foldr (:) []is an identity morphism for lists.)

   This is not possible with foldl because the constructor will be inside the recursive call to foldl and cannot be pattern matched.

2. Conversely, because the recursive call to foldl is in left-most, outermost position, it will be reduced by lazy evaluation and will not take up space on the pattern-matching stack. Combined with proper strictness annotation (e.g., foldl'), this allows functions like sumor lengthto run in constant space.

1. 如果f是数据构造函数，则该数据构造函数将位于最左侧，最外层带有 foldr。这意味着 foldr 实现了受保护的递归，因此以下是可能的：

   > take 5 . foldr (:) [] $ [1..]
   [1,2,3,4]
   

   这意味着，例如，foldr 可以是捷径融合的良好生产者和良好消费者。（是的，foldr (:) []是列表的恒等态射。）

   这对于 foldl 是不可能的，因为构造函数将在对 foldl 的递归调用中并且无法进行模式匹配。

2. 相反，由于对 foldl 的递归调用位于最左边、最外面的位置，因此会被惰性求值减少，并且不会占用模式匹配堆栈上的空间。结合适当的严格注释（例如，foldl'），这允许像sum或这样的函数length在恒定空间中运行。

For more on this, see Lazy Evaluation of Haskell.

有关更多信息，请参阅Haskell 的延迟评估。

回答by Nicolas Rinaudo

It does in fact matter whether you use foldLeftor foldRightin Scala, at least with lists, at least in the default implementation. I believe this answer not to hold true for libraries such as scalaz, though.

事实上，无论是在 Scala 中使用foldLeft还是foldRight在 Scala 中，至少对于列表，至少在默认实现中都是重要的。不过，我相信这个答案不适用于 scalaz 等图书馆。

If you look at the source code of foldLeftand foldRightfor LinearSeqOptimized, you'll see that:

如果你看看源代码foldLeft，并foldRight为LinearSeqOptimized，你会看到：

• foldLeftis implemented with a loop and local mutable variables, and fits in one stack frame.
• foldRightis recursive, but not tail recursive, and thus consumes one stack frame per element in the list.

• foldLeft用循环和局部可变变量实现，并适合一个堆栈框架。
• foldRight是递归的，但不是尾递归的，因此列表中的每个元素消耗一个堆栈帧。

foldLeftis thus safe, while foldRightmight stack overflow for long lists.

foldLeft因此是安全的，而foldRight对于长列表可能会堆栈溢出。

EditTo complete my answer, as it only adresses part of your question: it also matters which one you use depending on what you intend to do.

编辑为了完成我的回答，因为它只解决了您问题的一部分：根据您打算做什么，您使用哪一个也很重要。

To take your example, what I consider the optimal solution is to use foldLeft, prepending results to your accumulator, and reversethe result.

以您为例，我认为最佳解决方案是使用foldLeft，将结果添加到累加器中，然后reverse将结果。

This way:

这条路：

• the whole operation is O(n)
• it will not overflow the stack, regardless of the size of the list

• 整个操作是 O(n)
• 无论列表的大小如何，它都不会溢出堆栈

This is essentially what you thought you were doing with foldRightwhen assuming that it was implemented in terms of foldLeft.

这基本上就是您foldRight在假设它是根据foldLeft.

Should you use foldRight, you'll get a slightly faster implementation (well, slightly... twice as fast, really, but still O(n)) at the cost of safety.

如果你使用foldRight，你会得到一个稍微快一点的实现（好吧，稍微……快两倍，真的，但仍然是 O(n)），但要以安全为代价。

One could argue that, if you know your lists are going to be small enough, there is no safety issue and you can use foldRight. I feel, but that's only an opinion, that if your lists are small enough that you don't have to worry about your stack, they're small enough that you don't have to worry about the performance hit either.

有人可能会争辩说，如果您知道您的列表足够小，那么就不存在安全问题，您可以使用foldRight. 我觉得，但这只是一种意见，如果你的列表足够小，你不必担心你的堆栈，它们也足够小，你也不必担心性能下降。

回答by tgr

It depends, consider the following:

这取决于，请考虑以下事项：

scala> val l = List(1, 2, 3)
l: List[Int] = List(1, 2, 3)

scala> l.foldLeft(List.empty[Int]) { (acc, ele) => ele :: acc }
res0: List[Int] = List(3, 2, 1)

scala> l.foldRight(List.empty[Int]) { (ele, acc) => ele :: acc }
res1: List[Int] = List(1, 2, 3)

As you can see, foldLefttraverses the list from headto the last element. foldRighton the other hand traverses it from the last element to head.

如您所见，foldLeft从head到最后一个元素遍历列表。foldRight另一方面从最后一个元素到head.

If you use folding for agregation, there should be no difference:

如果使用折叠进行聚合，应该没有区别：

scala> l.foldLeft(0) { (acc, ele) => ele + acc }
res2: Int = 6

scala> l.foldRight(0) { (ele, acc) => ele + acc }
res3: Int = 6

回答by Thirupathi Chavati

scala> val words = List("Hic", "Est", "Index")
words: List[String] = List(Hic, Est, Index)

Incase of foldLeft:List elements will add to the empty string first and followed

Incase of foldLeft:List 元素将首先添加到空字符串中

words.foldLeft("")(_ + _) == (("" + "Hic") + "Est") + "Index"      //"HicEstIndex"

Incase of foldRight:Empty string will add to end of elements

Incase of foldRight：空字符串将添加到元素的末尾

words.foldRight("")(_ + _) == "Hic" + ("Est" + ("Index" + ""))     //"HicEstIndex"

Both cases will return the same output

两种情况都将返回相同的输出

def foldRight[B](z: B)(f: (A, B) => B): B
def foldLeft[B](z: B)(f: (B, A) => B): B

回答by Benjamin Kovach

I'm no Scala expert, but in Haskell, one of the most important differentiating features between foldl'(which really should be the default left fold) and foldris that foldrwill work on infinite data structures, where foldl'will hang indefinitely.

我不是 Scala 专家，但在 Haskell 中，最重要的区别之一是foldl'（这实际上应该是默认的左折叠）和foldr它foldr适用于无限数据结构，在那里foldl'将无限期挂起。

In order to understand why this is, I recommend visiting foldl.comand foldr.com, expanding the evaluations a couple of times, and reconstructing the call tree. You'll quickly see where foldris appropriate versus foldl'.

为了理解为什么会这样，我建议访问foldl.com和foldr.com，将评估扩展几次，并重建调用树。您将很快看到foldr与foldl'.