haskell - Haskell 中的二叉树的 Foldl/foldr 实现来自哪里？

Question

我正在学习 Learn You a Haskell，并且正在研究幺半群部分。在本节中，作者为树定义了foldMap方法，如下:

instance F.Foldable Tree where  
    foldMap f Empty = mempty  
    foldMap f (Node x l r) = F.foldMap f l `mappend`  
                             f x           `mappend`  
                             F.foldMap f r  

效果很好，而且非常出色。然而，他随后表示“现在我们的树类型有了可折叠实例，我们可以免费获得foldr和foldl!”并显示以下代码:

testTree = Node 5  
            (Node 3  
                (Node 1 Empty Empty)  
                (Node 6 Empty Empty)  
            )  
            (Node 9  
                (Node 8 Empty Empty)  
                (Node 10 Empty Empty)  
            )  

ghci> F.foldl (+) 0 testTree  
42  
ghci> F.foldl (*) 1 testTree  
64800  

现在我很困惑。没有任何地方为 Trees 编写foldl或foldr的实现。这些函数的工作方式似乎有点像折叠映射，但是将初始累加器作为树的头部，然后在适当的幺半群上进行折叠映射，但它实际上不能像这样工作，因为foldl和foldr采用比幺半群“+”和“*”作为参数。 Foldl和foldr实际在哪里实现，它们如何工作，以及为什么定义foldMap会导致它们存在？

Answer 1

看看 source of Foldable 。它使用 foldMap 定义 foldr ，反之亦然，因此定义对您来说更方便的一个就足够了(尽管同时实现这两种方法可以给您带来一些性能优势):

foldr :: (a -> b -> b) -> b -> t a -> b
foldr f z t = appEndo (foldMap (Endo . f) t) z

让我们通过一个例子来看看这里发生了什么。假设我们要折叠一个列表[i, j, k]。 f 和 z 的右侧折叠是

f i (f j (f k z))

这也可以表示为

(f i . f j . f k) z

使用f，我们将列表中的每个元素转换为 endomorphism在 b 上并将它们组合在一起。现在自同态形成了一个幺半群，它在 Haskell 中使用 Endo 来表达:它的 mempty 只是 id ，而 mappend 是.。所以我们可以将其重写为

appEndo (Endo (f i) `mappend` Endo (f j) `mappend` Endo (f k)) z

我们可以将内部部分表示为foldMap (Endo . f) [i, j, k]。

总结:关键思想是某些域上的自同态形成幺半群，并且 f::a -> (b -> b) 映射 a 的元素转化为 b 上的自同态。

<小时/>

相反表示为

foldMap f = foldr (mappend . f) mempty

这里我们有 f::a -> m，其中 m 是一个幺半群，并将其与 mappend 组合，我们得到 映射。 f::a -> (m -> m)，它采用 a 类型的元素 x 并在 m 上构造一个函数code> 将 u::m 转换为 mappend (fu) k。然后它使用此函数折叠结构的所有元素。