Haskell/Traversable類型類

Traversable類型類 (解答)

高級Haskell

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

我們已經學習了 Prelude 中四種用於操作資料結構的類型類: Functor, Applicative, Monad 和 Foldable. 現在我們來學習第五個: Traversable ^[1]. Traversable, 如同其名, 一般化了了關於遍歷 (traverse) 的操作: 遍歷一個結構, 對於其中的每一個值得出並返回一個結果.

Functor 與遍歷

我們已經接觸遍歷很久了. 比如說如下列表的 Functor 和 Foldable instance 實現:

instance Functor [] where
    fmap _ []     = []
    fmap f (x:xs) = f x : fmap f xs

instance Foldable [] where
    foldMap _ []     = mempty
    foldMap f (x:xs) = f x <> foldMap f xs

fmap f 遍歷整個列表, 將 f 應用到每個值上並將結果放入一個新構造的列表中返回. 相似的, foldMap f 遍歷整個列表, 將 f 應用到每個值上並將結果 mappend 後返回. 然而, Functor 和 Foldable, 並不能表示所有實用的遍歷方式. 舉個例子, 如果我們以如下的方式使用 Maybe 測試負數...

deleteIfNegative :: (Num a, Ord a) => a -> Maybe a
deleteIfNegative x = if x < 0 then Nothing else Just x

... 然後我們用它來實現...

rejectWithNegatives :: (Num a, Ord a) => [a] -> Maybe [a]

... 如果列表中沒有負數, 我們將它包裹在 Just 里返回; 否則我們返回 Nothing. 我們發現, 似乎 Foldable 和 Functor 在這裡都無法給我們幫助. 使用 Foldable 將會把原列錶轉換成一個我們所選的 Monoid, 而似乎我們並不能讓其返回 Just 中的原列表或 Nothing ^[2]. 至於 Functor, fmap 一開始看起來很有希望...

GHCi> let testList = [-5,3,2,-1,0]
GHCi> fmap deleteIfNegative testList
[Nothing,Just 3,Just 2,Nothing,Just 0]

... 然而現在我們必須找到一種方法將一列表的 Maybe 轉換成 Maybe 里的列表. 如果我們堅持走這條路, 看起來我們需要 fold. 然而, 我們不僅僅要將這個列表中的值組合起來, 我們還需要組合起 Maybe 所表示的額外信息 (context, 即"一個 Maybe 值是 Just 還是 Nothing"這個信息), 然後重建這個列表. 所幸, 有一個類型類存在的目的就是為了組合 Functor 表示的額外信息: Applicative ^[3]. 而從 Applicative, 可以最終導出我們所需要的類型類: Traversable.

instance Traversable [] where
    -- sequenceA :: Applicative f => [f a] -> f [a]
    sequenceA []     = pure []
    sequenceA (u:us) = (:) <$> u <*> sequenceA us

-- 或者, 等价的:
instance Traversable [] where
    sequenceA us = foldr (\u v -> (:) <$> u <*> v) (pure []) us

Traversable 與 Applicative 額外信息的關係和 Foldable 與 Monoid 值的關係一樣. 從這個角度來說, sequenceA 和 fold 類似 -− 前者總結出一個 Applicative 內值的額外信息, 然後使用這個信息重新構建一個值. sequenceA 就是我們想要的函數:

GHCi> let rejectWithNegatives = sequenceA . fmap deleteIfNegative
GHCi> :t rejectWithNegatives
rejectWithNegatives
  :: (Num a, Ord a, Traversable t) => t a -> Maybe (t a)
GHCi> rejectWithNegatives testList
Nothing
GHCi> rejectWithNegatives [0..10]
Just [0,1,2,3,4,5,6,7,8,9,10]

這些是 Traversable 提供的函數:

