第 7 章：函子（Functors）
原文：Bartosz Milewski, Category Theory for Programmers, Scala Edition, Chapter 7. 原书 PDF、
.tex源文件及相关图像采用 CC BY-SA 4.0；本译文按同一许可发布。
冒着听起来像坏掉的唱片一样反复唠叨的风险，我还是要这样说函子：函子是一个非常简单却非常强大的想法。范畴论中充满了这种简单却强大的想法。函子是范畴之间的映射。给定两个范畴 $C$ 和 $D$，函子 $F$ 把 $C$ 中的对象映射到 $D$ 中的对象，也就是说，它是对象上的函数。如果 $a$ 是 $C$ 中的对象，我们把它在 $D$ 中的像写作 $F a$（不用括号）。
但范畴不只是对象；它还包含连接对象的态射。函子也会映射态射，也就是说，它还是态射上的函数。不过，它不会随意映射态射，而是会保留连接关系。所以，如果 $C$ 中的态射 $f$ 连接对象 $a$ 与对象 $b$：
$$ f :: a \to b $$
那么 $f$ 在 $D$ 中的像 $F f$，会连接 $a$ 的像与 $b$ 的像：
$$ F f :: F a \to F b $$
（这里混用了数学记法和 Haskell 记法，但到现在为止应该已经能看懂了。把函子应用到对象或态射时，我不会写括号。）
可以看到，函子保留了范畴的结构：在一个范畴中相连的东西，在另一个范畴中仍然相连。但范畴的结构还有更多内容：态射还可以组合。如果 $h$ 是 $f$ 与 $g$ 的组合：
$$ h = g . f $$
我们希望它在 $F$ 下的像，是 $f$ 与 $g$ 的像的组合：
$$ F h = F g . F f $$
最后，我们还希望 $C$ 中所有恒等态射都被映射为 $D$ 中的恒等态射：
F id_a = id_{Fa}
这里，id_a 是对象 $a$ 上的恒等态射，id_{F a} 是 $F a$ 上的恒等态射。注意，这些条件让函子比普通函数受限得多。函子必须保留范畴结构。如果你把一个范畴想象成由态射网络粘合起来的一组对象，那么函子不允许在这块织物上撕开任何裂口。它可以把对象压扁到一起，也可以把多个态射粘成一个，但绝不能把东西撕裂。这个“不可撕裂”约束类似于你可能在微积分中见过的连续性条件。
从这个意义上说，函子是“连续的”（尽管对函子来说，还存在更严格的连续性概念）。就像函数一样，函子既可以折叠，也可以嵌入。当源范畴远小于目标范畴时，嵌入这一面会更明显。极端情况下，源范畴可以是平凡的单对象范畴，也就是只有一个对象和一个态射（恒等态射）的范畴。从单对象范畴到任意其他范畴的函子，只是在那个范畴中选择一个对象。这与单元素集合出发的态射在目标集合中选择元素的性质完全类似。
最大程度折叠的函子称为常函子 $\Delta_c$。它把源范畴中的每个对象都映射到目标范畴中选定的对象 $c$。它也把源范畴中的每个态射都映射到恒等态射 $id_c$。它就像黑洞，把一切压缩成一个奇点。讨论极限与余极限时，我们还会看到更多关于这个函子的内容。
7.1 编程中的函子（Functors in Programming）
让我们回到地面，谈谈编程。我们有类型与函数构成的范畴。可以讨论把这个范畴映射到自身的函子；这样的函子称为自函子（endofunctor）。那么，类型范畴中的自函子是什么？首先，它把类型映射到类型。我们已经见过这种映射的例子，只是当时可能还没有意识到它们正是这样的映射。我说的是由其他类型参数化的类型定义。来看几个例子。
7.1.1 Maybe 函子（The Maybe Functor）
Maybe 的定义是一个从类型 a 到类型 Maybe a 的映射：
data Maybe a = Nothing | Just a
sealed trait Option[+A]
case object None extends Option[Nothing]
case class Some[A](a: A) extends Option[A]
这里有一个重要的细节：Maybe 本身不是类型，而是类型构造器。必须给它一个类型参数，比如 Int 或 Bool，才能把它变成类型。没有参数的 Maybe 表示类型上的函数。
但我们能把 Maybe 变成函子吗？（从现在开始，在编程语境中说函子时，我几乎总是指自函子。）函子不仅是对象（这里是类型）上的映射，也是态射（这里是函数）上的映射。对任意从 a 到 b 的函数：
f :: a -> b
val f: A => B
我们希望生成一个从 Maybe a 到 Maybe b 的函数。为了定义这样的函数，需要考虑两个情形，对应 Maybe 的两个构造器。Nothing 的情形很简单：仍然返回 Nothing。如果参数是 Just，就把函数 f 作用到其中的内容上。所以 f 在 Maybe 下的像是这个函数：
f' :: Maybe a -> Maybe b
f' Nothing = Nothing
f' (Just x) = Just (f x)
def f1[A, B](f: A => B): Option[A] => Option[B] = {
case None => None
case Some(x) => Some(f(x))
}
（顺便说一句，Haskell 允许在变量名里使用撇号，在这种场景下非常方便。）
在 Haskell 中，我们把函子中“映射态射”的那一部分实现为一个名叫 fmap 的高阶函数。对 Maybe 来说，它有如下签名：
fmap :: (a -> b) -> (Maybe a -> Maybe b)
def fmap[A, B](f: A => B): Option[A] => Option[B]
我们常说 fmap 会提升一个函数。提升后的函数作用在 Maybe 值上。像往常一样，由于柯里化，这个签名可以用两种方式解释：它可以是一个单参数函数，参数本身是函数 (a -> b)，返回函数 (Maybe a -> Maybe b)；也可以是一个双参数函数，返回 Maybe b：
fmap :: (a -> b) -> Maybe a -> Maybe b
def fmap[A, B](f: A => B)(fa: Option[A]): Option[B]
根据前面的讨论，Maybe 的 fmap 可以这样实现：
fmap _ Nothing = Nothing
fmap f (Just x) = Just (f x)
def fmap[A, B](f: A => B): Option[A] => Option[B] = {
case None => None
case Some(x) => Some(f(x))
}
要说明类型构造器 Maybe 连同函数 fmap 构成一个函子，我们必须证明 fmap 保留恒等态射和组合。这些性质称为“函子律”，但它们只是确保范畴结构被保留下来。
7.1.2 等式推理（Equational Reasoning）
为了证明函子律，我会使用等式推理，这是 Haskell 中常见的证明技巧。它利用了这样一个事实：Haskell 函数以等式的形式定义，左边等于右边。你总是可以把一边替换成另一边，必要时重命名变量以避免名称冲突。可以把这看作内联函数，或者反过来，把表达式重构成函数。以恒等函数为例：
id x = x
def identity[A](x: A) = x
如果在某个表达式中看到 id y，就可以把它替换成 y（内联）。进一步说，如果看到 id 作用在某个表达式上，比如 id (y + 2)，也可以把它替换成表达式本身 (y + 2)。这个替换也能反向使用：可以把任意表达式 e 替换成 id e（重构）。
如果函数通过模式匹配定义，你可以独立使用每个子定义。例如，给定上面对 fmap 的定义，你可以把 fmap f Nothing 替换成 Nothing，也可以反过来。来看实际做法。先从保留恒等态射开始：
fmap id = id
fmap(identity) == identity
需要考虑两种情形：Nothing 和 Just。第一种情形如下（我使用 Haskell 伪代码把左边变换到右边）：
fmap id Nothing
= { definition of fmap }
Nothing
= { definition of id }
id Nothing
注意，在最后一步中，我反向使用了 id 的定义。我把表达式 Nothing 替换成了 id Nothing。在实践中，做这类证明时常常是“两头点蜡烛”，从两端往中间烧，直到在中间遇到同一个表达式；这里遇到的就是 Nothing。第二种情形也很简单：
fmap id (Just x)
= { definition of fmap }
Just (id x)
= { definition of id }
Just x
= { definition of id }
id (Just x)
现在说明 fmap 保留组合：
fmap (g . f) = fmap g . fmap f
fmap(g compose f) == fmap(g) compose fmap(f)
先看 Nothing 的情形：
fmap (g . f) Nothing
= { definition of fmap }
Nothing
= { definition of fmap }
fmap g Nothing
= { definition of fmap }
fmap g (fmap f Nothing)
再看 Just 的情形：
fmap (g . f) (Just x)
= { definition of fmap }
Just ((g . f) x)
= { definition of composition }
Just (g (f x))
= { definition of fmap }
fmap g (Just (f x))
= { definition of fmap }
fmap g (fmap f (Just x))
= { definition of composition }
(fmap g . fmap f) (Just x)
值得强调的是，等式推理不适用于带副作用的 C++ 风格“函数”。考虑下面的代码：
int square(int x) {
return x * x;
}
int counter() {
static int c = 0;
return c++;
}
double y = square(counter());
使用等式推理时，你可能会把 square 内联成：
double y = counter() * counter();
这显然不是合法变换，也不会产生相同结果。尽管如此，如果你把 square 实现为宏，C++ 编译器仍会尝试用这种等式推理，结果会非常糟糕。
7.1.3 Optional
函子在 Haskell 中很容易表达，但只要一门语言支持泛型编程和高阶函数，也可以在其中定义函子。考虑 C++ 中类似 Maybe 的模板类型 optional。下面是一个实现草图（真实实现要复杂得多，需要处理参数传递的各种方式、拷贝语义，以及 C++ 特有的资源管理问题）：
template<class T>
class optional {
bool _isValid; // the tag
T _v;
public:
optional()
: _isValid(false) {} // Nothing
optional(T x) : _isValid(true) , _v(x) {} // Just
bool isValid() const { return _isValid; }
T val() const { return _v; }
};
这个模板提供了函子定义的一部分：类型映射。它把任意类型 T 映射到新类型 optional<T>。下面定义它在函数上的作用：
template<class A, class B>
std::function<optional<B>(optional<A>)>
fmap(std::function<B(A)> f) {
return [f](optional<A> opt) {
if (!opt.isValid())
return optional<B>{};
else
return optional<B>{ f(opt.val()) };
};
}
这是一个高阶函数，接受一个函数作为参数并返回一个函数。下面是它的非柯里化版本：
template<class A, class B>
optional<B> fmap(std::function<B(A)> f, optional<A> opt) {
if (!opt.isValid())
return optional<B>{};
else
return optional<B>{ f(opt.val()) };
}
也可以把 fmap 做成 optional 的模板方法。选择太多反而让 C++ 中抽象函子模式变成了问题。Functor 应该是一个要继承的接口吗（很遗憾，不能有模板虚函数）？它应该是柯里化的自由模板函数，还是非柯里化的自由模板函数？C++ 编译器能正确推断缺失的类型吗，还是必须显式指定？
考虑一种情况：输入函数 f 把 int 映射到 bool。编译器会如何推断 g 的类型？
auto g = fmap(f);
尤其是将来如果有多个函子都重载了 fmap，情况会如何？（我们很快会看到更多函子。）
7.1.4 类型类（Typeclasses）
那么 Haskell 如何抽象函子呢？它使用类型类机制。类型类定义了一族支持公共接口的类型。例如，支持相等性的对象类可以这样定义：
class Eq a where
(==) :: a -> a -> Bool
trait Eq[A] {
def ===(x: A, y: A): Boolean
}
这个定义说明，如果类型 a 支持运算符 (==)，该运算符接受两个 a 类型参数并返回 Bool，那么类型 a 就属于 Eq 类。如果想告诉 Haskell 某个具体类型属于 Eq，必须声明它是该类的实例，并提供 (==) 的实现。例如，给定二维点 Point 的定义（两个 Float 的积类型）：
data Point = Pt Float Float
case class Point(x: Float, y: Float)
可以这样定义点的相等性：
instance Eq Point where
(Pt x y) == (Pt x' y') = x == x' && y == y'
implicit val pointEq = new Eq[Point] {
def ===(a1: Point, a2: Point): Boolean =
a1.x == a2.x && a1.y == a2.y
}
这里我把运算符 (==)（也就是正在定义的那个运算符）放在中缀位置，位于两个模式 (Pt x y) 和 (Pt x' y') 之间。函数体跟在单个等号之后。一旦 Point 被声明为 Eq 的实例，就可以直接比较点是否相等。注意，与 C++ 或 Java 不同，定义 Point 时不必指定 Eq 类（或接口）；可以之后在客户端代码中再做这件事。
类型类也是 Haskell 重载函数（和运算符）的唯一机制。我们需要用它为不同函子重载 fmap。不过有一个复杂之处：函子不是作为类型定义的，而是作为类型映射，也就是类型构造器定义的。我们需要的类型类不是像 Eq 那样的一族类型，而是一族类型构造器。幸运的是，Haskell 类型类既能作用于类型，也能作用于类型构造器。因此，Functor 类定义如下：
class Functor f where
fmap :: (a -> b) -> f a -> f b
trait Functor[F[_]] {
def fmap[A, B](f: A => B)(fa: F[A]): F[B]
}
它规定：如果存在一个具有指定类型签名的函数 fmap，那么 f 就是一个 Functor。小写的 f 是一个类型变量，类似于类型变量 a 和 b。不过，编译器可以通过它的用法推断出它表示类型构造器而不是类型：它会作用在其他类型上，比如 f a 和 f b。相应地，声明 Functor 实例时，必须给出一个类型构造器，Maybe 就是这样：
instance Functor Maybe where
fmap _ Nothing = Nothing
fmap f (Just x) = Just (f x)
implicit val optionFunctor = new Functor[Option] {
def fmap[A, B](f: A => B)(fa: Option[A]): Option[B] = fa match {
case None => None
case Some(x) => Some(f(x))
}
}
顺便说一句，Functor 类以及很多简单数据类型（包括 Maybe）的实例定义，都是标准 Prelude 库的一部分。
7.1.5 C++ 中的函子（Functor in C++）
能不能在 C++ 中尝试同样的方法？类型构造器对应模板类，例如 optional。类比一下，我们可以用模板模板参数 F 来参数化 fmap。语法如下：
template<template<class> F, class A, class B>
F<B> fmap(std::function<B(A)>, F<A>);
我们希望能够为不同函子特化这个模板。不幸的是，C++ 禁止对函数模板做偏特化。不能这样写：
template<class A, class B>
optional<B> fmap<optional>(std::function<B(A)> f, optional<A> opt)
因此，只能退回到函数重载，这又把我们带回了最初那个非柯里化 fmap 定义：
template<class A, class B>
optional<B> fmap(std::function<B(A)> f, optional<A> opt) {
if (!opt.isValid())
return optional<B>{};
else
return optional<B>{ f(opt.val()) };
}
这个定义可以工作，但只是因为 fmap 的第二个参数选择了重载。它完全无视更泛化的 fmap 定义。
7.1.6 List 函子（The List Functor）
为了对函子在编程中的角色建立一些直觉，需要看更多例子。任何由另一个类型参数化的类型，都可以作为函子的候选。泛型容器由它们存储的元素类型参数化，所以来看一个非常简单的容器：列表。
data List a = Nil | Cons a (List a)
sealed trait List[+E]
case object Nil extends List[Nothing]
case class Cons[E](h: E, t: List[E]) extends List[E]
我们有类型构造器 List，它把任意类型 a 映射到类型 List a。为了说明 List 是函子，必须定义函数的提升：给定函数 a -> b，定义函数 List a -> List b：
fmap :: (a -> b) -> (List a -> List b)
def fmap[A, B](f: A => B): List[A] => List[B]
作用在 List a 上的函数必须考虑两种情形，对应两个列表构造器。Nil 的情形很平凡，只要返回 Nil 即可；空列表没有太多可做的事。Cons 的情形稍微棘手，因为它涉及递归。
先退一步看看我们试图做什么。我们有一个 a 的列表，一个把 a 变成 b 的函数 f，并且想生成一个 b 的列表。显而易见的做法是用 f 把列表中的每个元素从 a 变成 b。但在实践中该怎么做？非空列表被定义为一个头部和一个尾部的 Cons。我们把 f 应用到头部，并把提升后的（fmapped）f 应用到尾部。这是一个递归定义，因为我们在用提升后的 f 定义提升后的 f：
fmap f (Cons x t) = Cons (f x) (fmap f t)
def fmap[A, B](f: A => B)(fa: List[A]): List[B] = fa match {
case Cons(x, t) => Cons(f(x), fmap(f)(t))
}
注意，右边的 fmap f 被应用到一个比正在定义的列表更短的列表上，也就是它的尾部。我们向越来越短的列表递归，所以最终必然会到达空列表 Nil。而前面已经决定，fmap f 作用在 Nil 上会返回 Nil，递归也就终止。为了得到最终结果，我们用 Cons 构造器把新的头部 (f x) 和新的尾部 (fmap f t) 组合起来。合在一起，列表函子的实例声明如下：
instance Functor List where
fmap _ Nil = Nil
fmap f (Cons x t) = Cons (f x) (fmap f t)
implicit val listFunctor = new Functor[List] {
def fmap[A, B](f: A => B)(fa: List[A]): List[B] = fa match {
case Nil => Nil
case Cons(x, t) => Cons(f(x), fmap(f)(t))
}
}
如果你更熟悉 C++，可以考虑 std::vector，它可以看作最通用的 C++ 容器。对 std::vector 的 fmap 实现只是对 std::transform 的一层薄封装：
template<class A, class B>
std::vector<B> fmap(std::function<B(A)> f, std::vector<A> v) {
std::vector<B> w;
std::transform( std::begin(v)
, std::end(v)
, std::back_inserter(w)
, f);
return w;
}
例如，可以用它对一串数字求平方：
std::vector<int> v{ 1, 2, 3, 4 };
auto w = fmap([](int i) { return i*i; }, v);
std::copy( std::begin(w)
, std::end(w)
, std::ostream_iterator(std::cout, ", "));
大多数 C++ 容器之所以是函子，是因为它们实现了可以传给 std::transform 的迭代器，而 std::transform 是 fmap 更原始的近亲。不幸的是，函子的简单性被迭代器和临时对象带来的常规杂乱掩盖了（参见上面的 fmap 实现）。值得高兴的是，新的 C++ range 库提案让 range 的函子性质变得明显得多。
7.1.7 Reader 函子（The Reader Functor）
现在你可能已经建立了一些直觉，例如把函子看作某种容器。让我展示一个乍看之下非常不同的例子。考虑一个映射，它把类型 a 映射到返回 a 的函数类型。我们还没有真正深入讨论函数类型，完整的范畴论处理还在后面，但作为程序员，我们对它们已经有一些理解。
在 Haskell 中，函数类型使用箭头类型构造器 (->) 构造。这个构造器接受两个类型：参数类型和结果类型。你已经见过它的中缀形式 a -> b，但如果加上括号，它也可以用作前缀形式：
(->) a b
Function1[A, B]
// or
A => B
就像普通函数一样，带有多个参数的类型函数也可以被部分应用。所以，当我们只给箭头提供一个类型参数时，它仍然期待另一个参数。因此：
(->) a
// with the Kind Projector plugin
Function1[A, ?] or A => ?
是一个类型构造器。它还需要一个类型 b，才能生成完整类型 a -> b。就目前而言，它定义了一整族由 a 参数化的类型构造器。看看这是否也是一族函子。
处理两个类型参数可能有点令人困惑，所以做一些重命名。按照前面的函子定义，把参数类型称为 r，把结果类型称为 a。于是我们的类型构造器接受任意类型 a，并把它映射到类型 r -> a。为了说明它是函子，我们想把函数 a -> b 提升为一个函数，这个函数接受 r -> a，返回 r -> b。这些类型分别由类型构造器 (->) r 作用在 a 和 b 上形成。下面是 fmap 在这个情形下的类型签名：
fmap :: (a -> b) -> (r -> a) -> (r -> b)
def fmap[A, B](f: A => B)(g: R => A): R => B
我们必须解决下面这个谜题：给定函数 f :: a -> b 和函数 g :: r -> a，创建一个函数 r -> b。这两个函数只有一种组合方式，而结果正是我们需要的。所以 fmap 的实现如下：
instance Functor ((->) r) where
fmap f g = f . g
// with the Kind Projector plugin:
implicit def function1Functor[R] = new Functor[R => ?] {
def fmap[A, B](f: A => B)(g: R => A): R => B =
f compose g
}
它就是可以工作！如果喜欢更简洁的记法，可以进一步注意到，组合可以写成前缀形式：
fmap f g = (.) f g
def fmap[A, B]: (A => B) => (R => A) => (R => B) =
f => g => f compose g
还可以省略参数，得到两个函数之间的直接等式：
fmap = (.)
def fmap[A, B]: (A => B) => (R => A) => (R => B) =
_ compose
类型构造器 (->) r 与上面这个 fmap 实现合在一起，称为 reader 函子。
7.2 作为容器的函子（Functors as Containers）
我们已经在编程语言中见过一些函子例子，它们定义了通用容器，或者至少定义了包含某个值的对象，而这个值的类型正是它们被参数化的类型。reader 函子看起来像个异类，因为我们通常不把函数看作数据。但我们已经见过，纯函数可以被记忆化，函数执行可以变成查表。表就是数据。反过来，由于 Haskell 的惰性，传统容器（例如列表）实际上也可能被实现为函数。例如，考虑自然数的无限列表，它可以紧凑地定义为：
nats :: [Integer]
nats = [1..]
// just imagine for a moment
// that Scala has lazy lists
def nats: Stream[Int] = Stream.from(1)
第一行中，一对方括号是 Haskell 内置的列表类型构造器。第二行中，方括号用于创建列表字面量。显然，这样的无限列表不能存储在内存中。编译器会把它实现为一个按需生成 Integer 的函数。Haskell 有效地模糊了数据与代码之间的界限。
列表可以被看作函数，函数也可以被看作把参数映射到结果的表。如果函数的定义域有限且不太大，后一种看法甚至可以用于实践。不过，把 strlen 实现成查表并不实际，因为不同字符串有无限多种。作为程序员，我们不喜欢无穷；但在范畴论中，你会学会把无穷当早餐吃。无论是所有字符串构成的集合，还是宇宙过去、现在与未来所有可能状态的集合，我们都能处理！
所以，我喜欢把函子对象（由自函子生成的类型的对象）想成包含了它所参数化类型的一个或多个值，即便这些值并不实际存在于那里。
一个函子例子是 C++ 的 std::future，它可能在某个时刻包含一个值，但不能保证一定如此；如果想访问它，可能会阻塞等待另一个线程完成执行。另一个例子是 Haskell 的 IO 对象，它可能包含用户输入，也可能包含我们的宇宙在显示器上展示 “Hello World!” 之后的未来版本。
根据这种解释，函子对象是某种可能包含其参数类型的一个或多个值的东西。或者，它也可能包含生成这些值的配方。我们完全不关心能不能访问这些值；这完全是可选的，并且在函子的范围之外。我们关心的只是能否用函数操纵这些值。如果这些值可访问，我们应该能看到操纵的结果。如果不可访问，那么我们关心的只是这些操纵能正确组合，并且用恒等函数操纵不会改变任何东西。
为了展示我们有多么不关心能否访问函子对象内部的值，下面是一个完全忽略其参数 a 的类型构造器：
data Const c a = Const c
case class Const[C, A](v: C)
Const 类型构造器接受两个类型 c 和 a。就像对箭头构造器所做的那样，我们将部分应用它来创建一个函子。数据构造器（也叫 Const）只接受一个 c 类型的值。它完全不依赖 a。这个类型构造器的 fmap 类型为：
fmap :: (a -> b) -> Const c a -> Const c b
def fmap[A, B](f: A => B)(ca: Const[C, A]): Const[C, B]
因为这个函子忽略自己的类型参数，fmap 的实现也可以随意忽略它的函数参数；这个函数没有东西可以作用：
instance Functor (Const c) where
fmap _ (Const v) = Const v
implicit def constFunctor[C] = new Functor[Const[C, ?]] {
def fmap[A, B](f: A => B)(ca: Const[C, A]): Const[C, B] =
Const(ca.v)
}
在 C++ 中这可能更清楚一些（我从没想到自己会说这句话！），因为 C++ 更明确地区分类型参数和值：类型参数是编译期的，值是运行期的。
template<class C, class A>
struct Const {
Const(C v) : _v(v) {}
C _v;
};
C++ 的 fmap 实现也会忽略函数参数，本质上只是把 Const 参数重新转换为另一种 Const，而不改变它的值：
template<class C, class A, class B>
Const<C, B> fmap(std::function<B(A)> f, Const<C, A> c) {
return Const<C, B>{c._v};
}
尽管它看起来很奇怪，Const 函子在许多构造中都扮演重要角色。在范畴论中，它是前面提到的 $\Delta_c$ 函子的一个特例，也就是黑洞的自函子版本。将来还会更多地见到它。
7.3 函子组合（Functor Composition）
不难说服自己，范畴之间的函子可以组合，就像集合之间的函数可以组合一样。两个函子的组合在作用于对象时，就是各自对象映射的组合；作用于态射时也类似。经过两个函子之后，恒等态射最终还是恒等态射，态射组合最终还是态射组合。这里确实没有太多神秘之处。特别是，自函子的组合很容易。
还记得函数 maybeTail 吗？我用 Haskell 内置列表实现把它重写一下：
maybeTail :: [a] -> Maybe [a]
maybeTail [] = Nothing
maybeTail (x:xs) = Just xs
def maybeTail[A]: List[A] => Option[List[A]] = {
case Nil => None
case Cons(x, xs) => Some(xs)
}
（我们之前称为 Nil 的空列表构造器，在这里被替换成了一对空方括号 []。Cons 构造器则被替换成了中缀运算符 :，也就是冒号。）
maybeTail 的结果类型是两个函子 Maybe 和 [] 作用在 a 上的组合。这两个函子各自都配有自己的 fmap 版本，但如果想把某个函数 f 应用到这个组合结构，也就是 Maybe 列表的内容上，该怎么办？我们必须穿过两层函子。可以用 fmap 穿过外层 Maybe。但不能直接把 f 送进 Maybe，因为 f 不能作用在列表上。必须把 (fmap f) 送进去，让它作用在内层列表上。
例如，看看如何对一个 Maybe 整数列表中的元素求平方：
square x = x * x
mis :: Maybe [Int]
mis = Just [1, 2, 3]
mis2 = fmap (fmap square) mis
def square: Int => Int = x => x * x
val mis: Option[List[Int]] =
Some(Cons(1, Cons(2, Cons(3, Nil))))
val mis2 = optionFunctor.
fmap(listFunctor.fmap(square))(mis)
编译器在分析类型之后，会弄清楚外层 fmap 应该使用 Maybe 实例中的实现，内层 fmap 应该使用列表函子实现。上面的代码可以改写成下面这样，这一点可能不是立刻显然：
mis2 = (fmap . fmap) square mis
def fmapO[A, B]: (A => B) => Option[A] => Option[B] =
optionFunctor.fmap
def fmapL[A, B]: (A => B) => List[A] => List[B] =
listFunctor.fmap
def fmapC[A, B]: (A => B) => Option[List[A]] => Option[List[B]] =
fmapO.compose(fmapL)
val mis2 = fmapC(square)(mis)
但请记住，fmap 可以被看作只接受一个参数的函数：
fmap :: (a -> b) -> (f a -> f b)
def fmap[F[_], A, B]: (A => B) => (F[A] => F[B])
在我们的例子中，(fmap . fmap) 中的第二个 fmap 接受的参数是：
square :: Int -> Int
def square: Int => Int
并返回一个类型如下的函数：
[Int] -> [Int]
List[Int] => List[Int]
第一个 fmap 随后接受这个函数，并返回一个函数：
Maybe [Int] -> Maybe [Int]
Option[List[Int]] => Option[List[Int]]
最后，这个函数被应用到 mis 上。所以，两个函子的组合也是一个函子，它的 fmap 就是相应两个 fmap 的组合。
回到范畴论：函子组合显然是结合的（对象映射是结合的，态射映射也是结合的）。每个范畴中也有一个平凡的恒等函子：它把每个对象映射到自身，把每个态射映射到自身。所以函子拥有某个范畴中态射所具有的一切性质。但那会是什么范畴呢？它必须是一个以范畴为对象、以函子为态射的范畴。这是范畴的范畴。
不过，所有范畴构成的范畴将不得不包含它自身，于是会陷入让“所有集合的集合”不可能存在的那类悖论。确实存在一个所有小范畴构成的范畴，称为 $Cat$（它是大的，所以不能成为自身的成员）。小范畴是指其中对象形成集合的范畴，而不是比集合更大的东西。请注意，在范畴论中，即便是无限不可数集合也被认为是“小的”。
我提到这些，是因为我觉得能够在多个抽象层次上识别出同样的结构反复出现，这件事相当惊人。稍后我们还会看到，函子本身也形成范畴。
7.4 挑战（Challenges）
- 能否通过如下定义把
Maybe类型构造器变成函子？
fmap _ _ = Nothing
它会忽略两个参数。（提示：检查函子律。）
- 证明 reader 函子的函子律。提示：真的很简单。
- 用你第二喜欢的语言实现 reader 函子（第一喜欢的当然是 Haskell）。
- 证明列表函子的函子律。假设这些定律对你正在处理的列表尾部成立（换句话说，使用归纳法）。