是否可以使用无阴影折叠来实现foldl/foldr

Question

所谓无尾折叠，我指的是关联运算符的假设基元折叠操作，它不保证任何排序。也就是说，(fold + 0 [a b c d])可以是(+ (+ a b) (+ c d))或(+ (+ (+ a b) c) d)。

考虑到这个操作是可融合的、高度可并行化的和通用的，我考虑将它与map和concat一起作为我的非递归极简主义语言的唯一列表基元。我已经用它实现了大多数列表函数，但没有实现侧面折叠foldl/foldr本身。有可能吗？

Answer 1

如果您有fold和map，那是通用的。这里的口号是foldr是由monoid组成的。事实上，标准haskell类型类Foldable就是这样实现foldr和foldl的

技巧是，集合上的自同态集在以恒等函数为恒等式的函数组合下形成了一个单胚。

注意，foldr和foldl本质上是连续的。因此，这个技巧必须放弃fold和map实现中的任何并行性。从本质上讲，将foldr编码为foldMap是将延迟的顺序计算编码为潜在的无序计算。这就是为什么我鼓励在可能的情况下使用foldMap而不是foldr——当可能的时候，它支持隐含的视差，但在表达能力上是等效的。

编辑：把所有东西放在一个地方

我们定义了a上的自同态集

newtype Endo a = Endo { appEndo :: a -> a }
instance Monoid (Endo a) where
mempty = Endo id
Endo f `mappend` Endo g = Endo (f . g)

然后在可折叠中，我们看到了foldr的定义

foldr f z t = appEndo (foldMap (Endo . f) t) z

它使用类型为Monoid m => (a -> m) -> t a -> m的foldMap(其中t是我们正在折叠的集合，从现在起，我们可以假设它是一个列表，给出Monoid m => (a -> m) -> [a] -> m，相当于

foldMap f ls = fold (map f ls)

其中CCD_ 27是一元折叠。如果你有一个叫fold' :: (a -> a -> a) -> a -> [a] -> a的无序折叠，那么它就是

fold = fold' mappend mempty

所以

foldr f z t = appEndo (foldMap (Endo . f) t) z
= appEndo (fold (map (Endo . f) t)) z
= appEndo (fold' mappend mempty (map (Endo . f) t)) z
= appEndo (fold' ((Endo f) (Endo g) -> Endo (f . g) (Endo id) (map (Endo . f) t)) z

可以进一步简化为

foldr f z t = (fold' (.) id (map f t)) z

并丢弃不必要的parens

foldr f z t = fold' (.) id (map f t) z

这就是丹尼尔·瓦格纳给出的答案。您可以用类似的方式或通过foldr实现foldl。

Answer 2

foldr f z xs = fold (.) id (map f xs) z

例如，在ghci:中

*Dmwit Debug.SimpleReflect> let foldr' f z xs = foldb (.) id (map f xs) z
*Dmwit Debug.SimpleReflect> foldr' f z [w,x,y]
f w (f x (f y z))
*Dmwit Debug.SimpleReflect> foldr f z [w,x,y]
f w (f x (f y z))