Scala:fold vs foldLeft

Question

我试图了解fold和foldLeft以及各自的reduce和reduceLeft是如何工作的.我用fold和foldLeft作为例子

scala> val r = List((ArrayBuffer(1, 2, 3, 4),10))
scala> r.foldLeft(ArrayBuffer(1,2,4,5))((x,y) => x -- y._1)

scala> res28: scala.collection.mutable.ArrayBuffer[Int] = ArrayBuffer(5)

scala> r.fold(ArrayBuffer(1,2,4,5))((x,y) => x -- y._1)
<console>:11: error: value _1 is not a member of Serializable with Equals
              r.fold(ArrayBuffer(1,2,4,5))((x,y) => x -- y._1)

为什么fold不工作foldLeft？什么是Serializable with Equals？我理解fold和foldLeft在参数泛型类型方面有轻微不同的API签名.请指教.谢谢.

Answer 1

该方法fold(最初为并行计算添加)的功能不如foldLeft它可以应用的类型.它的签名是:

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

这意味着完成折叠的类型必须是集合元素类型的超类型.

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

原因是fold可以并行实现,而foldLeft不能.这不仅是因为*Left暗示foldLeft从左到右顺序排列的部分,还因为操作员op无法组合并行计算的结果 - 它只定义了如何将聚合类型B与元素类型A相结合,而不是如何组合两种类型的聚合B.fold反过来,该方法确实定义了这个,因为聚合类型A1必须是元素类型的超类型A,即A1 >: A.这种超类型关系允许同时折叠聚合和元素,以及组合聚合 - 两者都与单个运算符相结合.

但是,聚合和元素类型之间的这种超类型关系也意味着A1您的示例中的聚合类型应该是超类型(ArrayBuffer[Int], Int).由于聚合的零元素属于ArrayBuffer(1, 2, 4, 5)类型ArrayBuffer[Int],因此聚合类型被推断为这两者的超类型 - 这Serializable with Equals是元组和数组缓冲区的唯一最小上限.

通常,如果要允许任意类型的并行折叠(这不按顺序完成),则必须使用aggregate需要定义两个聚合如何组合的方法.在你的情况下:

r.aggregate(ArrayBuffer(1, 2, 4, 5))({ (x, y) => x -- y._1 }, (x, y) => x intersect y)

顺便说一句,尝试用reduce/ 编写你的例子,reduceLeft因为这两种方法都有元素类型和聚合类型之间的超类型关系,你会发现它会导致与你所描述的类似的错误.