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中的二叉樹嗎？

回答

相關問題