class (Functor t, Foldable t) => Traversable t where
    traverse  :: Applicative f => (a -> f b) -> t a -> f (t b)
    sequenceA :: Applicative f => t (f a) -> f (t a)

    -- 以下函数有默认实现.
    -- 它们只是上面两个函数的特化版本罢了.
    mapM      :: Monad m => (a -> m b) -> t a -> m (t b)
    sequence  :: Monad m => t (m a) -> m (t a)

如果 sequenceA 可以被類比為 fold 的話, traverse 可以被類比為 foldMap. 它們是互相定義的, 因此一個 Traversable 的最小實現只需要實現其中一個就可以了:

traverse f = sequenceA . fmap f
sequenceA = traverse id

我們實現列表的 traverse 後, 它與 Functor 和 Foldable 的相似之處就顯而易見了:

instance Traversable [] where
    traverse _ []     = pure []
    traverse f (x:xs) = (:) <$> f x <*> traverse f xs

-- 或者, 等价的:
instance Traversable [] where
    traverse f xs = foldr (\x v -> (:) <$> f x <*> v) (pure []) xs

一般來說, 實現 Traversable instance 時我們最好選擇 traverse (而不是 sequenceA), 因為 traverse 的默認實現, 原則上, 遍歷了這個結構兩次 (fmap 和 sequenceA 各一次).

我們可以直接明了地用 traverse 定義 rejectWithNegatives:

rejectWithNegatives :: (Num a, Ord a, Traversable t) => t a -> Maybe (t a)
rejectWithNegatives = traverse deleteIfNegative

練習
為如下 `Tree` 實現一個 `Traversable` instance. `Tree` 的定義: `data Tree a = Leaf a \| Branch (Tree a) (Tree a)`

`Traversable` 的意義

Traversable 能夠在你所選擇的任意 Applicative 的意義下遍歷. traverse 的類型...

traverse :: (Applicative f, Traversable t) => (a -> f b) -> t a -> f (t b)

... 和我們在其他類型類中見到的 map 相似. 但和 fmap 所做的修改原有結構內部的值而保留額外信息不同, 也和 (>>=) 所做的修改結構本身不同, traverse 在結構之上添加了一層額外信息. 換句話說, traverse 使有副作用的遍歷成為可能 -− 遍歷將產生一個總的額外信息.

在我們能夠提取在這層新的額外信息之下的值的情況下, 它會反映出原有的結構 (當然, 值或許會變). 這裡是一個嵌套列表的例子:

GHCi> traverse (\x -> [0..x]) [0..3]
[[0,0,0,0],[0,0,0,1],[0,0,0,2],[0,0,0,3],[0,0,1,0],[0,0,1,1]
,[0,0,1,2],[0,0,1,3],[0,0,2,0],[0,0,2,1],[0,0,2,2],[0,0,2,3]
,[0,1,0,0],[0,1,0,1],[0,1,0,2],[0,1,0,3],[0,1,1,0],[0,1,1,1]
,[0,1,1,2],[0,1,1,3],[0,1,2,0],[0,1,2,1],[0,1,2,2],[0,1,2,3]
]

內層列表保留了原列表的結構 −- 它們都有四個元素. 外層列表就是新一層信息, 和列表所表示的不確定性對應: 子列表中的值可以在從 0 到其原值的區間中取值.

或許我們也可以從 sequenceA 的角度去理解 Traversable. 我們需要關注這個函數是如何分配額外信息的.

GHCi> sequenceA [[1,2,3,4],[5,6,7]]
[[1,5],[1,6],[1,7],[2,5],[2,6],[2,7]
,[3,5],[3,6],[3,7],[4,5],[4,6],[4,7]
]

本例中, sequenceA 的作用可以被看成將將原有結構外層的額外信息分配到新產生的結構中, 因此新結構的內層列表各包含兩個值, 就和原有的外層列表一樣. 新的外層結構包含 12 個值, 正是用 (<*>) 將一個 3 個值的列表和另一個 4 個值的列表結合所能得到的結果數目. 這種"分配額外信息"的觀點或許能夠幫助我們理解為什麼有一些 Functor 不能同時是 Traversable (比如說, 我們如何分配 IO, 或是函數的額外信息呢?).

