跳至內容

Haskell/Foldable類型類

編輯連結
維基教科書，自由的教學讀本
Foldable類型類 (解答)
高級Haskell

Monoid類型類
Applicative類型類
箭頭
理解箭頭
Foldable類型類
Traversable類型類
延續過渡風格（CPS）
可變對象
拉鏈
適用函子
獨異點
Lens 和引用
並行

Foldable 類型類歸納了列表上各種形式的 fold (foldr 和它的朋友們) 並將它們擴展到了任意的資料結構. 除了本身有極大的實用價值之外, Foldable 還很好地演示了 monoid 如何能夠幫助我們更好地抽象.

解剖 foldr

[編輯]

foldr 要做的事情並不少 -- 接收一個並返回一個二元函數, 每一個的類型中都有兩個變量. 

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

如果我們想要一般化 foldr, 或許我們會需要一個更簡單的函數, 或者我們至少要能夠將它拆散成更簡單的組件. 這些組件是什麼呢?

列表上的 fold 可以被粗略地描述為, 順序訪問列表內的元素並用一個二元函數將它們結合起來. 我們恰巧知道, 有一個類型類存在的目的就是為了結合一對值: 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, 正如同我們使用 mconcat 一樣 (即 (<>)) 和 mempty: 

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

mconcat 很好地復刻了 foldr 的"將所有元素結合"的特性, 並且支持一些後者的用法: 

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

很好 −- 但顯然我們不希望只能 fold Monoid. 一個可能的解決方案是將一個列表中任意類型的元素轉化為 Monoid 值以使用 mconcat 進行 fold: 

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. 我們可以在 Data.Monoid 模塊中的 Endo 里找到對應的 Monoid instance 定義[1]: 

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)))
-- (<>) 和 (.) 满足结合律, 因此括号其实可有可无.

-- 作为例子, 我们试着剖析计算过程:
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 是 Foldable 的核心, 其進而將 foldr 推廣到任意資料結構.

練習
  1. 實現兩個版本的作用於列表上 foldMap: 其中一個使用 foldr, 另一個使用顯示遞歸.

Foldable 類型類

[編輯]

為資料結構實現 Foldable 的 instance 只需要一個函數: foldMap 和 foldr 任選其一即可. 然而, Foldable, 定義了許多其它函數: 

-- 简便起见, 我们这里只写出类型.
class Foldable t where
    foldMap :: Monoid m => (a -> m) -> t a -> m
    foldr :: (a -> b -> b) -> b -> t a -> b

    -- 以下函数都有默认实现:
    fold :: Monoid m => t m -> m -- 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

我們將擴展出的函數也定義在類型類中 (而不是在模塊中直接提供默認的定義) 是為了為更高效的實現留出位置 -- 比如說, 如果我們需要一個對性能高度敏感的資料結構, 或許我們不會希望如同 foldl' 的默認實現那樣使用一些低效的技巧以將 foldr 轉換成 foldl. 但在任何情況下, 只要實現了 foldMap 或 foldr, 我們都可以"免費"使用上面列出的所有這些有用的函數. 這還沒完: Data.Foldable 模塊提供了更多推廣了 Foldable 的函數, 其中包括了值得注意的 mapM_/traverse_.

我們來看一個使用 Data.Map 的 Foldable 實現的樣例: 

GHCi> import qualified Data.Map as M
GHCi> let testMap = M.fromList $ zip [0..] ["昨天","我","起床","的时候","发现自己","含着","一个","柠檬"]
GHCi> length testMap
8
GHCi> sum . fmap length $ testMap
18
GHCi> elem "柠檬" testMap
True
GHCi> foldr1 (\x y -> x ++ (' ' : y)) testMap -- 注意: foldr1 是一个偏函数!
"昨天 我 起床 的时候 发现自己 含着 一个 柠檬"
GHCi> import Data.Foldable
GHCi> traverse_ putStrLn testMap
昨天
我
起床
的时候
发现自己
含着
一个
柠檬

除了提供一些有用的推廣之外, Foldable 和 foldMap 還揭示了一種聲明式編程的視角. 比如說, 與其將 sum 看成一個遍歷一個列表 (或者一棵樹或者隨便什麼資料結構) 並將其中的值用 (+) 累加起來的函數, 我們可以認為其詢問了每個元素的值並使用 Sum 將詢問結果總結了. 雖然這看起來並沒有太大不同, 這種總結一個 monoid 的新角度能夠讓我們拋去被 fold 的資料結構的實現細節, 專注於我們想要的結果.


列表風格的 fold

[編輯]

Foldable 還提供了一個 toList :: Foldable t => t a -> [a] 函數. 這意味著, 一個 Foldable 資料結構能夠被轉化成一個列表; 而且, 在這個列表上進行 fold 得到的結果和直接在原來的資料結構上進行結果無異. 一個可行的使用 foldMap 的 toList 實現是[2]: 

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

