scala fold 和 foldLeft 或 foldRight 之间的区别？

Difference between fold and foldLeft or foldRight?

提问by Andriy Drozdyuk

NOTE: I am on Scala 2.8—can that be a problem?

注意：我使用的是 Scala 2.8——这会不会有问题？

Why can't I use the foldfunction the same way as foldLeftor foldRight?

为什么我不能fold以与foldLeft或相同的方式使用该函数foldRight？

In the Set scaladocit says that:

在Set scaladoc它说：

The result of folding may only be a supertype of this parallel collection's type parameter T.

折叠的结果可能只是这个并行集合的类型参数的超类型T。

But I see no type parameter Tin the function signature:

但是我T在函数签名中看不到类型参数：

def fold [A1 >: A] (z: A1)(op: (A1, A1) ? A1): A1

What is the difference between the foldLeft-Rightand fold, and how do I use the latter?

foldLeft-Right和之间有什么区别fold，我该如何使用后者？

EDIT: For example how would I write a fold to add all elements in a list? With foldLeftit would be:

编辑：例如，我将如何编写折叠以添加列表中的所有元素？有了foldLeft这将是：

val foo = List(1, 2, 3)
foo.foldLeft(0)(_ + _)

// now try fold:
foo.fold(0)(_ + _)
>:7: error: value fold is not a member of List[Int]
  foo.fold(0)(_ + _)
    ^

采纳答案by exlevan

You're right about the old version of Scala being a problem. If you look at the scaladoc pagefor Scala 2.8.1, you'll see no fold defined there (which is consistent with your error message). Apparently, foldwas introduced in Scala 2.9.

你是对的，旧版本的 Scala 是一个问题。如果您查看Scala 2.8.1的scaladoc 页面，您将看到那里没有定义折叠（这与您的错误消息一致）。显然，fold是在 Scala 2.9 中引入的。

回答by Apocalisp

Short answer:

简答：

foldRightassociates to the right. I.e. elements will be accumulated in right-to-left order:

foldRight右边的伙伴。即元素将按从右到左的顺序累积：

List(a,b,c).foldRight(z)(f) = f(a, f(b, f(c, z)))

foldLeftassociates to the left. I.e. an accumulator will be initialized and elements will be added to the accumulator in left-to-right order:

foldLeft左边的同事。即一个累加器将被初始化，元素将按从左到右的顺序添加到累加器中：

List(a,b,c).foldLeft(z)(f) = f(f(f(z, a), b), c)

foldis associativein that the order in which the elements are added together is not defined. I.e. the arguments to foldform a monoid.

fold是关联的，因为未定义元素添加在一起的顺序。即fold形成幺半群的参数。

回答by Jean-Philippe Pellet

fold, contrary to foldRightand foldLeft, does not offer any guarantee about the order in which the elements of the collection will be processed. You'll probably want to use fold, with its more constrained signature, with parallel collections, where the lack of guaranteed processing order helps the parallel collection implements folding in a parallel way. The reason for changing the signature is similar: with the additional constraints, it's easier to make a parallel fold.

fold，与foldRight和相反foldLeft，不对集合元素的处理顺序提供任何保证。您可能希望使用fold具有更多约束签名的 并行集合，其中缺乏保证的处理顺序有助于并行集合以并行方式实现折叠。更改签名的原因类似：使用附加约束，更容易进行平行折叠。

回答by Ram Ghadiyaram

Agree with other answers. thought of giving a simple illustrative example:

同意其他答案。想到了一个简单的说明性例子：

 object MyClass {
 def main(args: Array[String]) {
val numbers = List(5, 4, 8, 6, 2)
 val a =  numbers.fold(0) { (z, i) =>
 {
     println("fold val1 " + z +" val2 " + i)
  z + i

 }
}
println(a)
 val b =  numbers.foldLeft(0) { (z, i) =>
 println("foldleft val1 " + z +" val2 " + i)
  z + i

}
println(b)
   val c =  numbers.foldRight(0) { (z, i) =>
   println("fold right val1 " + z +" val2 " + i)
  z + i

}
println(c)
 }
}

Result is self explanatory :

结果是不言自明的：

fold val1 0 val2 5
fold val1 5 val2 4
fold val1 9 val2 8
fold val1 17 val2 6
fold val1 23 val2 2
25
foldleft val1 0 val2 5
foldleft val1 5 val2 4
foldleft val1 9 val2 8
foldleft val1 17 val2 6
foldleft val1 23 val2 2
25
fold right val1 2 val2 0
fold right val1 6 val2 2
fold right val1 8 val2 8
fold right val1 4 val2 16
fold right val1 5 val2 20
25

回答by Garrett Rowe

For your particular example you would code it the same way you would with foldLeft.

对于您的特定示例，您将使用与 foldLeft 相同的方式对其进行编码。

