56

我不确定Scalafold和foldLeftScala 之间有什么区别。

问题fold 和 foldLeft 或 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 表示乘法。）

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

4

7 回答 7

76

正如 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

为了允许顺序列表的任意树分解，你必须有一个不做任何事情的零（所以你可以在树中任何你需要的地方添加它）并且你必须创建你认为的相同类型的东西您的二进制参数，因此类型不会根据您分解树的方式而改变。

（能够评估为一棵树对并行化很有好处。如果您希望能够随时转换输出时间，您需要一个组合运算符和一个标准的 start-value-transforms-sequence-element-to-desired -type 函数就像foldLefthas。Scala 有 this 并调用它aggregate，但在某些方面 this 更像foldLeft是fold。）

于 2012-07-03T23:02:29.713 回答
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出现两次。

于 2012-07-03T21:18:23.367 回答
15

注意：我在这里可能完全错了。我的 scala 并不完美。

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

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

对比

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

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

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

另一方面， foldLeft 对 B 类型（不受约束）进行操作，并且只要求您提供一个组合器方法，该方法采用 B 类型的参数和数组类型的另一个参数（在您的情况下为字符串），并产生一个 B。

于 2012-07-03T21:13:28.423 回答
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可以并行实现，就像并行集合一样。当多个处理器折叠集合中的值时，每个处理器都会获取 type 元素的子集，并通过连续应用来A生成 type 的折叠值。这些处理器产生的结果必须组合成一个最终的折叠值——这是使用函数完成的，它就是这样做的。A1opop

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

例子。在您的示例中，假设第一个处理器采用元素"1", "2"，第二个处理器采用 element "3"。第一个将产生折叠值3，第二个将产生另一个折叠值3。现在他们必须结合他们的结果来获得最终的折叠值——这是不可能的，因为闭包_ + _.toInt只知道如何结合一个IntandString而不是 2 个Int值。

对于这些类型不同的情况，请使用aggregate，其中您必须定义如何组合 type 的两个值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用作中性元素，但不能用作非空列表。

于 2012-07-03T22:57:11.583 回答
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)

所以我们可以看到折叠已经被并行化，使得零值被多次使用。如果我们再次运行它，我们可能会在日志中看到不同的值。

于 2012-07-03T21:35:48.457 回答
5

一般差异

这是方法的原型

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

因此，对于 fold 结果是 typeA1 >: A而不是 any B。此外，如文档中fold所述，订单不是

关于你的错误

键入时scala> Array("1","2","3").fold(0)(_ + _.toInt)，您假定0anint是 的子类型String。这就是编译器抛出错误的原因。

关于折叠中的奇怪 z

在这里，我们必须查看执行以fold了解发生了什么。这是我们得到的：

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

所以基本上，fold是一个foldleft对输出类型有约束的实现。我们现在可以看到，z在实践中将使用与 中相同的方式foldleft。因此，我们可以得出结论，之所以做出此评论，是因为在未来的实现中没有任何东西可以保证这种行为。我们现在已经可以看到它了，有相似之处：

def fold[U >: T](z: U)(op: (U, U) => U): U = {
  executeAndWaitResult(new Fold(z, op, splitter))
}
于 2012-07-03T21:13:47.987 回答
0

已经提到过，但没有示例：如果您想允许输出和输入的不同数据类型的并行性，您可以使用aggregate：

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

第一个函数首先被调用。然后用第二个函数减少它的结果。请参阅聚合 scala 函数的说明。

于 2019-05-20T03:59:00.827 回答