折叠和折叠的方法区别

我不确定Scala中foldfoldLeft什么区别。

折叠和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用于乘法)。

为什么会添加任意次数 ? 我认为折叠工作不同。

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

为了允许顺序列表的任意树分解,你必须有一个零,它不会做任何事情(所以你可以将它添加到树中任何需要它的地方),并且你必须创build和你一样的东西你的二进制参数,所以types不会改变,取决于你如何分解树。

(能够评估为树并行化是非常好的,如果你希望能够随时改变你的输出时间,你需要一个组合运算符一个标准的起始值 – 变换序列 – 元素 – 期望types的函数就像foldLeft一样,Scala有这个并且把它称为aggregate ,但是在某些方面,这更像foldLeft不是fold

我对Scala并不熟悉,但是Scala的集合库和Haskell有类似的devise。 这个答案是基于Haskell的,对于Scala来说也可能是准确的。

因为foldLeft处理input,所以它可以有不同的input和输出types。 另一方面, fold可以按不同的顺序处理input,所以input和输出必须具有相同的types。 通过扩展折叠expression式,这是最容易看到的。 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。 如果你不尊重这个约束,你最终会添加string整数! 这个错误被types系统捕获。

中性元素可以被多次引入,因为通常通过分割input和执行多个顺序的折叠来实现平行折叠。 顺序折叠介绍一次中性元素。 想象一下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出现两次。

注意:我可能在这里完全错误。 我的Scala并不完美。

我认为差异在于方法的签名:

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

VS

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

简而言之,fold被定义为对某个types为A1的数组进行操作,该types是数组types的超types,对于您的string数组,编译器将其定义为“Any”(可能是因为它需要一个可以存储您的String int型通知的types传递给折叠的组合方法需要两个相同types的参数吗?)这也是文档在谈到z时的含义–Fold的实现可能会并行地组合input,例如:

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

另一方面,foldLeft对typesB(不受限制)进行操作,只会要求您提供一个组合方法,该方法接受Btypes的参数和另一个数组types(在您的情况下为String),并生成一个B.

错误。 您正在收到编译时错误,因为fold的签名只允许折叠属于集合中值types的超types的types的值,以及String (集合types)和Int (types)的唯一超types您提供的零元素)是Any 。 所以,折叠结果的types被推断为AnyAny没有方法toInt

请注意,两个版本的fold有不同的签名:

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

为什么他们有不同的签名? 这是因为fold可以并行执行,就像parallel collection一样。 当多个处理器折叠集合中的值时,每个处理器都通过连续应用op来获取typesA的元素的子集,并产生typesA1的折叠值。 这些处理器产生的结果必须结合在一起形成一个最终的折叠值 – 这是使用op函数完成的。

现在请注意,这不能在foldLeft使用f来完成,因为每个处理器都会产生一个typesB的折叠值。 typesB几个值不能用f组合,因为f只将值B与另一个typesA值结合 – typesAB之间没有对应关系。

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

对于这些types不同的情况,请使用aggregate ,您必须在其中定义如何组合两个types为B值:

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

上面的组合定义了当折叠结果和集合中的元素具有不同types时如何进行最后一步。

中性元素。 如上所述,多个处理器可以折叠集合中的元素的子集。 他们每个人都将通过添加中性元素来开始其折叠值。

在以下示例中:

 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作为一个中性元素,但不是一个非空的列表。

另一个答案指出, 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) } } 

接下来,我们可以创build这些东西和一个标识元素的并行集合:

 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) 

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

一般的区别

这里是方法的原型

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

所以,对于折叠结果是typesA1 >: A而不是任何B 而且,正如文件中所规定的那样, fold的顺序不是

关于你的错误

当inputscala> Array("1","2","3").fold(0)(_ + _.toInt) ,假定0intString的子types。 这就是编译器抛出错误的原因。

关于折叠怪异的z

在这里我们必须看到fold的实现来理解发生了什么。 这是我们得到的:

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

所以基本上, fold是对输出types有约束的foldleft的实现。 现在我们可以看到z在实践中的使用方式与foldleft相同。 所以我们可以得出这样的结论:因为在将来的实现中没有任何东西可以保证行为。 我们现在已经可以看到它,有相似之处 :

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