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 的赞歌").