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

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

有件事我不明白Tree实施Foldable.

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 and foldl该类型免费!".

有人可以解释一下吗？我不明白我如何以及为什么会得到foldr and foldl现在免费...

我们从类型开始foldMap:

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

foldMap通过映射来工作a -> m对数据结构进行函数处理，然后运行它，将元素分解为单个累加值mappend.

接下来，我们注意到，给定某种类型b, the b -> b函数形成一个幺半群，其中(.)作为其二元运算（即mappend) and 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。为了解决这个问题，我们使用Endo新类型包装器来自Data.Monoid反而：

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

这是默认定义你可以找到Data.Foldable http://hackage.haskell.org/package/base-4.6.0.1/docs/src/Data-Foldable.html。最棘手的一点可能是Endo . f;如果你遇到困难，请考虑f不是作为二元运算符，而是作为具有类型的一个参数的函数a -> (b -> b);然后我们将得到的内函数包装为Endo.

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