Clojure clojure.core.reducers/fold和Scala fold有什么区别？

Question

我偶然发现Clojure有clojure.core.reducers/fold函数。

另外，Scala有内置的fold函数，但不能理解它们的工作方式是否不同？

Answer 1

我假设你说的是clojure.core.reducers/fold。

Scala在sequences上的默认fold实现非常简单：

collection.fold(identityElem)(binOp)

简单地从identityElem开始，然后顺序地遍历集合，并将二元运算binOp应用于已经累积的结果和当前序列值，例如

(1 to 3).fold(42000)(_ + _)

将导致42000 + 1 + 2 + 3 = 42006。

带完整签名的Clojure的fold

(r/fold n combinef reducef coll)

来自上面提到的包在两个阶段并行工作。首先，它将输入拆分成大小为n的较小组(大约)，然后使用reducef减少每个组，最后使用combinef合并每个组的结果。

主要区别在于，combinef应该同时是零值和二进制文件(Clojure具有多值函数)，并且(combinef) (没有参数)将被调用来为每个分区生成标识元素(因此，this documentation是正确的，而this documentation是错误的)。

也就是说，为了从上面的例子中模拟Scala的折叠，必须编写类似这样的代码：

(require '[clojure.core.reducers :as r])

(r/fold 3 (fn ([] 42000) ([x y] y)) + [1 2 3])

总的来说，Scala的fold

collection.fold(identityElement)(binOp)

reducers/fold可以按如下方式进行模拟：

(r/fold collectionSize (fn ([] identityElem) ([x y] y)) binOp collection)

(请注意，([x y] y)的巧妙设计去掉了第一个参数，这是故意的)。

我猜这个接口并不打算用于任何非么半群的零二进制操作，这就是为什么Scala的fold很难用Clojure的fold来模拟的原因。如果你想要一些像Scala的fold那样的东西，可以在Clojure中使用reduce。

编辑

哦，等等。文档实际上说明了

组合函数必须是关联的，并且在不带参数的情况下调用时，(组合函数)必须生成其标识元素

也就是说，我们实际上被迫使用monoid作为combinef，所以上面的42000, ([x y] y)-example实际上是无效的，并且行为实际上是未定义的。从严格的技术意义上讲，我以某种方式获取42006的事实是一个技巧，它依赖于库函数的未定义行为来获得所需的结果42006。

考虑到这些额外的信息，我根本不确定Scala的fold能否被Clojure的core.reducers/fold模拟。Clojure的fold似乎被限制为使用monoid进行缩减，而Scala的折叠更接近于一般的List折叠，代价是并行性。

Answer 2

clojure.core.reducers命名空间是专为并行处理大型数据集而设计的实现。你可以在这里找到完整的文档：

https://clojure.org/reference/reducers。

(r/fold reducef coll)
(r/fold combinef reducef coll)
(r/fold n combinef reducef coll)

r/fold接受一个可简化的集合，并将其划分为大约n个元素(默认为512个)的组。使用reducef函数对每个组进行缩减。在不带任何参数的情况下调用reducef函数，以在每个分区中生成一个标识值。然后使用combinef (缺省为reducef)函数对这些缩减的结果进行缩减。在不带参数的情况下调用时，(combinef)必须生成它的标识元素-这将被多次调用。操作可以并行执行。结果将保持秩序。

在你的机器达到极限之前，你应该坚持使用基本的reduce函数：

https://clojuredocs.org/clojure.core/reduce

这在本质上与Scala的fold函数相同：

(reduce + 0 [1 2 3 4 5]) => 15

其中函数签名为：

(reduce <op> <init-val> <collection-to-be-reduced> )