为什么 scala reduce() 和 reduceLeft() 以相同的方式减少值的序列？

Question

如果我运行:

List(1, 4, 3, 9).reduce {(a, b) => println(s"$a + $b"); a + b}

结果是：

1 + 4
5 + 3
8 + 9

但是，如果我使用 reduceLeft 而不是 reduce，它还会打印：

1 + 4
5 + 3
8 + 9

我认为 reduce 以这种方式减少值的顺序：

(1+4) + (3+9)
(5) + (12)
(17)

reduceLeft 和 reduce 之间的真正区别是什么？

Answer 1

区别是：

reduce 允许以任何顺序减少；对于 List，它恰好与 reduceLeft 相同，因为它更有效率（和 it's the default implementation for IterableOnceOps subtypes，所以它们中的大部分都是相同的）。对于另一个集合，它可能相当于 reduceRight，对于树类型，它可能比您预期的要多。
不同类型的签名：
```
reduce[B >: A](op: (B, B) => B): B
```
对比
```
reduceLeft[B >: A](op: (B, A) => B): B
```
因为 reduceLeft 中 op 的第一个参数始终是调用它的集合的一个元素，但对于 reduce 它可能是递归 reduce 呼叫.

Answer 2

看看两个函数的类型：

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

注意，在reduceLeft中op的第二个参数是A（与元素类型相同），而在reduce中是B（与 return 值相同）。

这是一个重要的区别。 reduce 中的操作必须是 associative，这意味着你可以将列表分成几个部分，分别对每个部分应用操作，然后再次对结果应用组合。

当您想并行执行操作时，这一点很重要：reduce 可以并行应用于列表的不同部分，然后合并结果。

reduceLeft 另一方面，只能按顺序工作（从左到右，顾名思义），操作不必是关联的，并且可以期望它的第二个参数总是一个元素序列（以及第一个 - 到目前为止的操作结果）；

考虑

    val sum = (1 to 100).reduce(_ + _)

这会产生与 (1 to 100).reduceLeft(_ + _) 相同的结果，只是前者可以并行化。另一方面：

    val strings = (1 to 100).reduceLeft[Any](_.toString + ";" + _.toString)

不应该写成 reduce （即使在这个人为的例子中，只要你坚持串行处理，它就可以，甚至会工作），因为结果取决于顺序元素被馈送到操作中。

Why does scala reduce() and reduceLeft() reduce the sequence of the values in the same way?