scala - 函数式编程(尤其是 Scala 和 Scala API)中的 reduce 和 foldLeft/fold 之间的区别？

Question

为什么Scala和Spark、Scalding等框架都有reduce和 foldLeft ?那么reduce 和有什么区别？和 fold ?

Answer 1

减少与左折叠

在与此主题相关的任何其他 stackoverflow 答案中都没有提到的一个很大的区别是 reduce应该给定一个可交换的幺半群，即一个既可交换又可结合的运算。这意味着操作可以并行化。

这种区别对于大数据/MPP/分布式计算非常重要，这也是为什么reduce的全部原因。甚至存在。收藏可以切碎和reduce可以对每个chunk进行操作，那么reduce可以对每个块的结果进行操作——事实上，分块的级别不需要停止一层深。我们也可以切碎每一块。这就是为什么在给定无限数量的 CPU 的情况下，对列表中的整数求和是 O(log N) 的原因。

如果你只看签名，就没有理由 reduce存在是因为你可以用 reduce 实现你能做的一切与 foldLeft . foldLeft的功能大于 reduce 的功能.

但是你不能并行化 foldLeft ，所以它的运行时间总是 O(N)(即使你输入一个可交换的幺半群)。这是因为假设操作不是可交换的幺半群，因此累积值将由一系列顺序聚合计算。
foldLeft不假设交换性或结合性。关联性提供了拆分集合的能力，而交换性使累积变得容易，因为顺序并不重要(因此聚合每个块的每个结果的顺序并不重要)。严格来说，交换性不是并行化所必需的，例如分布式排序算法，它只是使逻辑更容易，因为您不需要给块排序。

如果您查看 reduce 的 Spark 文档它特别说“......交换和结合二元运算符”

http://spark.apache.org/docs/1.0.0/api/scala/index.html#org.apache.spark.rdd.RDD

这是证明reduce不仅仅是 foldLeft 的特例

scala> val intParList: ParSeq[Int] = (1 to 100000).map(_ => scala.util.Random.nextInt()).par

scala> timeMany(1000, intParList.reduce(_ + _))
Took 462.395867 milli seconds

scala> timeMany(1000, intParList.foldLeft(0)(_ + _))
Took 2589.363031 milli seconds

减少与折叠

现在这是它更接近 FP/数学根源的地方，并且解释起来有点棘手。 Reduce 被正式定义为 MapReduce 范式的一部分，它处理无序集合(多集)，Fold 是根据递归(参见 catamorphism)正式定义的，因此假定集合的结构/序列。

没有fold Scalding 中的方法，因为在(严格的)Map Reduce 编程模型下我们无法定义 fold因为块没有排序和 fold只需要结合性，不需要交换性。

简单地说，reduce无需累积顺序即可工作，fold需要一个累积顺序，正是这个累积顺序需要一个零值，而不是零值的存在区分它们。严格来说reduce应该在一个空集合上工作，因为它的零值可以通过取任意值 x 推导出来。然后解决 x op y = x ，但这不适用于非交换运算，因为可能存在不同的左右零值(即 x op y != y op x )。当然，Scala 不会费心算出这个零值是什么，因为这需要做一些数学运算(这可能是无法计算的)，所以只是抛出一个异常。

似乎(在词源学中经常出现这种情况)这种原始的数学含义已经丢失，因为编程中唯一明显的区别是签名。结果是reduce已成为fold的代名词，而不是保留它在 MapReduce 中的原始含义。现在这些术语经常互换使用，并且在大多数实现中表现相同(忽略空集合)。怪异性会因特殊性而加剧，就像在 Spark 中一样，我们现在将解决这些问题。

所以 Spark 确实有一个 fold ，但是子结果(每个分区一个)的组合顺序(在撰写本文时)与任务完成的顺序相同 - 因此是不确定的。感谢@CafeFeed 指出 fold用途 runJob ，在阅读代码后，我意识到它是不确定的。 Spark 的 treeReduce 造成了进一步的困惑。但没有 treeFold .

结论
reduce之间有区别和 fold即使应用于非空序列。前者被定义为 MapReduce 编程范式的一部分，用于具有任意顺序的集合 ( http://theory.stanford.edu/~sergei/papers/soda10-mrc.pdf )，并且除了给出确定性结果的关联性之外，还应该假设运算符是可交换的。后者是根据原形定义的，并且要求集合具有序列的概念(或递归定义，如链表)，因此不需要可交换运算符。

在实践中，由于编程的非数学性质，reduce和 fold倾向于以相同的方式运行，无论是正确的(如在 Scala 中)还是错误的(如在 Spark 中)。

额外:我对 Spark API 的看法

我的观点是，如果使用术语 fold 可以避免混淆。在 Spark 中完全丢弃。至少 spark 在他们的文档中有一个注释:

This behaves somewhat differently from fold operations implemented for non-distributed collections in functional languages like Scala.