val ns = List(1, 2, 3, 4)
val s0 = ns.foldLeft (0) (_+_) //10
val s1 = ns.fold (0) (_+_) //10
assert(s0 == s1)

回答by thedevd

fold() does parallel processing so does not guarantee the processing order. where as foldLeft and foldRight process the items in sequentially for left to right (in case of foldLeft) or right to left (in case of foldRight)

fold() 进行并行处理，因此不保证处理顺序。其中 foldLeft 和 foldRight 按从左到右（在 foldLeft 的情况下）或从右到左（在 foldRight 的情况下）的顺序处理项目

Examples of sum the list -

总结列表的例子 -

val numList = List(1, 2, 3, 4, 5)

val r1 = numList.par.fold(0)((acc, value) => {
  println("adding accumulator=" + acc + ", value=" + value + " => " + (acc + value))
  acc + value
})
println("fold(): " + r1)
println("#######################")
/*
 * You can see from the output that,
 * fold process the elements of parallel collection in parallel
 * So it is parallel not linear operation.
 * 
 * adding accumulator=0, value=4 => 4
 * adding accumulator=0, value=3 => 3
 * adding accumulator=0, value=1 => 1
 * adding accumulator=0, value=5 => 5
 * adding accumulator=4, value=5 => 9
 * adding accumulator=0, value=2 => 2
 * adding accumulator=3, value=9 => 12
 * adding accumulator=1, value=2 => 3
 * adding accumulator=3, value=12 => 15
 * fold(): 15
 */

val r2 = numList.par.foldLeft(0)((acc, value) => {
  println("adding accumulator=" + acc + ", value=" + value + " => " + (acc + value))
  acc + value
})
println("foldLeft(): " + r2)
println("#######################")
/*
 * You can see that foldLeft
 * picks elements from left to right.
 * It means foldLeft does sequence operation
 * 
 * adding accumulator=0, value=1 => 1
 * adding accumulator=1, value=2 => 3
 * adding accumulator=3, value=3 => 6
 * adding accumulator=6, value=4 => 10
 * adding accumulator=10, value=5 => 15
 * foldLeft(): 15
 * #######################
 */

// --> Note in foldRight second arguments is accumulated one.
val r3 = numList.par.foldRight(0)((value, acc) => {
 println("adding value=" + value + ", acc=" + acc + " => " + (value + acc))
  acc + value
})
println("foldRight(): " + r3)
println("#######################")

/*
 * You can see that foldRight
 * picks elements from right to left.
 * It means foldRight does sequence operation.
 * 
 * adding value=5, acc=0 => 5
 * adding value=4, acc=5 => 9
 * adding value=3, acc=9 => 12
 * adding value=2, acc=12 => 14
 * adding value=1, acc=14 => 15
 * foldRight(): 15
 * #######################
 */

回答by Gaurang Shah

There is two way to solve problems, iterative and recursive. Let's understand by a simple example.let's write a function to sum till the given number.

有两种解决问题的方法，迭代和递归。让我们通过一个简单的例子来理解。让我们编写一个函数来求和直到给定的数字。

For example if I give input as 5, I should get 15 as output, as mentioned below.

例如，如果我将输入设为 5，我应该得到 15 作为输出，如下所述。

Input: 5

输入：5

Output: (1+2+3+4+5) = 15

输出：(1+2+3+4+5) = 15

Iterative Solution.

迭代解决方案。

iterate through 1 to 5 and sum each element.

迭代 1 到 5 并对每个元素求和。

  def sumNumber(num: Int): Long = {
    var sum=0
    for(i <- 1 to num){
      sum+=i
    }
    sum
  }

Recursive Solution

递归解

break down the bigger problem into smaller problems and solve them.

把大问题分解成小问题，然后解决它们。

  def sumNumberRec(num:Int, sum:Int=0): Long = {
    if(num == 0){
      sum
    }else{
      val newNum = num - 1
      val newSum = sum + num
      sumNumberRec(newNum, newSum)
    }
  }

FoldLeft: is a iterative solution

FoldRight: is a recursive solution I am not sure if they have memoization to improve the complexity.

FoldLeft：是一个迭代解决方案

FoldRight：是一种递归解决方案，我不确定他们是否有记忆来提高复杂性。

And so, if you run the foldRight and FoldLeft on the small list, both will give you a result with similar performance.

因此，如果您在小列表上运行 foldRight 和 FoldLeft，两者都会为您提供具有相似性能的结果。

However, if you will try to run a FoldRighton Long Listit might throw a StackOverFlowerror (depends on your memory)

但是，如果您尝试FoldRight在Long List上运行，它可能会引发StackOverFlow错误（取决于您的记忆）

Check the following screenshot, where foldLeftran without error, however foldRighton same list gave OutofMemmoryError.

检查以下屏幕截图，其中foldLeft运行没有错误，但是foldRight在同一个列表中给出了OutofMemmory错误。