Foldable
是一个相当令人困惑的类,因为它没有很多法则,并且对于几乎任何给定类型都可以编写许多不同的 Foldable
实例。幸运的是,如果一个类型有一个 Traversable
实例,就可以以纯机械的方式确定 Foldable
实例应该做什么。
我们有:
class (Functor t, Foldable t) => Traversable t where
traverse :: Applicative f => (a -> f b) -> t a -> f (t b)
Traversable
有几个不同的法则,但最重要的是traverse Identity = Identity
。现在我们来看看它如何适用于Maybe
:
traverse :: Applicative f => (a -> f b) -> Maybe a -> f (Maybe b)
traverse g Nothing = _none
traverse g (Just a) = _some
现在在第一种情况下,你需要生成
f (Maybe b)
,而所有你拥有的只有
g :: a -> f b
。由于你没有任何
f
值,也没有任何
a
值,唯一能够生成的就是
pure Nothing
。
在第二种情况下,你必须生成
f (Maybe b)
,而你有
g :: a -> f b
和
a
。所以开始的唯一有趣的方式是将
g
应用于
a
,得到
g a :: f b
。现在你有两个选择:你可以放弃这个值,只返回
Nothing
,或者你可以用
Just
将其包装起来。
根据恒等律,
traverse Identity (Just a) = Identity (Just a)
。所以你不能返回
Nothing
。唯一合法的定义是...
traverse _ Nothing = pure Nothing
traverse g (Just a) = Just <$> g a
Maybe
的Traversable
实例完全由Traversable
定律和参数化确定。
现在可以使用traverse
进行折叠:
foldMapDefault :: (Traversable t, Monoid m)
=> (a -> m) -> t a -> m
foldMapDefault f xs =
getConst (traverse (Const . f) xs)
由于这适用于 Maybe
,
foldMapDefault f Nothing =
getConst (traverse (Const . f) Nothing)
foldMapDefault f (Just a) =
getConst (traverse (Const . f) (Just a))
扩展我们的定义,
foldMapDefault f Nothing = getConst (pure Nothing)
foldMapDefault f (Just a) = getConst (Just <$> (Const (f a)))
根据 Const
的 pure
和 <$>
的定义,它们如下:
foldMapDefault f Nothing = getConst (Const mempty)
foldMapDefault f (Just a) = getConst (Const (f a))
揭开构造函数的神秘面纱,
foldMapDefault f Nothing = mempty
foldMapDefault f (Just a) = f a
这确实是Maybe
中foldMap
的精确定义。
Maybe a
可以被视为一个包含 0 或 1 个元素的列表,并且fold
可以明确地针对其中的每个东西进行定义。 - Alexis KingFoldable
可以转换为列表;toList <$> [Nothing, Just True] == [[], [True]]
- Chris MartinFoldable
类,其中的foldr
等价于将数据类型转换为列表,然后在结果列表上使用foldr
。在其他语境中,“fold”是一个所谓的“消除器”,比如来自“递归方案”的cata
。在我的第一次计算机科学考试中,我被要求在口试中生成一个“二叉树的fold”,那是类似于cata
的东西。 - chi