16

我是 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为某种类型实现，我们就 可以免费获得该类型foldrfoldl！” .

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

4

2 回答 2

30

我们从 的类型开始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，是因为 endofunction 是从一种类型到相同类型的函数。）

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

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

我们可以看到它foldEndo匹配它，除了泛化到 anyFoldable和一些参数的重新排序。

在我们开始实现之前，有一个技术难题是b -> b不能直接将Monoid. 为了解决这个问题，我们使用Endonewtype 包装器来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的默认定义。最棘手的可能是Endo . f；如果您对此有疑问，请f不要将其视为二元运算符，而应将其视为具有 type 的一个参数的函数a -> (b -> b)；然后我们用Endo.

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

于 2014-04-27T06:01:56.497 回答
6

foldr 总是可以定义为：

foldr f z t = appEndo (foldMap (Endo . f) t) z

其中 appEndo 和 Endo 只是新类型的解包器/包装器。事实上，这段代码是直接从 Foldable 类型类中提取的。所以，通过定义 foldMap，你会自动得到 foldr。

于 2014-04-27T05:43:58.423 回答