减速器(在Clojure中)是否解决了Guy Steele概述的缩放倍数累积问题？

Question

在她的演讲中,Clojure Bodil 的未来提出以下主张:

盖伊斯蒂尔在ICFP上发表了一篇名为" 组织并行执行功能代码"(或者,折叠和折叠考虑稍微有害)的演讲(同样在ACM中).

其中盖伊斯蒂尔在幻灯片70中断言:

一旦你说"第一次SUM = 0",你就被冲洗了.对于并行性,累加器是不可靠的.请注意,foldl和 foldr,虽然功能,从根本上累积.

这有点有趣.所以Bodil说Guy Steele正在呼唤一个问题.然后她声称Rich用Reducers(以及Transducers,它是这种思路的延续)来解决它.在16:11 的Transducers演讲中,我们看到Rich发表了一些特别的论文foldr.

• 鸟 - 建设性功能规划讲座(1988)
• 赫顿 - 关于折叠的普遍性和表现力的教程(1999)

Rich有效地说folds是可组合的 - 你可以用它们来构建其他更高阶的函数,比如map和filter.

我的问题是 - 博迪尔对吗？Rich有没有解决Guy Steele设置的问题？减速器(在Clojure中)是否解决了Guy Steele概述的缩放倍数累积问题？

Answer 1

是的,Reducer确实解决了这个问题,因为他们的语义与Guy Steele所指的折叠类型略有不同(虽然效果在实践中可能非常相似).

foldr并foldl获取单个函数参数,该参数依次应用于集合的每个成员(以及累加器值).正如斯蒂尔所说,它们本质上是顺序的(这就是为什么有"左"和"右"变体的意义).Clojure的clojure.core/reduce功能也是这样的.

clojure.core.reducers/fold另一方面,它有两个函数参数,一个简化函数和一个组合函数.该集合被分成块,每个块使用缩减功能缩小,然后使用组合功能组合这些结果.图形上看起来像这样:

(这个图来自我的七周七并发模型,其中包括一个关于Reducers的部分).

有时,您可以使用单个函数进行缩减和合并(例如,对整数序列求和).但在其他情况下,这是不可能的.

当使用单个函数进行缩小和合并时,clojure.core.reducers/fold当且仅当缩减/合并函数是关联的时,才会给出与顺序折叠相同的结果.