haskell - Tree 实现 Foldable FoldMap 时 Foldr/Foldl 是免费的吗？

Question

我是 Haskell 的初学者，正在从“Learn You a Haskell”学习。

我不明白 Foldable 的 Tree 实现。

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  

引用 LYAH 的话:“因此，如果我们只为某种类型实现 foldMap， 我们会得到 foldr 和 foldl免费使用该类型!”。

有人能解释一下吗？我不明白现在如何以及为何免费获得 foldr 和 foldl...

Answer 1

我们从 foldMap 的类型开始:

foldMap :: (Foldable t, Monoid m) => (a -> m) -> t a -> m

foldMap 的工作原理是将 a -> m 函数映射到数据结构上，然后运行它，使用 mappend< 将元素粉碎为单个累积值.

接下来，我们注意到，给定某种类型 b，b -> b 函数形成一个幺半群，其中 (.) 为它的二元运算(即 mappend)和 id 作为标识元素(即 mempty)。如果您还没有遇到过它，id 定义为id x = x)。如果我们将 foldMap 专门用于该幺半群，我们将得到以下类型:

foldEndo :: Foldable t => (a -> (b -> b)) -> t a -> (b -> b)

(我将函数命名为foldEndo，因为内函数是从一种类型到同一类型的函数。)

现在，如果我们查看列表的签名foldr

foldr :: (a -> b -> b) -> b -> [a] -> b

我们可以看到 foldEndo 与它匹配，除了对任何 Foldable 的泛化以及对参数的一些重新排序。

在我们开始实现之前，有一个技术复杂性，即 b -> b 无法直接成为 Monoid 的实例。为了解决这个问题，我们使用 Data.Monoid 中的 Endo 新类型包装器:

newtype Endo a = Endo { appEndo :: a -> a }

instance Monoid (Endo a) where
        mempty = Endo id
        Endo f `mappend` Endo g = Endo (f . g)

根据Endo编写，foldEndo只是专门的foldMap:

foldEndo :: Foldable t => (a -> Endo b) -> t a -> Endo b

因此我们将直接跳转到foldr，并根据foldMap定义它。

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

这是默认定义you can find in Data.Foldable 。最棘手的部分可能是 Endo 。 f;如果您对此有困难，请不要将 f 视为二元运算符，而是将其视为类型为 a -> (b -> b) 的一个参数的函数；然后我们用 Endo 包装生成的内函数。

对于foldl，推导本质上是相同的，除了我们使用不同的内函数幺半群，以flip (.)作为二元运算(即我们以相反的方向组合函数)。