66

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

为什么我不能以与orfold相同的方式使用该功能？foldLeftfoldRight

在Set scaladoc 中它说：

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

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

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

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

编辑：例如，我将如何编写折叠以添加列表中的所有元素？有了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)(_ + _)
    ^
4

7 回答 7

77

简短的回答：

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

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

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

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

fold是关联的，因为没有定义元素相加的顺序。即fold形成幺半群的论据。

于 2011-06-06T16:28:15.197 回答
57

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

于 2011-06-06T15:11:40.033 回答
11

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

于 2011-06-08T21:34:37.150 回答
3

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

val ns = List(1, 2, 3, 4)
val s0 = ns.foldLeft (0) (_+_) //10
val s1 = ns.fold (0) (_+_) //10
assert(s0 == s1)
于 2011-06-06T18:25:00.390 回答
3

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

 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)
 }
}

结果不言自明：

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
于 2017-04-20T05:39:15.233 回答
1

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

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

输入：5

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

迭代解决方案。

遍历 1 到 5 并对每个元素求和。

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

递归解决方案

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

  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：是一个迭代解决方案

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

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

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

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

在此处输入图像描述

于 2020-02-07T02:51:35.850 回答
0

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

总和列表的示例 -

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
 * #######################
 */
于 2019-10-18T06:44:15.990 回答