clojure - reducer (在 Clojure 中)是否解决了 Guy Steele 概述的缩放文件夹累积问题？

Question

在她的演讲中The Future Of Clojure博迪尔提出以下主张:

Guy Steele gave a talk at ICFP called Organizing Functional Code for Parallel Execution (or, foldl and foldr Considered Slightly Harmful) (Also in ACM).

Guy Steele 在幻灯片 70 中断言:

As soon as you say “first, SUM = 0” you are hosed. Accumulators are BAD for parallelism. Note that foldl and foldr, though functional, are fundamentally accumulative.

这有点有趣。所以博迪尔说盖伊·斯蒂尔提出了一个问题。然后她声称里奇用Reducers来解决这个问题。 (和 Transducers 是这种思路的延续)。在 the Transducers talk在 16:11，我们看到 Rich 指出了一些有关 foldr 的特定论文。

• 鸟 - Lectures on Constructive Functional Programming (1988)
• 赫顿 - A tutorial on the universality and expressiveness of fold (1999)

Rich 有效地表示 fold 是可组合的 - 您可以使用它们来构建其他高阶函数，例如 map 和 filter。

我的问题是 - Bodil 是对的吗？里奇解决了盖伊·斯蒂尔提出的问题了吗？ reducer(在 Clojure 中)是否解决了 Guy Steele 概述的缩放文件夹累积问题？

Answer 1

是的，reducers 确实解决了这个问题，因为它们的语义与 Guy Steele 所指的折叠类型略有不同(尽管在实践中效果可能非常相似)。

foldr 和 foldl 采用单个函数参数，该参数依次应用于集合的每个成员(以及累加器值)。正如斯蒂尔所说，它们本质上是连续的(这就是为什么有“左”和“右”变体是有意义的)。 Clojure 的 clojure.core/reduce 函数也以这种方式工作。

另一方面，

clojure.core.reducers/fold 采用两个函数参数，一个缩减函数和一个组合函数。集合被分成 block ，使用归约函数对每个 block 进行归约，然后使用组合函数组合这些结果。从图形上看，它看起来像这样:

(此图来 self 的书 Seven Concurrency Models in Seven Weeks ，其中包含有关 reducer 的部分)。

有时，您可以使用单个函数进行归约和组合(例如对整数序列求和)。但在其他情况下，这是不可能的。

当使用单个函数进行缩减和组合时，当且仅当缩减/组合函数具有关联性时，clojure.core.reducers/fold 才会给出与顺序折叠相同的结果。