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

我正在学习通过学习你一个Haskell，并且我正在关于monoids的部分。在本节中，作者定义了一棵树的foldMap方法，如下所示：Foldable的foldl/foldr实现来自haskell中的二叉树吗？

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会使它们存在？

来源

2013-05-26 MYV

你看过Data.Foldable的源代码吗？可折叠类中的定义应该足以提供足够的信息来回答你的问题。 – 2013-05-26 08:58:05

Haskell类型类可以使用其他方法对某些方法进行默认实现。在这里它们类似于mixin如何在其他语言中工作。例如，在Ruby中，只需要定义<=>就可以访问Comparable的其余方法。 – danidiaz

[Foldr/Foldl免费实现折叠折叠图时可能的重复？]（http://stackoverflow.com/questions/23319683/foldr-foldl-for-free-when-tree-is-implementing-foldable-foldmap ） –

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

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的endomorphism和撰写在一起。现在，自同构形成一个幺半群，它在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。然后它使用这个函数折叠结构的所有元素。

来源

2013-05-26 11:06:14

当你说“... ...成为'b'上的自同态”时，你不会从列表'[a，b，c]'引用'b'，而是从'foldr'引用'b' ::（a - > b - > b）...。也许用'[j，k，l]'作为例子的列表会让你对新手的解释更清楚 – Rolf

从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-26 10:46:04 Landei

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

回答

相关问题