haskell - Haskell中的二叉树的Foldable的foldl/folder实现来自哪里？

我正在通过“了解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

哪个工作正常，完全是baller。但是，他然后说:“现在我们为树类型提供了一个Foldable实例，我们免费获得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

现在我很困惑。 foldl或为Trees编写的foldr的实现都没有。这些功能似乎像foldmap一样工作，但是将初始累加器放在树的头部，然后将foldMapping放在适当的monoid上，但实际上不能像这样工作，因为foldl和foldr接受的通用功能比以等号“+”和“*”作为参数。 foldl和foldr实际在哪里实现，它们如何工作，为什么定义foldMap导致它们存在？

最佳答案

看看source of 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上的endomorphism并将它们组合在一起。现在，内同态形成一个类同体，在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是一个monoid，并将其与mappend组成，我们得到mappend . f :: a -> (m -> m)，它接受类型为x的a元素，并在m上构造一个函数，将u :: m转换为mappend (f u) k。然后，它使用此功能折叠结构的所有元素。