練習
若我們將矩陣表示為嵌套的列表, 並規定內層列表為行. 使用 `Traversable` 來實現函數 `transpose :: [[a]] -> [[a]]` 其轉置一個矩陣 (也就是將行號和列號對調). 此練習中, 我們暫時假定內層列表長度相同. 解釋 `traverse mappend` 的作用.

`Traversable` 法則

我們期望 Traversable 滿足這兩條法則:

traverse Identity = Identity -- 恒等
traverse (Compose . fmap g . f) = Compose . fmap (traverse g) . traverse f -- 复合

以及一個必定成立的定理:

-- 若 t 是一个 Applicative 上的同态映射 (homomorphism)
t . traverse f = traverse (t . f) -- 自然性 (naturality)

或許它們不是非常容易, 因此我們來分析一下. 從最後一個開始: 一個 Applicative 上的同態映射是一個保留了 Applicative 操作的函數, 使得:

-- 对于任意 f, g 和 a
t :: (Applicative f, Applicative g) => f a -> g a

t (pure x) = pure x
t (x <*> y) = t x <*> t y

我們可以注意到, 這個定義和么半群同態類似, 而且還有著對應著我們在關於 Foldable 的章節中所見的 foldMap 的自然性定理.

恆等法則使用了 Identity, 一個無實際作用的 Functor:

newtype Identity a = Identity { runIdentity :: a }

instance Functor Identity where
    fmap f (Identity x) = Identity (f x)

instance Applicative Identity where
    pure x = Identity x
    Identity f <*> Identity x = Identity (f x)

法則規定, 對一個結構用 Identity 進行遍歷相當於用 Identity 包裹起這個結構, 也就是相當於什麼都不做 (因為其與原結構只差一次 runIdentity 調用). 顯然, Identity 值構造函數可以被稱為"守恆"遍歷.

複合法則則需要引入 Compose Functor:

newtype Compose f g a = Compose { getCompose :: f (g a) }

instance (Functor f, Functor g) => Functor (Compose f g) where
    fmap f (Compose x) = Compose (fmap (fmap f) x)

instance (Applicative f, Applicative g) => Applicative (Compose f g) where
    pure x = Compose (pure (pure x))
    Compose f <*> Compose x = Compose ((<*>) <$> f <*> x)

Compose 代表的是 Functor 的複合. 兩個複合的 Functor 仍然形成一個 Functor, 相似的, 兩個複合的 Applicative 仍然形成一個 Applicative ^[4]. Compose 的 instance 實現都並不難理解.

複合法則指的是, 將兩次遍歷分開進行 (等式右側) 與將兩次遍歷複合起來進行 (等式左側) 的結果不應該有差異. 這個法則和 Functor 的第二個法則類似. 由於第二次遍歷 (或者對於等式左側來說, 遍歷的第二部分) 發生在由第一次 (部分) 遍歷生成的結構的下層, 我們需要 fmap. 我們還需要 Compose 以將複合的遍歷應用在正確的層級上.

Identity 和 Compose 分別定義在 Data.Functor.Identity 和 Data.Functor.Compose.

這兩個法則也能用 sequenceA 表示:

sequenceA . fmap Identity = Identity -- 恒等
sequenceA . fmap Compose = Compose . fmap sequenceA . sequenceA -- 复合
-- For any applicative homomorphism t:
t . sequenceA = sequenceA . fmap t -- 自然性 (naturality)

雖然並不容易看出, 但是由這些法則我們能夠推出一些有用的性質: ^[5]:

遍歷不會遺漏值.
遍歷不會重複訪問值.
traverse pure = pure
被遍歷的結構不會改變 (其將會被完整保存或是完全摧毀).

重新發明 `fmap` 和 `foldMap`

