折叠非名单？

Question

在最近的一项任务中,我被要求为某些非列表类型定义折叠函数.我还不能完全理解这个概念.到目前为止,我已经理解fold为执行后续元素list.fold上Tree还是做做直观的感觉,因为一个是能够通过根的子树递归应用的一些功能.

但是,在类似的数据类型上:

Maybe a :: Nothing | Just a

没有list(在我看来)执行折叠操作.

我确信我在理解这里的基本概念时遇到了一些问题,我非常感谢一些清理工作.

Answer 1

Foldable是一个非常令人困惑的类,说实话,因为它没有很多法则,并且很有可能Foldable为几乎任何给定的类型编写很多不同的实例.幸运的是,Foldable基于Traversable相同类型的实例(如果有的话),可以找出实例应该以纯机械方式执行的操作.

我们有

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

该Traversable实例Maybe完全由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)))

通过的定义pure,并<$>为Const这些都是

foldMapDefault f Nothing = getConst (Const mempty)
foldMapDefault f (Just a) = getConst (Const (f a))

展开构造函数,

foldMapDefault f Nothing = mempty
foldMapDefault f (Just a) = f a

这确实是如何foldMap定义的Maybe.