toList 反映了, 列表實際上是 Haskell 中類型上的自由么半群(free monoid). "自由"指的是, 任何值都能夠被以某種方式轉化成一個 monoid, 並且不增添或遺漏任何信息 (使用 (\x -> [x]) 和 head, 我們能夠將任意類型為 a 的值與 [a] 互相轉化並且不丟失信息) [3].

Foldable 的一個與此有關的關鍵性質能夠被 toList 體現出來. 因為對於列表來說, toList = id, 如果我們有這樣定義的一個函數... 

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

... 我們只要將 (\x -> [x]) 傳遞給 xsAsFoldMap 就可以從中得回 xs. 這種意義上, 一個列表和它的右 fold 等價(同構). 這意味著, 對任何比列表複雜的 Foldable 的操作都會損失一定的信息. 換句話說, Foldable 提供的從列表推廣出的 fold 都沒有我們在更多數據類型一章中所見到的那麼通用 (在後者中我們總是能夠從 fold 得回原值).

練習

  1. 這個練習使用到更多數據類型中的資料結構:

    data Tree a = Leaf a | Branch (Tree a) (Tree a)

    1. 為 Tree 實現 Foldable 的 instance.
    2. 實現 treeDepth :: Tree a -> Int, 其給出樹最深處的深度. 你可以使用 Foldable 或者更多數據類型一章中的 treeFold. 事實上, 這兩種實現方式都是可行的嗎? 
      treeFold :: (b -> b -> b) -> (a -> b) -> Tree a -> b
treeFold fbranch fleaf = g where
  g (Leaf x) = fleaf x
  g (Branch left right) = fbranch (g left) (g right)

更多關於 Foldable 的事

[編輯]

Foldable 在 Haskell 的通用而有特殊規定的類型類中獨樹一幟, 因為其並沒有規定自己的法則. 然而, 我們確實能夠得出以下性質, 雖然它們嚴格來說並不是法則 (因為對於任何 instance 它們都成立): 對於一個么半群同態 g[4], 

foldMap (g . f) = g . foldMap f

不使用 foldMap (g . f) 的寫法, 而是使用 g . foldMap f 有一些好處, 也就是 g 只被應用到了 fold 的結果上, 而不是應用到了被 fold 的資料結構中的每一個值上.

如果這裡的 Foldable 也是一個 Functor, 我們有這個性質... 

foldMap f = fold . fmap f

... 因此在使用了 Functor 法則後我們能夠得到: 

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

雖然 foldMap 或許暗示了任何 Foldable 都應該也是一個 Functor, 實際情況卻並不總是這樣. 例如 Data.Set.Set. 因為其中的值必須有 Ord instance, 因此它提供的 map 函數並不能和 fmap 等價, 因為後者的返回值類型可能沒有 Ord instance. 但是, 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"
練習
    1. 為二元組實現 Monoid instance,
      (Monoid a, Monoid b) => Monoid (a,b)
    2. 證明 fst 和 snd 么半群同態.
    3. 使用上文提到的 foldMap 和么半群同態的性質證明
      foldMap f &&& foldMap g = foldMap (f &&& g)
      其中,
      f &&& g = \x -> (f x, g x)

    這個練習來源於 Edward Kmett 的帖子.[5].


Foldable類型類
習題解答
高級Haskell

Monoid類型類  >> Applicative類型類  >> 箭頭  >> 理解箭頭  >> Foldable類型類  >> Traversable類型類  >> 延續過渡風格（CPS）  >> 可變對象  >> 拉鏈  >> 適用函子  >> 獨異點  >> Lens 和引用  >> 並行


Haskell

Haskell基礎 >> 初級Haskell >> Haskell進階 >> Monads
高級Haskell >> 類型的樂趣 >> 理論提升 >> Haskell性能

庫參考 >> 普通實務 >> 特殊任務

  1. ↑ "Endo" 是 "endomorphism" 的縮寫, 指一個參數和返回值同類型的函數.
  2. ↑ Data.Foldable 為了性能考慮使用了一種不同的默認實現.
  3. ↑ 對於列表形成一個自由么半群這件事, 在非終止性上有一個值得注意的地方. 詳見 Dan Doel 所寫的 Free Monoids in Haskell. (那篇文章中的討論或許有些超前, 畢竟我們剛剛介紹了 Foldable.)
  4. ↑ 即滿足 f (x `mappend` y) = f x `mappend` f y 的函數 f.
  5. ↑ 見Haskell Café
取自「https://zh.wikibooks.org/w/index.php?title=Haskell/Foldable类型类&oldid=133752」