Haskell/Foldable類型類

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 定義:

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 推廣到任意數據結構.

練習
實現兩個版本的作用於列表上 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 實現是:

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

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

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 得回原值).

練習
這個練習使用到更多數據類型中的數據結構: data Tree a = Leaf a | Branch (Tree a) (Tree a) 為 Tree 實現 Foldable 的 instance. 實現 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,

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"

練習
為二元組實現 Monoid instance, (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 的帖子..

---

Foldable類型類

習題解答

高級Haskell

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

Haskell

Haskell基礎 >> 初級Haskell >> Haskell進階 >> Monads 高級Haskell >> 類型的樂趣 >> 理論提升 >> Haskell性能 庫參考 >> 普通實務 >> 特殊任務