我們仍未說明為什麼 Traversable 有著 Functor 和 Foldable 的類型類限制. 原因很簡單: 一個滿足法則的 Traversable 能夠獨立使用 traverse 實現 fmap 和 foldMap. 對於 fmap, 我們只需用 Identity 使任意函數滿足遍歷的類型:

fmap f = runIdentity . traverse (Identity . f)

至於 foldMap, 我們需要引入 Control.Applicative 中的 Functor Const:

newtype Const a b = Const { getConst :: a }

instance Functor (Const a) where
    fmap _ (Const x) = Const x

Const 是一個常Functor. 一個 Const a b 類型的值實際上並不包含一個 b 值. 事實上, 它保存著一個不受 fmap 影響的 a 類型的值. 對於我們當前的目的來說, 有趣的部分在於它的 Applicative instance 實現:

instance Monoid a => Applicative (Const a) where
    pure _ = Const mempty
    Const x <*> Const y = Const (x `mappend` y)

(<*>) 簡單地將值用 mappend 結合起來 ^[6]. 我們能夠利用這個性質, 將任何形如 Monoid m => a -> m 的函數轉化為 foldMap 所要求的類型. 由於以上的 instance, 遍歷退化為 fold:

foldMap f = getConst . traverse (Const . f)

我們由此使用 traverse 定義了兩個從表面上看截然不同的兩個函數, 而我們所要做的只是選擇合適的包裹 Functor 罷了. 我們或許可以從中了解到抽象 Functor 的強大之處 ^[7].

Traversable類型類

習題解答

高級Haskell

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

編輯此章節

Haskell

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

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

編輯書目結構

↑ 嚴格來說, 我們指的是 GHC Prelude, 因為 Applicative, Foldable 和 Traversable 還沒有在語言標準中成為 Prelude 的一部分. 當然這只是時間問題罷了.
↑ 或許我們可以嘗試修改 Data.Monoid 中的 Monoid a => Monoid (Maybe a) instance. 你大可以試試, 然而, 你會發現這並行不通.
↑ Applicative 的 Monoid 表示將它的目的很好地詮釋了.
↑ 然而, 值得注意的是, 兩個複合的 Monad 卻不一定仍然形成一個 Monad.
↑ 細節請見 Data.Traversable 的文檔.
↑ 這是一個關於 Applicative 如何么半群意味地 (monoidally) 結合額外信息 (context) 的極佳例子. 如果我們將其中的值去掉, 只留下額外的信息, Applicative 的 Monoid 意味的法則和 Monoid 法則出奇一致.
↑ 一個具有極大實用價值的極佳的例子是 lens 庫 ("一曲 Functor 的讚歌").

[1] 嚴格來說, 我們指的是 GHC Prelude, 因為 Applicative, Foldable 和 Traversable 還沒有在語言標準中成為 Prelude 的一部分. 當然這只是時間問題罷了.

[2] 或許我們可以嘗試修改 Data.Monoid 中的 Monoid a => Monoid (Maybe a) instance. 你大可以試試, 然而, 你會發現這並行不通.

[3] Applicative 的 Monoid 表示將它的目的很好地詮釋了.

[4] 然而, 值得注意的是, 兩個複合的 Monad 卻不一定仍然形成一個 Monad.

[5] 細節請見 Data.Traversable 的文檔.

[6] 這是一個關於 Applicative 如何么半群意味地 (monoidally) 結合額外信息 (context) 的極佳例子. 如果我們將其中的值去掉, 只留下額外的信息, Applicative 的 Monoid 意味的法則和 Monoid 法則出奇一致.

[7] 一個具有極大實用價值的極佳的例子是 lens 庫 ("一曲 Functor 的讚歌").

[1]

[2]

[3]

[4]

[5]

[6]

[7]

Functor 與遍歷

Traversable 的意義

Traversable 法則

重新發明 fmap 和 foldMap

`Traversable` 的意義

`Traversable` 法則

重新發明 `fmap` 和 `foldMap`