Haskell/Foldable

Foldable 型別類提供對列表摺疊 (foldr 及其朋友) 的泛化，以及從它派生到任意資料結構的操作。除了非常有用之外，Foldable 是一個很好的例子，說明 monoid 如何幫助制定良好的抽象。

解構 foldr

本段將介紹 foldMap 作為 foldr 的替代。我們將展示如何用前者實現後者。foldr 是一個非常繁忙的函式 - 在第一個函式箭頭兩側有 2 個二元函式，它們型別都使用 2 個變數。

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

如果我們要泛化 foldr，那麼使用更簡單的東西來處理，或者至少能夠將其分解成更簡單的元件，會比較方便。這些元件會是什麼呢？

對列表摺疊的一個粗略描述是，它包括遍歷列表元素，並將它們與一個二元函式組合起來。我們碰巧知道一個型別類，它完全是關於組合成對的值：Monoid。如果我們取 foldr f z ...

a `f` (b `f` (c `f` z)) -- foldr f z [a,b,c]

... 並使 f = (<>) 和 z = mempty ...

a <> (b <> (c <> mempty)) -- foldr (<>) mempty [a,b,c]

... 我們得到 mconcat = foldr mappend mempty，它是一個更簡單、更專業的 foldr，我們不需要指定組合函式或初始累加器，因為我們只使用 mappend（即 (<>)）和 mempty。

mconcat :: Monoid m => [m] -> m

mconcat 足夠好地捕捉了 foldr 的組合所有元素方面，並且涵蓋了它的幾個用例。

GHCi> mconcat ["Tree", "fingers"] -- concat
"Treefingers"

很不錯 - 但我們肯定不想只限於使用 Monoid 例項來摺疊。改進這種情況的一種方法是意識到我們可以使用 mconcat 來摺疊具有任何型別元素的列表，只要我們有一個函式將它們轉換為某些 Monoid 型別。

foldMap :: Monoid m => (a -> m) -> [a] -> m
foldMap g = mconcat . fmap g

這已經讓事情變得更有意思了。

GHCi> foldMap Sum [1..10]
Sum {getSum = 55}

到目前為止一切順利，但似乎我們仍然無法使用任意的組合函式來摺疊。然而，事實證明，任何 適合 foldr 簽名的二元函式都可以用來將值轉換為 Monoid 型別！訣竅是將傳遞給 foldr 的組合函式看作是單個引數的函式...

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

... 並利用 b -> b 函式在組合下形成 monoid 的事實，以 (.) 作為 mappend，以 id 作為 mempty 。相應的 Monoid 例項可以透過 Data.Monoid 中的 Endo 包裝器獲得 。

newtype Endo b = Endo { appEndo :: b -> b }

instance Monoid Endo where
    mempty                  = Endo id
    Endo g `mappend` Endo f = Endo (g . f)

我們現在可以定義...

foldComposing :: (a -> (b -> b)) -> [a] -> Endo b
foldComposing f = foldMap (Endo . f)

... 它從每個元素建立一個 b -> b 函式，並將它們全部組合起來。

Endo (f a) <> (Endo (f b) <> (Endo (f c) <> (Endo id))) -- foldComposing f [a,b,c]
Endo (f a . (f b . (f c . id))) 
-- (<>) and (.) are associative, so we don't actually need the parentheses.

-- As an example, here is a step-by-step evaluation:
foldComposing (+) [1, 2, 3]
foldMap (Endo . (+)) [1, 2, 3]
mconcat (fmap (Endo . (+)) [1, 2, 3]) 
mconcat (fmap Endo [(+1), (+2), (+3)])
mconcat [Endo (+1), Endo (+2), Endo (+3)]
Endo ((+1) . (+2) . (+3))
Endo (+6)

如果我們將該函式應用於某個 b 值...

foldr :: (a -> (b -> b)) -> b -> [a] -> b
foldr f z xs = appEndo (foldComposing f xs) z

... 我們最終會恢復 foldr。這意味著我們可以用 foldMap 來定義 foldr，foldMap 是一個更簡單，因此更容易推理的函式。因此，foldMap 是 Foldable 的概念核心，Foldable 類將 foldr 泛化到任意資料結構。

