非列表上的折叠？

Question

在最近的任务中，我被要求为一些非列表类型定义fold函数。我仍然无法完全理解这个概念。到目前为止，我已经理解了fold作用于list中连续元素的过程。在Tree上使用fold仍然有直观的意义，因为你可以递归地将某个函数应用于根节点的子树。但是，在像下面这样的数据类型上：

Maybe a :: Nothing | Just a

据我所知，似乎没有要执行折叠操作的list。

我确信在这里有一些基本概念的理解问题，非常希望得到一些澄清。

- CowNorris

---

一个提示：从某种意义上讲，Maybe a 可以被视为一个包含 0 或 1 个元素的列表，并且 fold 可以明确地针对其中的每个东西进行定义。 - Alexis King

为了更加明确，注意任何 Foldable 可以转换为列表；toList <$> [Nothing, Just True] == [[], [True]] - Chris Martin

我想知道你实际需要实现哪种“fold”。在 Haskell 中，我们有 Foldable 类，其中的 foldr 等价于将数据类型转换为列表，然后在结果列表上使用 foldr。在其他语境中，“fold”是一个所谓的“消除器”，比如来自“递归方案”的 cata。在我的第一次计算机科学考试中，我被要求在口试中生成一个“二叉树的fold”，那是类似于 cata 的东西。 - chi

Answer 1

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的精确定义。

- dfeuer

---

这似乎对于楼主来说有点高级了。不过这仍然是一个好答案，只是一些反馈意见。 - luqui

Answer 2

作为“基本概念”，这是非常令人费解的，所以不要感到太糟糕。

也许将关于折叠对列表的操作的直觉放在一边，思考如果应用于Maybe，特定的折叠函数（我们使用foldr）应该有什么类型会有所帮助。写下List a代替[a]使它更清晰，标准的foldr应用于列表的类型如下：

foldr :: (a -> b -> b) -> b -> List a -> b

显然，Maybe类型对应的折叠操作必须具备以下类型：

foldrMaybe :: (a -> b -> b) -> b -> Maybe a -> b

考虑一下这个定义可能有什么含义，因为它必须对所有的a和b进行定义，而不知道其他类型的信息。作为进一步的提示，请看看Data.Maybe中是否已经定义了一个具有类似类型的函数——也许（哈哈），这会给你一些想法。

- K. A. Buhr

---

我认为 foldMaybe 应该有这种类型并不明显 - 我会说 b -> (a -> b) -> Maybe a -> b 更加“明显”，因为 foldList 的类型（几乎）对应于列表的自然消除器，而 b -> (a -> b) -> Maybe a -> b 是 Maybe 的自然消除器 - 实际上，在 Data.Maybe 中有一个具有此类型的函数（maybe）。没有具有该类型的 foldMaybe，除了 Data.Foldable.foldr，它具有更通用的类型（而此函数的类型与 Maybe 或甚至 List 几乎没有关系）。 - user2407038

好的观点，但是为了澄清，我的意思是很明显foldr应该通过与列表类型的显然类比来具有Maybe类型，而不一定是最自然的Maybe折叠看起来像foldr。我已经编辑了答案以使其更清晰。实际上，在当前版本的Haskell中，Data.Foldable.foldr就是Prelude.foldr，并且它的类型确实会针对列表和Maybes进行特化，即使foldr不是Maybe的“自然”折叠方式。 - K. A. Buhr