foldLeft与foldRight

1) 先看一个例子: 求1到100的总和

用右折叠:

[scala toolbar=”false”]Range(1,101).foldRight(0)((x,y)=>x+y)
[/scala]

可缩写为

[scala toolbar=”false”](Range(1,101):\0)(_+_)
[/scala]

用左折叠:

[scala toolbar=”false”]Range(1,101).foldLeft(0)((x,y)=>x+y)
[/scala]

可缩写为

[scala toolbar=”false”](0/:Range(1,101))(_+_)
[/scala]

将所有字符串解析为Int,并进行求和(右折叠):

[scala toolbar=”false”](Array(“1″,”2″,”3”).map(Integer.parseInt):\0) (_+_)
[/scala]

2) foldLeft和foldRight方法是在GenTraversableOnce特质里定义的
实现是在GenTraversableOnce 里:

[scala toolbar=”false”]def foldLeft[B](z: B)(op: (B, A) => B): B = {
var result = z
this.seq foreach (x => result = op(result, x))
result
}
[/scala]

假设容器里有a,b,c 三个元素,实现上等同于 op(op(op(z,a),b),c)

返回值的类型是传入的初始值z的类型

3) 右折叠的使用与左折叠不同,
初始参数位置就不同,一个在左(逆序),一个在右
并且效率不同,foldLeft应该效率更高,需要做个测试验证一下。

4) 另一个很大的不同,可能是内存的使用方式,foldRight容易内存溢出:

scala>  println(Range(1,100000001).foldLeft(0) (_+_))
        987459712

scala>  println(Range(1,100000001).foldRight(0) (_+_))
java.lang.OutOfMemoryError: Java heap space
at scala.collection.immutable.List.$colon$colon(List.scala:67)
at scala.collection.TraversableOnce$$anonfun$reversed$1.apply(TraversableOnce.scala:88)
at scala.collection.TraversableOnce$$anonfun$reversed$1.apply(TraversableOnce.scala:88)
at scala.collection.Iterator$class.foreach(Iterator.scala:631)
at scala.collection.IndexedSeqLike$Elements.foreach(IndexedSeqLike.scala:52)
at scala.collection.TraversableOnce$class.reversed(TraversableOnce.scala:88)
at scala.collection.IndexedSeqLike$Elements.reversed(IndexedSeqLike.scala:52)
at scala.collection.TraversableOnce$class.foldRight(TraversableOnce.scala:195)
at scala.collection.IndexedSeqLike$Elements.foldRight(IndexedSeqLike.scala:52)
at scala.collection.IterableLike$class.foldRight(It...

补充,foldRight的实现是非尾递归的(tail-recursive)。

2 thoughts on “foldLeft与foldRight

  1. 楼主好。看到你的博客,觉得有点小问题。
    def foldLeft[B](z: B)(op: (B, A) => B): B = {
    var result = z
    this.seq foreach (x => result = op(result, x))
    result
    }

    def foldRight[B](z: B)(op: (A, B) => B): B =
    reversed.foldLeft(z)((x, y) => op(y, x))

    foldLeft和foldRight是不是尾递归依赖于foreach实现是不是尾递归。foldRight出现堆溢出应该是reversed方法抛出的。

    • 谢谢指出,TraversableOnce里的reversed方法里用了一个不可变的List来做翻转操作,每次会创建新的对象,是这里引发的OOM

      // for internal use
      protected[this] def reversed = {
      var elems: List[A] = Nil
      self foreach (elems ::= _)
      elems
      }

Leave a Reply

Your email address will not be published. Required fields are marked *