首页 文章

foldable的foldl / foldr实现来自haskell中的二叉树？

提问于
浏览 次
8

我正在通过Learn You a 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

哪个工作正常，完全是芭蕾舞者 . 然而，他接着说：“现在我们的树型有一个可折叠的实例，我们可以免费获得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放在适当的monoid上，但它实际上不能像这样工作，因为foldl和foldr比一般函数更多monoids''和'*'作为参数 . foldl和foldr实际上在哪里实现，它们如何工作，为什么定义foldMap会导致它们存在？

haskell tree fold monoids

2 回答

  • 14

    看看source of Foldable . 它使用 foldMap 定义了 foldr ，反之亦然，所以它足以定义一个更方便你的（虽然实现它们可以给你一些性能优势）：

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

    让's examine what happens here on an example. Let'说我们即将折叠列表 [i, j, k] . 右侧折叠 f 和 z 是

    f i (f j (f k z))

    这可以替代地表示为

    (f i . f j . f k) z

    使用 f ，我们将列表中的每个元素转换为 b b 并将它们组合在一起 . 现在，endomorphisms形成一个monoid，它在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 是一个幺半群，用 mappend 组成它我们得到 mappend . f :: a -> (m -> m) ，它取一个 a 类型的元素 x 并在 m 上构造一个函数，将 u :: m 转换为 mappend (f u) k . 然后它使用此函数折叠结构的所有元素 .

    回复于
  • 3

    来自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

    所以你有默认的实现（在这种情况下甚至是圆形） . 这就是为什么有一条评论："Minimal complete definition: foldMap or foldr."在 Foldable 类型类的描述中（见http://hackage.haskell.org/packages/archive/base/latest/doc/html/Data-Foldable.html）

    这个技术的一个更简单的例子是 Eq 类型类，其中 (==) 和 (/=) 是相互定义的，但当然你需要在一个实例中至少实现其中一个（否则你会得到一个无限循环） .

    回复于

相关问题