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

Question

我发现 Clojure 有 clojure.core.reducers/fold 功能。

Scala 也有内置的 fold 函数，但无法理解它们的工作方式是否不同？

Answer 1

我假设您正在谈论 clojure.core.reducers/fold .

Scala 的默认 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 的折叠

collection.fold(identityElement)(binOp)

可以通过reducers/fold来模拟，如下所示:

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

(注意 ([x y] y) 装置丢弃了第一个参数，这是故意的)。

我猜这个接口(interface)不适合与任何非幺半群的零二进制操作一起使用，这就是为什么 Scala 的 fold 很难使用 Clojure 的 fold< 进行模拟的原因。如果您想要像 Scala 的 fold 那样的行为，请在 Clojure 中使用 reduce。

---

编辑

哦，等等。该文档实际上指出

combinef must be associative, and, when called with no arguments, (combinef) must produce its identity element

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

考虑到这些额外的信息，我不确定 Scala 的 fold 是否可以由 Clojure 的 core.reducers/fold 模拟。 Clojure 的折叠似乎仅限于使用幺半群进行约简，而 Scala 的折叠更接近于一般的列表变形，但代价是并行性。