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 库。