是否可以使用无边折叠实现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是由monoids组成的事实上,标准的haskell类型类Foldable实现foldr并且foldl 就是这样

诀窍在于集合上的一组内同态在函数组合下形成一个monoid,其中identity作为标识.

注意尽管如此foldr并且foldl本质上是顺序的.所以,这一招已经放弃你有任何并行在你的实现fold和map.本质上,foldrinto foldMap的编码是将延迟顺序计算编码成可能无序的计算.这就是为什么我鼓励在可能的情况下使用foldMapover foldr- 它在可能的情况下支持隐含的并行性,但在表达能力方面是相同的.

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

我们定义了一组endo态射 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

这个使用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

并丢弃不必要的parens

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

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