foldLeft与foldRight

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

用右折叠:

Range(1,101).foldRight(0)((x,y)=>x+y)

可缩写为

(Range(1,101):\0)(_+_)

用左折叠:

Range(1,101).foldLeft(0)((x,y)=>x+y)

可缩写为

(0/:Range(1,101))(_+_)

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

(Array("1","2","3").map(Integer.parseInt):\0) (_+_)

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

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

假设容器里有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)。

foldLeft与foldRight》上有2条评论

  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方法抛出的。

    回复
    1. hongjiang 文章作者

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

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

      回复

发表评论

电子邮件地址不会被公开。 必填项已用*标注