fold和foldLeft方法的区别

Question

fold和foldLeft方法的区别

56

我不确定在Scala中fold和foldLeft的区别是什么。

这个问题“Difference between fold and foldLeft or foldRight?”有一个回答讨论了顺序。这是可以理解的。但我仍然不明白为什么这样会起作用（来自REPL）：

scala> Array("1","2","3").foldLeft(0)(_ + _.toInt)
res6: Int = 6

但是这个不行：

scala> Array("1","2","3").fold(0)(_ + _.toInt)
<console>:8: error: value toInt is not a member of Any
              Array("1","2","3").fold(0)(_ + _.toInt)
                                               ^

这个错误信息的意思是什么？

我也感到文档中的这一行很困惑。

z - 折叠操作的中性元素；可以任意添加到结果中，且不能改变结果（例如，在列表连接中为Nil，在加法中为0，在乘法中为1）。

为什么它会被任意次数地添加？我以为折叠的工作方式不同。

- Karel Bílek

7个回答

30

我不熟悉Scala，但Scala的集合库与Haskell的设计类似。这个答案基于Haskell，对于Scala可能也是准确的。

因为foldLeft从左到右处理它的输入，所以它可以有不同的输入和输出类型。另一方面，fold可以以不同的顺序处理其输入，因此输入和输出必须都具有相同的类型。通过展开折叠表达式最容易看出这一点。foldLeft按特定顺序进行操作：

Array("1","2","3").foldLeft(0)(_ + _.toInt)
= ((0 + "1".toInt) + "2".toInt) + "3".toInt

请注意，数组元素从不用作组合函数的第一个参数。它们始终出现在+的右侧。

fold不保证特定的顺序。它可能会执行各种操作，例如：

Array("1","2","3").fold(0)(_ + _.toInt)
=  ((0 + "1".toInt) + "2".toInt) + "3".toInt
or (0 + "1".toInt) + ("2" + "3".toInt).toInt
or "1" + ("2" + ("3" + 0.toInt).toInt).toInt

数组元素可以出现在组合函数的任一参数中。但是，您的组合函数期望其第一个参数为int类型。如果不遵守这个限制，就会将字符串添加到整数值上! 这个错误会被类型系统捕获。

由于通常并行折叠是通过拆分输入并执行多个连续折叠来实现的，因此可以多次引入中性元素。顺序折叠只介绍中性元素一次。想象一下Array(1,2,3,4).fold(0)(_ + _)的一个特定的执行，其中该数组分成两个单独的数组，并且这些数组在两个线程中被顺序地折叠。（当然，真正的fold函数不会将数组分裂成多个数组。）一个线程执行Array(1,2).fold(0)(_ + _)，计算0+1+2。另一个线程执行Array(3,4).fold(0)(_ + _)，计算0+3+4。最后，两个线程的部分总和相加。请注意，中性元素0出现了两次。

- Heatsink

fold 相对于 foldLeft 的优势在于，fold 可以并行处理数据，而 foldLeft 是线性的，因此 fold 可能比 foldLeft 更快。这是正确的吗？ - Frank Kong

15

注意：我可能完全错误。我的Scala并不完美。

我认为区别在于方法的签名：

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

vs

def foldLeft[B](z: B)(op: (B, T) ⇒ B): B

简而言之，折叠被定义为对某种类型A1进行操作，该类型是数组类型的超类型，对于您的字符串数组，编译器将其定义为“Any”（可能是因为它需要一种可以存储您的String或int的类型-请注意传递给折叠Fold的组合方法需要两个相同类型的参数）。这也是文档在谈论z时所指的- Fold的实现可能是并行组合您的输入，例如：

"1" + "2" --\
             --> 3 + 3 -> 6
"3" + *z* --/

另一方面，foldLeft 操作的类型是 B（无限制的），只要求您提供一个组合器方法，该方法接受类型为 B 和数组类型（在您的情况下为 String）的另一个参数，并生成一个 B。

- Chris Shain

2

那几乎是完美的。A1 是 A 的超类型 -- 也就是说，我可以从 Int 转换到 Any（例如），但不能从 Any 转换到 Int。 - Daniel C. Sobral

好的。在这种情况下，我不确定为什么它被转换为 Any 而不是 AnyVal。但除此之外，我认为我理解了。 - Karel Bílek

1

@KarelBílek 可能是因为需要一个 String 和 int 共同的基础类型。String 是一个引用类型（再次假设，因为它在 Java 中）。 - Chris Shain

15

错误原因。你遇到了一个编译时错误，因为fold函数的签名只允许折叠集合中类型是其值类型的超类型的值，而String（你的集合类型）和Int（你提供的零元素的类型）的唯一超类型是Any。因此，折叠结果的类型被推断为Any，而Any没有toInt方法。

请注意，两个版本的fold具有不同的签名：

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

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

为什么它们有不同的签名？这是因为fold可以并行实现，就像并行集合一样。当多个处理器折叠集合中的值时，每个处理器都会取一个元素类型为A的子集，并通过连续应用op来生成类型A1的折叠值。那些处理器产生的结果必须合并成一个最终的折叠值 - 这是使用函数op完成的，它正是做这件事的。

现在，请注意，这不能使用foldLeft中的f来完成，因为每个处理器都会产生类型为B的折叠值。无法使用f组合多个类型为B的值，因为f只能将值B与另一个类型为A的值组合 - 类型A和B之间没有对应关系。

