8

我正在通过 Learn You a Haskell 进行工作，并且我在 monoids 部分。在本节中，作者为一棵树定义 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 在适当的幺半群上，但它实际上不能像这样工作，因为 foldl 和 foldr 比幺半群 '+' 和 '*' 作为参数。foldl 和 foldr 实际在哪里实现，它们是如何工作的，为什么定义 foldMap 会导致它们存在？

4

2 回答 2

15

看一下源码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它们组合在一起。现在自同态形成一个幺半群，在 Haskell 中使用Endo: 它memptyis justid和mappendis 来表示.。所以我们可以将其重写为

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 -> mwherem是一个幺半群，并用mappend我们得到组合它，它接受一个类型mappend . f :: a -> (m -> m)的元素并在其上构造一个转换为的函数。然后它使用这个函数折叠结构的所有元素。xamu :: mmappend (f u) k

于 2013-05-26T11:06:14.360 回答
4

来自http://hackage.haskell.org/packages/archive/base/latest/doc/html/src/Data-Foldable.html#Foldable：

class Foldable t where

    ... 

    foldMap :: Monoid m => (a -> m) -> t a -> m
    foldMap f = foldr (mappend . f) mempty

    ...

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

    ...

    foldl :: (a -> b -> a) -> a -> t b -> a
    foldl f z t = appEndo (getDual (foldMap (Dual . Endo . flip f) t)) z

所以你有默认实现（在这种情况下甚至是循环的）。这就是为什么会有评论：“最小的完整定义：foldMap 或 foldr。” 在Foldable类型类的描述中（参见http://hackage.haskell.org/packages/archive/base/latest/doc/html/Data-Foldable.html）

这种技术的一个更简单的例子是Eq类型类，其中(==)和(/=)是根据彼此定义的，但是当然您需要在实例中至少实现它们中的一个（否则您将获得无限循环）。

于 2013-05-26T10:46:04.287 回答