9

在她的演讲中，Clojure Bodil 的未来提出了以下主张：

Guy Steele 在 ICFP 上做了一个演讲，名为为并行执行组织功能代码（或 foldl 和 foldr 被认为有轻微危害）（也在ACM 中）。

Guy Steele 在幻灯片 70 中断言：

只要你说“第一SUM = 0”，你就被灌输了。累加器不利于并行性。请注意foldl和 foldr，虽然是功能性的，但从根本上来说是累积性的。

这很有趣。所以 Bodil 说 Guy Steele 是在说一个问题。然后她声称 Rich 用Reducers（和Transducers是这种思路的延续）解决了这个问题。在16:11的 Transducers 演讲中，我们看到 Rich 提到了一些关于foldr.

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

我的问题是 - Bodil 是对的吗？Rich 解决了 Guy Steele 提出的问题了吗？减速器（在 Clojure 中）是否解决了 Guy Steele 概述的缩放折叠累积问题？

4

2 回答 2

10

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

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

clojure.core.reducers/fold另一方面，它接受两个函数参数，一个归约函数和一个组合函数。集合被分成块，每个块都使用归约函数进行归约，然后使用组合函数组合这些结果。从图形上看，这看起来像这样：

折叠树

（这张图来自我的书《七周内的七种并发模型》，其中包括一个关于 Reducers 的部分）。

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

当使用单个函数进行归约和合并时，clojure.core.reducers/fold当且仅当归约/合并函数是关联的时，将给出与顺序折叠相同的结果。

于 2014-12-08T14:04:14.040 回答
2

关于 reducers 的原始博客文章（Reducers - A Library and Model for Collection Processing）在Simplicity is Opportunityfold部分介绍了该功能。

fold 的主要签名接受一个组合函数、一个归约函数和一个集合，并返回组合集合的归约子段的结果，可能是并行的。

Clojure 数据结构利用了可能的并行性。

当集合适合并行细分时，它会执行此操作。理想的候选者是由树构建的数据结构。Clojure 向量和映射是树，并且基于 ForkJoin 框架具有折叠的并行实现。

如果集合是一个序列，则reduce应用良好的旧功能。

如果底层集合不适合（例如是一个序列）怎么办？fold 只是演变为 reduce，产生相同的语义（如果不是物理）结果。

于 2014-12-08T14:08:36.627 回答