練習
為列表編寫 foldMap 的兩種實現：一種用 foldr 實現，另一種用顯式遞迴實現。

Foldable 類

為資料結構實現 Foldable 需要編寫一個函式：foldMap 或 foldr。但是，Foldable 還有很多其他方法。

-- Abridged definition, with just the method signatures.
class Foldable t where
    foldMap :: Monoid m => (a -> m) -> t a -> m
    foldr :: (a -> b -> b) -> b -> t a -> b

    -- All of the following have default implementations:
    fold :: Monoid m => t m -> m -- generalised mconcat
    foldr' :: (a -> b -> b) -> b -> t a -> b
    foldl :: (b -> a -> b) -> b -> t a -> b
    foldl' :: (b -> a -> b) -> b -> t a -> b
    foldr1 :: (a -> a -> a) -> t a -> a
    foldl1 :: (a -> a -> a) -> t a -> a
    toList :: t a -> [a]
    null :: t a -> Bool
    length :: t a -> Int
    elem :: Eq a => a -> t a -> Bool
    maximum :: Ord a => t a -> a
    minimum :: Ord a => t a -> a
    sum :: Num a => t a -> a
    product :: Num a => t a -> a

這些額外的方法存在是為了在必要時可以編寫更有效的實現。無論如何，只編寫 foldMap 或 foldr 就能讓你免費獲得上面列出的所有非常有用的函式。更棒的是：Data.Foldable 提供了更多泛化到任何 Foldable 的函式，包括，令人驚訝的是，mapM_/traverse_。

以下是如何使用 Data.Map 快速演示 Foldable。

GHCi> import qualified Data.Map as M
GHCi> let testMap = M.fromList $ zip [0..] ["Yesterday","I","woke","up","sucking","a","lemon"]
GHCi> length testMap 
7
GHCi> sum . fmap length $ testMap 
29
GHCi> elem "lemon" testMap 
True
GHCi> foldr1 (\x y -> x ++ (' ' : y)) testMap -- Be careful: foldr1 is partial!
"Yesterday I woke up sucking a lemon"
GHCi> import Data.Foldable
GHCi> traverse_ putStrLn testMap 
Yesterday
I
woke
up
sucking
a
lemon

除了提供有用的泛化之外，Foldable 和 foldMap 還建議了一種更宣告性的思考摺疊的方式。例如，我們可以說，sum 並不是一個遍歷列表（或樹，或任何資料結構）並使用 (+) 累積其元素的函式，而是它查詢每個元素的值，並使用 Sum monoid 彙總查詢結果。雖然差異可能很小，但 monoidal 摘要觀點可以透過將我們希望獲得的結果型別從被摺疊的資料結構的細節中分離出來，幫助澄清涉及摺疊的問題。

練習

讓我們玩“找出 Monoid”遊戲！以下是規則： 對於每個函式，建議一個 mempty、mappend 和（如果需要）一個函式來準備值，這將使它能夠使用 fold 或 foldMap 來實現。不需要為 newtype 例項費心（除非你希望使用 foldMap 來測試你的解決方案，當然）- 例如，"mempty 是 0，mappend 是 (+)" 將是 sum 的一個完全可以接受的答案。如果有必要，你可以部分應用函式並在答案中使用提供的引數。不要用 id 和 (.) 來回答所有問題 - 那樣就作弊了！ （提示：如果你需要建議，請檢視 Data.Monoid 中的 Monoid 例項。） product :: (Foldable t, Num a) => t a -> a concat :: Foldable t => t [a] -> [a] concatMap :: Foldable t => (a -> [b]) -> t a -> [b] all :: Foldable t => (a -> Bool) -> t a -> Bool elem :: (Foldable t, Eq a) => a -> t a -> Bool length :: Foldable t => t a -> Int traverse_ :: (Foldable t, Applicative f) => ‌(a -> f b) -> t a -> f () mapM_ :: (Foldable t, Monad m) => ‌(a -> m b) -> t a -> m () safeMaximum :: (Foldable t, Ord a) => t a -> Maybe a （類似於 maximum，但處理空情況。） find :: Foldable t => (a -> Bool) -> t a -> Maybe a composeL :: Foldable t => ‌(b -> a -> b) -> t a -> b -> b (等同於 foldl.)

