Haskell/Traversable
我們已經學習了 Prelude 中五個型別類中的四個，這些型別類可以用於資料結構操作：Functor、Applicative、Monad 和 Foldable。第五個是 Traversable [1]。遍歷意味著橫跨，而這正是 Traversable 泛化的：橫跨一個結構，在每個停靠點收集結果。
如果遍歷意味著橫跨，那麼我們已經很長時間一直在執行遍歷了。考慮以下對列表的合理 Functor 和 Foldable 例項
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 的結構替換原始列表的結構，並且無法將其扭曲成返回原始列表或 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 的列表。如果你眯起眼睛仔細看，這有點像摺疊。但是，我們不需要僅僅合併值並銷燬列表，而是需要合併值的 Maybe 上下文並在合併的上下文中重新建立列表結構。幸運的是，有一個型別類本質上是關於合併 Functor 上下文的：Applicative [3]。Applicative 反過來又引導我們到我們需要的類：Traversable。
instance Traversable [] where
-- sequenceA :: Applicative f => [f a] -> f [a]
sequenceA [] = pure []
sequenceA (u:us) = (:) <$> u <*> sequenceA us
-- Or, equivalently:
instance Traversable [] where
sequenceA us = foldr (\u v -> (:) <$> u <*> v) (pure []) us
Traversable 對於 Applicative 上下文就像 Foldable 對於 Monoid 值一樣。從這個角度來看，sequenceA 與 fold 相似 - 它建立了結構中上下文的應用性摘要，然後在新的上下文中重建結構。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)
-- These methods have default definitions.
-- They are merely specialised versions of the other two.
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
-- Or, equivalently:
instance Traversable [] where
traverse f xs = foldr (\x v -> (:) <$> f x <*> v) (pure []) xs
通常，在實現 Traversable 時最好寫 traverse，因為 traverse 的預設定義原則上會對結構執行兩次遍歷（一次用於 fmap，另一次用於 sequenceA）。
我們可以用 traverse 清晰地直接定義 rejectWithNegatives
rejectWithNegatives :: (Num a, Ord a, Traversable t) => t a -> Maybe (t a)
rejectWithNegatives = traverse deleteIfNegative
| 練習 |
|---|
|
Traversable 結構可以使用你選擇的應用性函子來遍歷。traverse 的型別...
traverse :: (Applicative f, Traversable t) => (a -> f b) -> t a -> f (t b)
... 與我們在其他類中看到的對映函式的型別相似。traverse 不會使用它的函式引數在原始結構下插入函子上下文（就像 fmap 所做的那樣），也不會修改結構本身（就像 (>>=) 所做的那樣），而是添加了一個額外的上下文層 在 結構的 頂部。換句話說，traverse 允許進行 有副作用的遍歷 - 產生整體效果的遍歷（即新的外部上下文層）。
如果新層下面的結構可以恢復，它將與原始結構匹配（當然，值可能已經改變）。這是一個涉及巢狀列表的示例
GHCi> traverse (\x -> [0..x]) [0..2]
[[0,0,0],[0,0,1],[0,0,2],[0,1,0],[0,1,1],[0,1,2]]
為了理解這裡發生了什麼，讓我們一步一步地分解它。
traverse (\x -> [0..x]) [0..2]
sequenceA $ fmap (\x -> [0..x]) [0..2]
sequenceA [[0],[0,1],[0,1,2]]
(:) <$> [0] <*> ((:) <$> [0,1] <*> ((:) <$> [0,1,2] <*> pure []))
(:) <$> [0] <*> ((:) <$> [0,1] <*> ([[0],[1],[2]]))
(:) <$> [0] <*> ([[0,0],[0,1],[0,2],[1,0],[1,1],[1,2]])
[[0,0,0],[0,0,1],[0,0,2],[0,1,0],[0,1,1],[0,1,2]]
內部列表保留了原始列表的結構 - 它們都有三個元素。外部列表是新的層，對應於透過允許每個元素從零到其（原始）值變化來引入不確定性。
我們也可以透過關注 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 可以看作將舊的外部結構分配到新的外部結構中，因此新的內部列表有兩個元素，就像舊的外部列表一樣。新的外部結構是一個包含十二個元素的列表，這正是你期望用 (<*>) 將一個包含四個元素的列表與另一個包含三個元素的列表組合起來的結果。從分配的角度來看，一個有趣的方面是它如何幫助理解為什麼某些函子不可能擁有 Traversable 的例項（如何分配 IO 操作？或者函式？）。
| 練習 |
|---|
|
如果你還記得應用函子那一章的內容，可以幫助你完成以下練習。
|
Traversable 法則
[edit | edit source]合理的Traversable 例項需要遵循一些法則。有以下兩個法則
traverse Identity = Identity -- identity
traverse (Compose . fmap g . f) = Compose . fmap (traverse g) . traverse f -- composition
還有一個額外的法則，它保證成立
-- If t is an applicative homomorphism, then
t . traverse f = traverse (t . f) -- naturality
這些法則不是自解釋的，所以讓我們仔細看看它們。從最後一個開始：應用函子同態是一個保持Applicative 操作的函式，因此
-- Given a choice of f and g, and for any 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，它是啞函子
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 函子的基礎上陳述的
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，組合兩個Applicative 會得到一個Applicative [4]。這些例項是顯而易見的，將方法向下一層函子層級傳遞。
組合法則指出，我們是否分別執行兩次遍歷（等式右邊）或將它們組合起來以僅遍歷結構一次（等式左邊）無關緊要。例如，它類似於第二個函子法則。fmap 是必需的，因為第二次遍歷（或等式左邊第一次（部分）遍歷之後的第二次遍歷）發生在第一次（部分）遍歷新增的結構層之下。Compose 是必需的，以便組合後的遍歷應用於正確的層級。
Identity 和Compose 分別來自 Data.Functor.Identity 和 Data.Functor.Compose。
這些法則也可以用sequenceA 來表述
sequenceA . fmap Identity = Identity -- identity
sequenceA . fmap Compose = Compose . fmap sequenceA . sequenceA -- composition
-- For any applicative homomorphism t:
t . sequenceA = sequenceA . fmap t -- naturality
雖然並不明顯，但遍歷的幾個理想特徵都源於這些法則，包括 [5]
- 遍歷不會跳過元素。
- 遍歷不會訪問元素多次。
traverse pure = pure- 遍歷不會修改原始結構（它要麼保留，要麼完全銷燬）。
恢復fmap 和foldMap
[edit | edit source]我們還沒有證明Traversable 的Functor 和Foldable 類約束。原因很簡單：只要Traversable 例項遵循法則，traverse 就足以實現fmap 和foldMap。對於fmap，我們只需要使用Identity 將任意函式轉換為遍歷即可
fmap f = runIdentity . traverse (Identity . f)
為了恢復foldMap，我們需要引入第三個輔助函子：Const，來自 Control-Applicative
newtype Const a b = Const { getConst :: a }
instance Functor (Const a) where
fmap _ (Const x) = Const x
Const 是一個常量函子。Const a b 型別的值實際上不包含b 值。相反，它包含一個a 值，該值不受fmap 的影響。對於我們當前的目的，真正有趣的例項是Applicative 例項
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。由於上面的例項，遍歷就變成了摺疊
foldMap f = getConst . traverse (Const . f)
我們剛剛從traverse 中恢復了兩個表面上看起來完全不同的函式，而我們所做的只是選擇了兩個不同的函子。這體現了函子作為抽象概念的強大之處 [7]。
註釋
- ↑ 嚴格地說，我們應該參考 GHC Prelude 中的五個類，因為根據 Haskell 報告，
Applicative、Foldable和Traversable還沒有正式成為 Prelude 的一部分。不過，它們遲早會加入。 - ↑ 一個嘗試的方法是利用 Data.Monoid 中的
Monoid a => Monoid (Maybe a)例項。但是，如果你嘗試這樣做，你會發現它不可能得到預期的結果。 - ↑ 么半群表示法 對此進行了非常清晰的說明。
- ↑ 然而，值得注意的是，組合兩個
Monad並不一定會得到一個Monad。 - ↑ 有關技術細節，請檢視 Data.Traversable 文件中引用的論文。
- ↑ 這很好地說明了
Applicative如何以么半群的方式組合上下文。如果我們移除上下文中的值，么半群表示法 中的應用函子法則與么半群法則完全一致。 - ↑ 一個主要的例子，而且是一個具有明顯實際意義的例子，就是對函子的頌歌，lens 庫。