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