haskell - 是否可以使用单边折叠来实现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 is made of monoids事实上，标准的 haskell 类型类 Foldable 实现了 foldr 和 foldl in just this way

诀窍在于，集合上的自同态集合在函数组合下形成一个幺半群，并以恒等函数作为恒等。

请注意，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)

然后在foldable中，我们看到foldr的定义

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

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

foldMap f ls = fold (map f ls)

其中 fold 是幺半群折叠。如果您有一个名为 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

并删除不必要的括号

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

这是 Daniel Wagner 给出的答案。您可以以类似的方式或通过 foldr 实现 foldl。