scala List reduce和fold对比分析

reduce和fold都是执行折叠操作，reduce是fold的一种特例。
list.reduceLeft(+)相当于list.tail.foldLeft(list.head)(+)

scala> xs.reduceLeft{(x: Int, y: Int) => {println(x + "+" + y); x + y}}
1+2
3+3
6+4
10+5
res33: Int = 15

scala> xs.tail.foldLeft(xs.head){(x: Int, y: Int) => {println(x + "+" + y); x + y}}
1+2
3+3
6+4
10+5
res34: Int = 15

两者的区别如下：
1. 返回类型不同
(1) reduce*（reduce/reduceLeft/reduceRight）将List[A]折叠成A1(A1是A或者A的父类）
(2) fold跟reduce一样
(3) foldLeft和foldRight将List[A]折叠成B，B可以是任意类型，比如可以是另外一种集合。所以，可以做集合的转换，比如把List[Int]转换成Array[String]，并且两者长度可以不相等。
2. 参数不同
(1) reduce操作族用List的头节点或者尾节点作为初始值，所以不需要指定初始值。
(2) fold族需要指定初始值。
3. 空List的折叠结果不同
(1) reduce*抛异常UnsupportedOperationException
(2) reduce*Option返回None
(3) fold*返回初始值

reduce vs fold

List[A]
def reduce[A1 >: A](op: (A1, A1) => A1): A1
// Reduces the elements of this traversable or iterator using the specified associative binary operator.
// The order in which operations are performed on elements is unspecified and may be nondeterministic
def fold[A1 >: A](z: A1)(op: (A1, A1) => A1): A1
// Fold the elements of this traversable or iterator using the specified associative binary operator.
// The order in which operations are performed on elements is unspecified and may be nondeterministic

scala> val xs = List(1,2,3,4,5)
xs: List[Int] = List(1, 2, 3, 4, 5)

scala> xs.reduce{(x: Int, y: Int) => {println(x + "+" + y); x + y}
     | }
1+2
3+3
6+4
10+5
res1: Int = 15

scala> xs.fold(0){(x: Int, y: Int) => {println(x + "+" + y); x + y}}
0+1
1+2
3+3
6+4
10+5
res4: Int = 15

1.reduce少一次操作
2. reduce和fold不保证顺序，对并行化有益。两个操作数的参数类型是一样的，不能保证保存折叠值的操作数是哪个。
3. *Left/Right是线性遍历，reduce/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

reduceLeft vs foldLeft

def reduceLeft[B >: A](op: (B, A) => B): B
// Applies a binary operator to all elements of this sequence, going left to right.
def foldLeft[B](z: B)(op: (B, A) => B): B
// Applies a binary operator to a start value and all elements of this sequence, going left to right.

scala> xs.reduceLeft{(x: Int, y: Int) => {println(x + "+" + y); x + y}}
1+2
3+3
6+4
10+5
res2: Int = 15

scala> xs.foldLeft(0){(x: Int, y: Int) => {println(x + "+" + y); x + y}}
0+1
1+2
3+3
6+4
10+5
res5: Int = 15

scala> xs.foldLeft(Array.empty[String]){(ys: Array[String], x: Int) => x.toString +: ys}
res23: Array[String] = Array(5, 4, 3, 2, 1)

1. 第一个操作数保存折叠值
2. foldLeft的折叠类型可以是任意类型

reduceRight vs foldRight

def reduceRight[B >: A](op: (A, B) => B): B
// Applies a binary operator to all elements of this sequence, going right to left.
def foldRight[B](z: B)(op: (A, B) => B): B
// Applies a binary operator to all elements of this list and a start value, going right to left.

scala> xs.reduceRight{(x: Int, y: Int) => {println(x + "+" + y); x + y}}
4+5
3+9
2+12
1+14
res3: Int = 15

scala> xs.foldRight(0){(x: Int, y: Int) => {println(x + "+" + y); x + y}}
5+0
4+5
3+9
2+12
1+14
res6: Int = 15

scala> xs.foldRight(Array.empty[String]){(x: Int, ys: Array[String]) => x.toString +: ys}
res29: Array[String] = Array(1, 2, 3, 4, 5)

第二个操作数保存折叠值

reduce*Option

def reduceLeftOption[B >: A](op: (B, A) => B): Option[B]
// Optionally applies a binary operator to all elements of this traversable or iterator, going left to right.
def reduceOption[A1 >: A](op: (A1, A1) => A1): Option[A1]
// Reduces the elements of this traversable or iterator, if any, using the specified associative binary operator.
def reduceRightOption[B >: A](op: (A, B) => B): Option[B]
// Optionally applies a binary operator to all elements of this traversable or iterator, going right to left.

scala> val z = List.empty[Int]
z: List[Int] = List()

scala> z.reduce(_+_)
java.lang.UnsupportedOperationException: empty.reduceLeft
  at scala.collection.LinearSeqOptimized.reduceLeft$(LinearSeqOptimized.scala:135)
  at scala.collection.LinearSeqOptimized.reduceLeft(LinearSeqOptimized.scala:134)
  at scala.collection.TraversableOnce.reduce$(TraversableOnce.scala:208)
  at scala.collection.TraversableOnce.reduce(TraversableOnce.scala:208)
  ... 28 elided

scala> z.reduceLeft(_+_)
java.lang.UnsupportedOperationException: empty.reduceLeft
  at scala.collection.LinearSeqOptimized.reduceLeft$(LinearSeqOptimized.scala:135)
  at scala.collection.LinearSeqOptimized.reduceLeft(LinearSeqOptimized.scala:134)
  ... 28 elided

scala> z.reduceRight(_+_)
java.lang.UnsupportedOperationException: Nil.reduceRight
  at scala.collection.LinearSeqOptimized.reduceRight$(LinearSeqOptimized.scala:140)
  at scala.collection.LinearSeqOptimized.reduceRight(LinearSeqOptimized.scala:139)
  ... 28 elided

scala> z.reduceOption(_+_)
res9: Option[Int] = None

scala> z.reduceLeftOption(_+_)
res12: Option[Int] = None

scala> z.reduceRightOption(_+_)
res13: Option[Int] = None

scala> xs.reduceRightOption(_+_)
res31: Option[Int] = Some(15)

scala> z.fold(0)(_+_)
res14: Int = 0

scala> z.foldLeft(0)(_+_)
res15: Int = 0

scala> z.foldRight(0)(_+_)
res16: Int = 0

参考

http://www.scala-lang.org/api/current/scala/collection/immutable/List.html
http://stackoverflow.com/questions/11319111/fold-and-foldleft-method-difference