列表式摺疊

Foldable 包含 toList :: Foldable t => t a -> [a] 方法。這意味著任何 Foldable 資料結構都可以轉換為列表；此外，摺疊生成的列表將產生與直接摺疊原始結構相同的結果。根據 foldMap 可能的 toList 實現將是

toList = foldMap (\x -> [x])

toList 反映了這樣一個事實，即列表是 Haskell 型別中的 **自由么半群**。“自由”在這裡意味著任何值都可以提升到么半群，既不新增也不刪除任何資訊（我們可以將型別為 a 的值轉換為具有單個元素的 [a] 列表，並透過 (\x->[x]) 和 head 以無損方式返回）。

toList 突出顯示了 Foldable 的一個相關關鍵特徵。由於列表的 toList = id，如果您給定一個定義為... 的函式

-- Given a list xs :: [a] 
xsAsFoldMap :: Monoid m => (a -> m) -> m
xsAsFoldMap = \f -> foldMap f xs

... 始終可以透過向 xsAsFoldMap 提供 (\x->[x]) 來恢復原始列表 xs。從這個意義上講，**列表等同於其右摺疊**。這意味著如果資料結構比列表更復雜，則使用 Foldable 操作進行摺疊將不可避免地成為一種有損操作。換句話說，我們可以說 Foldable 提供的列表式摺疊不如我們之前在 其他資料結構 中看到的摺疊（正式稱為 **範疇同態**）通用，後者確實可以重建原始結構。

練習
此練習涉及我們在 其他資料結構 中使用的樹型別 data Tree a = Leaf a | Branch (Tree a) (Tree a) 為 Tree 寫一個 Foldable 例項。 實現 treeDepth :: Tree a -> Int，它給出從樹根到最遠葉子的分支數量。使用 Foldable 或 其他資料結構 中定義的 treeFold 範疇同態。這兩個建議是否實際上都可行？

關於 Foldable 的更多事實

Foldable 在 Haskell 類中稍微不同尋常，這些類既有原則性又通用，因為它本身沒有自己的規律。最接近的是以下屬性，嚴格來說這不是一個規律（因為它保證在無論例項是什麼的情況下都成立）：給定一個 么半群同態 g，

foldMap (g . f) = g . foldMap f

從 foldMap (g . f) 切換到 g . foldMap f 可能是有利的，因為它意味著僅對摺疊的結果應用 g，而不是對正在摺疊的結構中的可能許多元素應用 g。

如果 Foldable 結構也是 Functor，則它還自動成立...

foldMap f = fold . fmap f

... 因此我們得到，在應用 第二個函子定律 和上面的屬性之後

foldMap g . fmap f = foldMap (g . f) = g . foldMap f

儘管存在 foldMap 這樣的方法可能表明任何 Foldable 型別也應該具有 Functor 例項，但 Functor 實際上不是 Foldable 的超類。這使得為結構提供 Foldable 例項成為可能，這些結構由於某種原因不能是 Functor。最常見的例子是 集合 來自 Data.Set。這些集合的元素型別必須是 Ord 的例項，因此它們的 map 函式不能用作 fmap，後者沒有額外的類約束。但是，這並不否認 Data.Set.Set 一個有用的 Foldable 例項。

GHCi> import qualified Data.Set as S
GHCi> let testSet = S.fromList [1,3,2,5,5,0]
GHCi> testSet 
fromList [0,1,2,3,5]
GHCi> import Data.Foldable
GHCi> toList testSet
[0,1,2,3,5]
GHCi> foldMap show testSet 
"01235"

練習
編寫對對的么半群例項， (Monoid a, Monoid b) => Monoid (a,b) 證明 fst 和 snd 是么半群同態。 使用上面介紹的 foldMap 的么半群同態屬性證明 foldMap f &&& foldMap g = foldMap (f &&& g) 其中 f &&& g = \x -> (f x, g x) 此練習基於 Edward Kmett 的一條訊息 。