折叠和foldLeft方法的区别

Question

我不确定fold和foldLeftScala 之间有什么区别.

问题折叠和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 - 折叠操作的中性元素; 可被添加到所述结果的任意次数,并且不能改变的结果(例如,无连接列表,0此外,或1乘法.)

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

Answer 1

由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是.)

Answer 2

我不熟悉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.如果您不遵守该约束,则最终会向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出现两次.

Answer 3

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

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

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

VS

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

简而言之,fold被定义为在某种类型A1上运行,它是数组类型的超类型,对于您的字符串数组,编译器将其定义为"Any"(可能是因为它需要一种可以存储String 或 int-notice的类型)传递给fold Fold的组合器方法需要两个相同类型的参数？)这也是文档在讨论z时的意思--Fold的实现可以使它并行组合你的输入,例如:

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

另一方面,foldLeft在类型B(无约束)上运行,并且只要求您提供一个组合器方法,该方法接受类型B的参数和数组的另一个类型(在您的情况下为String),并生成B.

Answer 4

错误.您将收到编译时错误,因为签名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并A1通过连续应用生成类型的折叠值op.这些处理器产生的结果必须组合成一个最终的折叠值 - 这是使用op函数完成的,这正是这样做的.

现在,请注意,使用fin 无法完成此操作foldLeft,因为每个处理器都会生成折叠值类型B.类型的几个值B不能使用进行组合f,因为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中性元素,但不能使用非空列表.

Answer 5

一般差异

以下是这些方法的原型

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

因此,对于折叠,结果是类型A1 >: A而不是任何类型B.而且,正如doc中所指定的那样,对于fold命令不是

关于你的错误

在输入时scala> Array("1","2","3").fold(0)(_ + _.toInt)你假设0,a int是一个子类型String.这就是编译器抛出错误的原因.

关于奇怪的折叠

在这里我们必须看到实现,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))
}

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

因此我们可以看到折叠已经以这样的方式并行化,即零值被多次使用.如果我们再次运行它,我们可能会在日志中看到不同的值.