为什么Functor类型类不包括fold方法？

Question

为什么类型类Functor只有成员fmap？我经常发现对数据类型进行折叠很有用。比如，层次结构的数据类型，如树形结构。

请注意，map是fold的一种特殊情况，即后者更基本。我想我可以接受它现在的状态，但也许有一个原因？

- akonsu

---

你如何定义在IO上的 fold，它是一个Functor但不是Foldable？ - Zeta

fmap 如何是 fold 的特殊情况？我无法想象你如何能够用其中一个实现另一个，这就是我所谓的“更基本”的概念。 - Dietrich Epp

我的帖子中的 fmap 是一个打字错误。我指的是 map。 - akonsu

Answer 1

因为Functor是一种非常通用的对象，不是所有Functor都支持折叠操作。例如，有一个实例¹

instance Functor (a ->) where
     -- > fmap :: (b -> c) -> (a -> b) -> (a -> c)
     fmap f g = g . f

然而，尽管对于所有的 a，(a ->) 都是一个 Functor，但对于无限的 a，没有一个合理的 fold 定义。（顺便说一句，通常情况下 'fold' 是一个catamorphism，这意味着对于每个 functor，它都有一个不同的类型。 Foldable 类型类为类似序列的类型定义了它。）

考虑一下 Integer -> Integer 的 foldr 定义会是什么样子；最外层的应用会是什么？

它的值会是什么？

foldr (\ _ n -> 1 + n) 0 (\ n -> n + 1)

如果没有更多关于参数类型的结构信息，fold 的合理定义是不存在的。

¹ 由于某种原因，(a ->) 不是合法的 Haskell 语法。但我仍将使用它作为 (->) a 更易读的版本，因为我认为这对新手来说更容易理解。

- Jonathan Cast

---

我想我明白我的错误了：map 只是针对列表（或者其他一些东西）而言的 fold 的特例，而不是普遍适用的。谢谢。 - akonsu

是的，在列表上，fold 比其他类型（尤其是任意树）更加强大。从形式上来说（忽略惰性），列表函子是自由幺半函子，它是从幺半到集合的遗忘函子的左伴随；然后，一般的 fold 函数是列表函子和遗忘函子之间的同态集伴随的一个方向。因此，列表上的每个幺半同态（包括 map）都可以通过某个 fold 实例给出。 - Jonathan Cast

Answer 2

你需要的抽象概念是Foldable：这是一个类型类，提供各种形式的fold（折叠）。

对于可以“在改变时折叠”的东西，也有Traversable，可与列表的mapAccumL函数相比较。

实际上，指出@DietrichEpp的话是不正确的，因为这里有可能非Functor实例的Foldable。详情请参见此处。

然而，map是mapAccumL的特殊情况（毫不奇怪，考虑到名称），因此Traversable的定义要求该事物也是Functor和Foldable。

- Joachim Breitner

---

谢谢。这很有趣。我是一个初学者，我模糊地理解你在说什么。总的来说，似乎很困惑，一个“Functor”不一定是一个“Foldable”。鉴于“map”是基于“fold”定义的... - akonsu

这正是原因所在：如果*fold是基于map定义的*，那么我们就可以为每个Functor定义fold，因为我们可以利用现有的map免费获得fold。 - Lynn

@DietrichEpp的提示是正确的；有可能存在非Functor实例的Foldable（https://dev59.com/rmsy5IYBdhLWcg3wtwa9）。 - Lynn

抱歉，我混淆了“fold”和“traverse”，已经相应地修正了答案。 - Joachim Breitner