Haskell/Traversable類型類
我們已經學習了 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
練習 |
---|
|
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
法則
編輯
我們期望 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
|
- ↑ 嚴格來說, 我們指的是 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 的讚歌").