scala reduce和Fold

宗政永望

2023-12-01

reduce

reduce表示将列表，传入一个函数进行聚合运算。

reduce源码

[A1 >: A]：reduce的参数A1必须为调用reduce数据集元素类型的子集
reduceLeft(op)：将匿名函数op传递给reduceLeft,底层调用reduceLeft实现
op: (A1, A1) => A1：第一个A1为当前聚合后的变量，第二个A1为当前要聚合的元素。最终返回A1类型的变量
reduce最终将原数据集聚合后生成一个元素

  def reduce[A1 >: A](op: (A1, A1) => A1): A1 = reduceLeft(op)

reduceLeft源码

底层利用尾递归实现。调用reduce的数据集为空时抛出异常

实现过程：

var first = true：定义标记为first为true
var acc: B = 0.asInstanceOf[B]：声明一个个泛型B类型相同的变量（这里用到了擦拭法，直接写0.asInstanceOf[String]会报错）
第一个元素时，将第一个元素的值赋给acc。同时将标记为置为false
从第二个元素开始，进行递归调用匿名函数op。直到遍历完整个源数据集
- 将第一个元素和第二个元素进行操作，结果赋值给第一个元素，作为第一次聚合结果
- 将第三个元素和第一次聚合结果进行操作，将结果赋给第一个元素，作为第二次聚合结果
- 将第四个元素。。。。。

 /** Applies a binary operator to all elements of this $coll,
   *  going left to right.
   *  $willNotTerminateInf
   *  $orderDependentFold
   *
   *  @param  op    the binary operator.
   *  @tparam  B    the result type of the binary operator.
   *  @return  the result of inserting `op` between consecutive elements of this $coll,
   *           going left to right:
   *           {{{
   *             op( op( ... op(x_1, x_2) ..., x_{n-1}), x_n)
   *           }}}
   *           where `x,,1,,, ..., x,,n,,` are the elements of this $coll.
   *  @throws UnsupportedOperationException if this $coll is empty.   */
  def reduceLeft[B >: A](op: (B, A) => B): B = {
    if (isEmpty)
      throw new UnsupportedOperationException("empty.reduceLeft")

    var first = true
    var acc: B = 0.asInstanceOf[B]

    for (x <- self) {
      if (first) {
        acc = x
        first = false
      }
      else acc = op(acc, x)
    }
    acc
  }

示例

scala> val a = List(1,2,3,4,5,6,7,8,9,10)
a: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)

//集合中第一个元素赋给x，第二个赋给y
//相加后的元素赋给x，第三个元素赋给y
//以此类推
scala> a.reduce((x,y) => x + y)
res5: Int = 55

// 第一个下划线表示第一个参数，就是历史的聚合数据结果
// 第二个下划线表示第二个参数，就是当前要聚合的数据元素
scala> a.reduce(_ + _)
res53: Int = 55

reduceRight源码

源数据集为空，则抛出异常
源数据集不为空，从右侧开始递归

  def reduceRight[B >: A](op: (A, B) => B): B = {
    if (isEmpty)
      throw new UnsupportedOperationException("empty.reduceRight")

    reversed.reduceLeft[B]((x, y) => op(y, x))
  }