例子。在你的例子中，假设第一个处理器获取元素"1"、"2"，第二个处理器获取元素"3"。第一个处理器将生成折叠值3，第二个处理器将生成另一个折叠值3。现在，它们必须合并它们的结果以获取最终的折叠值 - 这是不可能的，因为闭包_ + _.toInt只知道如何组合一个Int和一个String，而不是两个Int值。

对于这些类型不同的情况，请使用aggregate，其中必须定义如何组合两个类型为B的值：

def aggregate[B](z: B)(seqop: (B, A) => B, combop: (B, B) => B): B

combop定义了当折叠结果和集合中的元素具有不同类型时如何执行最后一步。

中性元素。如上所述，多个处理器可能会在集合的子集上进行折叠。每个处理器将通过添加中性元素来开始其折叠值。

在以下示例中：

List(1, 2, 3).foldLeft(4)(_ + _)

该函数总是返回10 = 4 + 1 + 2 + 3。

然而，4不应与fold一起使用，因为它不是一个中性元素：

List(1, 2, 3).fold(4)(_ + _)

上面的代码可能会返回 (4 + 1 + 2) + (4 + 3) = 14 或者 (4 + 1) + (4 + 2) + (4 + 3) = 18。如果在 fold 中不使用中性元素，则结果是不确定的。同样地，您可以使用 Nil 作为中性元素，但不能使用非空列表。

- axel22

6

正如其他答案所指出的那样，fold方法主要是为了支持并行折叠。您可以按照以下方式查看此操作。首先，我们可以定义一种包装整数的方式，以便跟踪已对其实例执行的操作。

case class TrackInt(v: Int) {
  val log = collection.mutable.Buffer.empty[Int]
  def plus(that: TrackInt) = {
    this.log += that.v
    that.log += this.v
    new TrackInt(this.v + that.v)
  }
}

接下来，我们可以创建一个并行集合和一个身份元素来表示这些内容：

val xs = (1 to 10).map(TrackInt(_)).par
val zero = TrackInt(0)

首先我们会尝试使用foldLeft：

scala> xs.foldLeft(zero)(_ plus _)
res0: TrackInt = TrackInt(55)

scala> zero.log
res1: scala.collection.mutable.Buffer[Int] = ArrayBuffer(1)

因此，我们的零值仅被使用一次，就像我们所期望的那样，因为foldLeft执行顺序折叠。接下来，我们可以清除日志并尝试fold：

scala> zero.log.clear()

scala> xs.fold(zero)(_ plus _)
res2: TrackInt = TrackInt(55)

scala> zero.log
res3: scala.collection.mutable.Buffer[Int] = ArrayBuffer(1, 6, 2, 7, 8)

我们可以看到，折叠操作已经并行化了，以至于零值被多次使用。如果我们再次运行这个程序，很可能会在日志中看到不同的值。

- Travis Brown

5

一般差异

这里是方法的原型

fold[A1 >: A](z: A1)(op: (A1, A1) ⇒ A1): A1
foldLeft[B](z: B)(f: (B, A) ⇒ B): B

因此，对于fold，结果的类型为A1 >: A，而不是任何B。此外，正如文档中指定的那样，对于fold，顺序不是。

关于您的错误

当输入scala> Array("1","2","3").fold(0)(_ + _.toInt)时，您假设0，即int是String的子类型。这就是编译器报错的原因。

关于折叠中奇怪的z

在这里，我们需要查看fold的实现才能理解发生了什么。以下是我们得到的内容：

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

基本上，fold是对输出类型施加限制的foldleft实现。我们现在可以看到，在实践中z将与foldleft中使用方式相同。因此，我们可以得出结论，这个注释是因为没有什么保证在未来的实现中会有同样的行为。我们已经可以看到了，比如parallels：

def fold[U >: T](z: U)(op: (U, U) => U): U = {
  executeAndWaitResult(new Fold(z, op, splitter))
}

- Christopher Chiche

0

虽然已经提到过，但没有举例说明：如果您想允许输出和输入使用不同数据类型的并行处理，可以使用aggregate：

Array("1","2","3").aggregate(0)(_ + _.toInt, _ + _)

第一个函数首先被调用。然后使用第二个函数对其结果进行归约。请参阅scala聚合函数说明。

- serv-inc

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Rex Kerr · Accepted Answer

根据Scala的定义，foldLeft是一种线性操作，而fold则允许成为一种树形操作。例如：

List(1,2,3,4,5).foldLeft(0)(_ + _)
// This is the only valid order of operations
0+1 = 1
      1+2 = 3
            3+3 = 6
                  6+4 = 10
                        10 + 5 = 15
                                 15  // done

List(1,2,3,4,5).fold(0)(_ + _)
// This is valid
0+1 = 1             0+3 = 3           0+5 = 5
      1+2 = 3             3+4 = 7           5
            3         +         7=10        5
                                  10    +   5 = 15
                                                15  // done

为了允许一个顺序列表的任意树形分解，你必须有一个不执行任何操作的零元素（这样你就可以在树中添加它），并且你必须创建与您取为二元参数的相同类型的东西，以便类型不会因为您如何分解树而改变。

（能够作为树进行评估对于并行化很好。如果你想要在进行转换输出的同时能够转换输出时间，你需要既有组合运算符又有一个标准的开始值-将序列元素转换为所需类型的函数，就像foldLeft一样拥有的。Scala 有这个功能，并称其为aggregate，但在某些方面，这更像是 foldLeft 而不是 fold。）