可以将foldr用作MapReduce吗？

Question

我在想,当你做MapReduce时,你正在改变你的数据主义者,然后使用reduce函数对你想要的转换数据做任何事情.我想我也可以这样做foldr.做什么的时候foldr (filterfun . mapfun) [].我可以说Haskell的foldr与mapreduce相同吗？或者我错过了什么？

Answer 1

不完全的.正如Alec的评论所指出的那样,foldr不允许减少重新排序或并行化.例如,如果你有

foldr (+) 0 [1,2,3,4]

那就是

1 + (2 + (3 + 4))

实现foldr不能分开容器并分别对每一半求和,因为你只是给它一个函数a -> b -> b和一个值b.除了将它应用于元素和累加器之外,它不能对该函数执行任何操作.

foldMap :: (Foldable f, Monoid m)
        => (a -> m) -> f a -> m

另一方面,非常多mapReduce.由于Monoid约束带有关联性声明,你可以编写一个foldMap减少容器的前半部分和后半部分,然后将它们与它们一起混合<>.

foldr(in Data.Foldable)的默认实现实际使用foldMap:

foldr c n xs = appEndo (foldMap (Endo . c) xs) n

也就是说,它将每个元素转换为一个函数 ; 这些功能都是由这些功能组成的(组合形成一个具有id其身份的幺半群),并将结果应用于种子.但是,您不能对中间函数执行任何有用的操作!