```vbnet
 (x, y) => op(y, x) x，y位置互换
例：list.reduceRight(_-_) =》过程：
List(1,4,3,5,3) = 》List(3,5,3,4,1)=》5-3=》3-(5-3)=》4-(3-(5-3))=》1-(4-(3-(5-3))) 小括号内的结果，每次都放在后面一个位置

reduceLeftOption源码

源数据将为空则返回None
源数据集不为空则调用reduceLeft，将操作Op传递给reduceLeft

  def reduceLeftOption[B >: A](op: (B, A) => B): Option[B] =
    if (isEmpty) None else Some(reduceLeft(op))

reduceRightOption源码

源数据将为空则返回None
源数据集不为空则调用reduceLeft，将匿名函数Op传递给reduceRight

  def reduceRightOption[B >: A](op: (A, B) => B): Option[B] =
    if (isEmpty) None else Some(reduceRight(op))

总结

从源码上看：干活的函数是reduceLeft。reduceLeft底层是利用尾递归实现功能
reduce的初始值为源数据第一个或者最后一个元素
调用reduce的数据集为空时，会抛出异常：throw new UnsupportedOperationException("empty.reduceLeft")
reduce相关函数最后返回或者聚合生成一个元素（源数据集还在）
reduce最后聚合生成的元素类型与源数据类型一致

var acc: B = 0.asInstanceOf[B]

将foldLeft放入源文件并进行编译，以打印出中间代码阶段：

./scalac -Xprint:icode X.scala

然后你得到…

def reduceLeft($this: X, op$1: Function2): java.lang.Object = {
  if ($this.isEmpty())
    scala.sys.`package`.error("Bad")
  else
    ();
  var first$1: scala.runtime.BooleanRef = new scala.runtime.BooleanRef(true);
  var acc$1: scala.runtime.ObjectRef = new scala.runtime.ObjectRef(scala.Int.box(0));
  $this.foreach({
    (new anonymous class X$$anonfun$reduceLeft$1($this, op$1, first$1, acc$1): Function1)
  });
  acc.elem
};

原文链接

fold

给定初始值，将源数据集和初始值一起进行折叠

fold源码

fold底层调用foldLeft(),foldLeft底层利用foreach实现。但是fold无序，为什么无序目前我还没搞清楚
fold相关函数都是柯里化函数
/: ( )和:()是foldLeft和foldRight的快速写法，斜杠前写初始值
每次处理完的数据都赋值给集合外的元素，然后继续和后面的元素一起被操作

示例

scala> (0 /: List("1", "2", "3")) {(sum, elem) => sum + elem.toInt}
res2: Int = 6
scala> (0 /: List("1", "2", "3")) {_ + _.toInt}
res3: Int = 6
scala> (List("1", "2", "3") :\ 0) {(elem, sum) => elem.toInt + sum}
res13: Int = 6
scala> (List("1", "2", "3") :\ 0) {_.toInt + _}
res14: Int = 6

源码

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

 def :\[B](z: B)(op: (A, B) => B): B = foldRight(z)(op)

def foldLeft[B](z: B)(op: (B, A) => B): B = {
  var result = z
  this 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))

解析

从源码上看，fold底层实现是利用foreach
首先将第一个B类型的参数z赋值给变量result
然后源数据集调用foreach（如List.foreach()，这里的this foreach 和this.foreach含义相同）
- 在第一次调用foreach中，调用匿名函数op处理result和源数据集的某个元素。
- 将Op的处理结果作为返回值赋值给result
利用foreach处理源数据集的每一个元素，重复上面第一次调用的过程
最后将foreach处理的结果，作为fold的结果

fold和foldLeft（存疑）

理论上fold和foldLeft一模一样，实际上fold可能是乱序的，foldLeft是从左到右执行。
foldLeft可以返回与源数据集不同的类型，而fold则可能报错。

scala> val ls = List("1","2","3")
ls: List[String] = List(1, 2, 3)

scala> ls.foldLeft(0)(_+_.toInt)
res13: Int = 6

scala> ls.fold(0)(_+_.toInt)
<console>:13: error: value toInt is not a member of Any
       ls.fold(0)(_+_.toInt)
                      ^
scala> ls.foldRight(0)(_+_.toInt)
<console>:13: error: type mismatch;
 found   : String
 required: Int
       ls.foldRight(0)(_+_.toInt)

从上面结果可以看到，当给fold的初始值可源数据类型不一致时，会出问题

网上的解释大多是：fold内部乱序。从源码上此处我没有搞明白。

下面是网上的解释
这是因为fold函数不讲究折叠顺序，foldLeft是这样结合的：

((0 + "1".toInt) + "2".toInt) + "3".toInt

而fold函数是乱序，有可能像上面这样，也有可能是下面这样或其他不可预测的顺序：

(0 + "2".toInt) + ("1" + "3".toInt).toInt

reduce和fold区别

初始值
- Reduce初始值是集合元素的头或尾（left或者right）
- Fold必须手动指定初始值
空集合操作
- Reduce进行空集合操作会抛异常
- Fold进行空集合操作结果为初始值
返回值
- Reduce最终聚合的元素必须和调用Reduce方法的集合中元素一致
- Fold最终折叠得到的元素类型可以和调用Fold中的元素不一致(使用FoldLeft)
底层实现
- Reduce底层采用尾递归实现
- Fold底层采用foreach实现