斯卡拉 : 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 一样工作？什么是可使用Equals序列化？据我了解，fold 和foldLeft 在参数泛型类型方面的API 签名略有不同。请指教。谢谢。

Answer 1

方法fold (最初是为了并行计算而添加的)不如 foldLeft 强大就其可应用的类型而言。它的签名是:

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

这意味着进行折叠的类型必须是集合元素类型的父类(super class)型。

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

原因是fold可以并行实现，而foldLeft不能。这不仅仅是因为*Left这意味着 foldLeft 的部分从左到右依次进行，也是因为运算符 op无法组合并行计算的结果 - 它仅定义如何组合聚合类型 B元素类型为 A ，但不是如何组合 B 类型的两个聚合。 fold方法反过来确实定义了这一点，因为聚合类型 A1必须是元素类型 A 的父类(super class)型，即A1 >: A 。这种父类(super class)型关系允许同时折叠聚合和元素，并组合聚合——两者都使用单个运算符。

但是，聚合和元素类型之间的这种父类(super class)型关系也意味着聚合类型 A1在你的例子中应该是 (ArrayBuffer[Int], Int) 的父类(super class)型。由于聚合的零元素是 ArrayBuffer(1, 2, 4, 5)类型 ArrayBuffer[Int] ，聚合类型被推断为这两者的父类(super class)型——那就是 Serializable with Equals ，元组和数组缓冲区的唯一最小上限。

一般来说，如果你想允许任意类型的并行折叠(这是无序的)，你必须使用方法 aggregate这需要定义如何组合两个聚合。对于您的情况:

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

顺便说一句，尝试用 reduce 编写您的示例/reduceLeft -- 由于这两种方法所具有的元素类型和聚合类型之间的父类(super class)型关系，您会发现它会导致与您所描述的类似的错误。