foldable的foldl/foldr实现来自haskell中的二叉树？

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的实现.这些函数看起来有点像foldmap,但是将初始累加器作为树的头部,然后将foldMapping放在适当的monoid上,但它实际上不能像这样工作,因为foldl和foldr占用的功能比monoids'+'和'*'作为参数.foldl和foldr实际上在哪里实现,它们如何工作,以及为什么定义foldMap会使它们存在？

Answer 1

只要看看它的来源Foldable.它定义foldr使用foldMap,反之亦然,所以它足以定义一个更方便的(虽然实现它们可以给你一些性能优势):

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,我们转换列表中的每个元素为自同态上b,撰写在一起.现在,同态形成一个独异,这是在使用哈斯克尔表示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我们得到的mappend . f :: a -> (m -> m),这需要一个元素x类型a和构造函数上m是转换u :: m成mappend (f u) k.然后它使用此函数折叠结构的所有元素.