第 15 章：Yoneda 引理（The Yoneda Lemma）
原文：Bartosz Milewski, Category Theory for Programmers, Scala Edition, Chapter 15. 原书 PDF、
.tex源文件及相关图像采用 CC BY-SA 4.0；本译文按同一许可发布。
范畴论中的大多数构造，都是对数学中其他更具体领域里的结果所作的推广。积、余积、幺半群、指数对象等等，在范畴论出现很久以前就已经为人所知。它们在数学的不同分支中也许有不同名字。集合论中的笛卡尔积、序理论中的 meet、逻辑中的合取，全都是“范畴积”这个抽象思想的具体例子。
Yoneda 引理在这一点上格外突出：它是一个关于一般范畴的宏大陈述，在数学其他分支中几乎没有先例。有人说它最接近的类比是群论中的 Cayley 定理（每个群都同构于某个集合上的置换群）。
Yoneda 引理的设定是任意范畴 $C$，以及一个从 $C$ 到 $Set$ 的函子 $F$。上一节已经看到，有些 $Set$ 值函子是可表示的，也就是说，它们同构于 hom 函子。Yoneda 引理告诉我们，所有 $Set$ 值函子都可以通过自然变换从 hom 函子得到，并且它显式枚举了所有这样的自然变换。
在谈到自然变换时，我提到自然性条件可能相当严格。当你在某个对象处定义自然变换的一个分量时，自然性可能强到足以把这个分量“运输”到另一个通过态射与它相连的对象上。源范畴和目标范畴中对象之间的箭头越多，运输自然变换分量时受到的约束就越多。$Set$ 恰好是一个箭头非常丰富的范畴。
Yoneda 引理告诉我们，hom 函子与任意其他函子 $F$ 之间的自然变换，完全由它在一个点上的单个分量值决定！自然变换的其余部分都由自然性条件推出。
所以让我们回顾 Yoneda 引理中涉及的两个函子之间的自然性条件。第一个函子是 hom 函子。它把 $C$ 中任意对象 $x$ 映射为态射集合 $C(a, x)$，其中 $a$ 是 $C$ 中固定的对象。我们还见过，它把从 $x$ 到 $y$ 的任意态射 $f$ 映射为 $C(a, f)$。
第二个函子是任意 $Set$ 值函子 $F$。
把这两个函子之间的自然变换称为 $\alpha$。因为我们在 $Set$ 中工作，自然变换的分量，比如 $\alpha_x$ 或 $\alpha_y$，只是集合之间的普通函数：
alpha_x :: C(a, x) -> F x
alpha_y :: C(a, y) -> F y
由于这些只是函数，我们可以观察它们在具体点上的取值。但 $C(a, x)$ 这个集合中的一个点是什么？关键观察是：集合 $C(a, x)$ 中的每个点，同时也是一个从 $a$ 到 $x$ 的态射 $h$。
因此，$\alpha$ 的自然性方块：
alpha_y . C(a, f) = F f . alpha_x
逐点作用在 $h$ 上，就变成：
alpha_y (C(a, f) h) = (F f) (alpha_x h)
你可能还记得上一节中 hom 函子 $C(a, -)$ 在态射 $f$ 上的作用被定义为预组合：
C(a, f) h = f . h
于是得到：
alpha_y (f . h) = (F f) (alpha_x h)
只要把它特化到 $x = a$ 的情形，就能看出这个条件有多强。
在这种情况下，$h$ 变成从 $a$ 到 $a$ 的态射。我们知道至少存在这样一个态射，也就是 $h = id_a$。把它代入：
alpha_y f = (F f) (alpha_a id_a)
注意刚刚发生了什么：左边是 $\alpha_y$ 对 $C(a, y)$ 中任意元素 $f$ 的作用。而它完全由 $\alpha_a$ 在 $id_a$ 处的单个值决定。我们可以任意选择这样的一个值，它会生成一个自然变换。由于 $\alpha_a$ 的值位于集合 $F a$ 中，$F a$ 中任意一个点都会定义某个 $\alpha$。
反过来，给定任意从 $C(a, -)$ 到 $F$ 的自然变换 $\alpha$，可以在 $id_a$ 处求值，得到 $F a$ 中的一个点。
我们刚刚证明了 Yoneda 引理：
从 $C(a, -)$ 到 $F$ 的自然变换，与 $F a$ 的元素之间存在一一对应。
换句话说：
Nat(C(a, -), F) ~= F a
或者，如果用 $[C, Set]$ 表示 $C$ 与 $Set$ 之间的函子范畴，那么自然变换的集合只是该范畴中的一个 hom-set，因此可以写作：
[C, Set](C(a, -), F) ~= F a
稍后我会解释这个对应实际上如何成为一个自然同构。
现在试着为这个结果建立一些直觉。最令人惊讶的是，整个自然变换都从一个成核点结晶出来：我们在 $id_a$ 处赋给它的值。它从这一点出发，沿着自然性条件扩散，淹没 $C$ 在 $Set$ 中的像。
所以先考虑 $C$ 在 $C(a, -)$ 下的像。
先从 $a$ 自身的像开始。在 hom 函子 $C(a, -)$ 下，$a$ 被映射到集合 $C(a, a)$。另一方面，在函子 $F$ 下，它被映射到集合 $F a$。自然变换的分量 $\alpha_a$ 是从 $C(a, a)$ 到 $F a$ 的某个函数。我们只关注集合 $C(a, a)$ 中的一个点，也就是对应态射 $id_a$ 的点。为了强调它只是集合中的一个点，把它称为 $p$。分量 $\alpha_a$ 应该把 $p$ 映射到 $F a$ 中的某个点 $q$。我会说明，对 $q$ 的任意选择都会导出唯一的自然变换。
第一个断言是：一个点 $q$ 的选择会唯一决定函数 $\alpha_a$ 的其余部分。确实，取 $C(a, a)$ 中任意另一个点 $p'$，它对应某个从 $a$ 到 $a$ 的态射 $g$。Yoneda 引理的魔力就在这里发生：$g$ 可以被看作集合 $C(a, a)$ 中的点 $p'$。与此同时，它又选择了两个集合之间的函数。确实，在 hom 函子下，态射 $g$ 被映射为函数 $C(a, g)$；在 $F$ 下，它被映射为 $F g$。
现在考虑 $C(a, g)$ 对最初那个 $p$ 的作用；你还记得，$p$ 对应 $id_a$。这个作用被定义为预组合，也就是 $g \circ id_a$，它等于 $g$，也就对应我们的点 $p'$。所以，态射 $g$ 被映射为一个函数，而这个函数作用在 $p$ 上会产生 $p'$，也就是 $g$。我们绕了一圈又回来了！
现在考虑 $F g$ 对 $q$ 的作用。它是某个 $q'$，也就是 $F a$ 中的一个点。为了使自然性方块闭合，$p'$ 必须在 $\alpha_a$ 下被映射到 $q'$。我们任取了 $p'$（任取了 $g$），并推导出了它在 $\alpha_a$ 下的映射。因此，函数 $\alpha_a$ 被完全决定了。
第二个断言是：对 $C$ 中任意与 $a$ 相连的对象 $x$，$\alpha_x$ 也被唯一决定。推理类似，只是现在有另外两个集合 $C(a, x)$ 和 $F x$，并且从 $a$ 到 $x$ 的态射 $g$ 在 hom 函子下被映射为：
C(a, g) :: C(a, a) -> C(a, x)
在 $F$ 下被映射为：
F g :: F a -> F x
同样，$C(a, g)$ 作用在我们的 $p$ 上时，由预组合给出：$g \circ id_a$，它对应 $C(a, x)$ 中的一个点 $p'$。自然性决定了 $\alpha_x$ 作用在 $p'$ 上的值为：
q' = (F g) q
由于 $p'$ 是任意的，整个函数 $\alpha_x$ 也因此被决定。
如果 $C$ 中有些对象与 $a$ 没有连接，会发生什么？它们在 $C(a, -)$ 下全都会被映射到同一个集合，也就是空集。回忆一下，空集是集合范畴中的始对象。这意味着从这个集合到任意其他集合都有唯一函数。我们把这个函数称为 absurd。因此，这里也没有为自然变换分量留下选择：它只能是 absurd。
理解 Yoneda 引理的一种方式是意识到：$Set$ 值函子之间的自然变换不过是函数族，而函数通常是有损的。函数可能折叠信息，也可能只覆盖其陪域的一部分。唯一不有损的函数是可逆函数，也就是同构。因此，最好的保结构 $Set$ 值函子是可表示函子。它们要么是 hom 函子，要么是与 hom 函子自然同构的函子。其他任意函子 $F$ 都是通过有损变换从 hom 函子得到的。这样的变换不仅可能丢失信息，还可能只覆盖函子 $F$ 在 $Set$ 中的像的一小部分。
15.1 Haskell 中的 Yoneda（Yoneda in Haskell）
我们已经在 Haskell 中以 reader 函子的形式遇到过 hom 函子：
type Reader a x = a -> x
type Reader[A, X] = A => X
reader 通过预组合来映射态射（这里也就是函数）：
instance Functor (Reader a) where
fmap f h = f . h
implicit def readerFunctor[A] = new Functor[Reader[A, ?]] {
def fmap[X, B](f: X => B)(h: Reader[A, X]): Reader[A, B] =
f compose h
}
Yoneda 引理告诉我们，reader 函子可以自然地映射到任何其他函子。
自然变换是一个多态函数。所以给定一个函子 F，我们有一个从 reader 函子到它的映射：
alpha :: forall x . (a -> x) -> F x
// 为了构造一个通用变换，需要引入另一个类型。
// 若想进一步了解 FunctionK (~>)：
// typelevel.org/cats/datatypes/functionk.html
trait ~>[F[_], G[_]] {
def apply[B](fa: F[B]): G[B]
}
// Kind Projector 插件提供了更简洁的类型 lambda 语法：
def alpha[A]: (A => ?) ~> F
和往常一样，forall 是可选的，但我喜欢显式写出它，以强调自然变换的参数多态性。
Yoneda 引理告诉我们，这些自然变换与 F a 的元素一一对应：
forall x . (a -> x) -> F x ~= F a
这个等式右边是我们通常会视为数据结构的东西。还记得把函子解释为广义容器吗？F a 是一个 a 的容器。但左边是一个以函数为参数的多态函数。Yoneda 引理告诉我们，这两种表示是等价的，它们包含相同信息。
换一种说法：给我一个如下类型的多态函数：
alpha :: forall x . (a -> x) -> F x
def alpha[A]: (A => ?) ~> F
我就能产生一个 a 的容器。技巧就是我们在 Yoneda 引理证明中用过的那个：用 id 调用这个函数，得到 F a 的一个元素：
alpha id :: F a
alpha(identity): F[A]
反过来也成立：给定一个 F a 类型的值：
fa :: F a
def fa[A]: F[A]
可以定义一个多态函数：
alpha h = fmap h fa
alpha(h) == fmap(h)(fa)
它具有正确的类型。你可以轻松地在两种表示之间来回转换。
拥有多种表示的好处在于：其中一种可能更容易组合，或者在某些应用中更高效。
这个原则最简单的例子，是编译器构造中常用的一种代码变换：延续传递风格（continuation passing style，CPS）。它是 Yoneda 引理应用于恒等函子的最简单情形。把 F 替换成恒等函子，会得到：
forall r . (a -> r) -> r ~= a
这个公式的解释是：任意类型 a 都可以替换为一个接受 a 的“处理器”的函数。处理器是一个接受 a 并执行剩余计算的函数，也就是延续。（类型 r 通常封装某种状态码。）
这种编程风格在 UI、异步系统和并发编程中非常常见。CPS 的缺点是它涉及控制反转。代码被拆分在生产者和消费者（处理器）之间，不容易组合。任何做过一点非平凡 Web 编程的人，都熟悉由交互式有状态处理器带来的意大利面条式代码噩梦。稍后会看到，审慎使用函子和单子，可以恢复 CPS 的某些组合性质。
15.2 Co-Yoneda
和往常一样，反转箭头方向可以得到一个额外构造。Yoneda 引理可以应用到对偶范畴 C^op，从而给出逆变函子之间的映射。
等价地，我们也可以通过固定 hom 函子的目标对象而不是源对象来推导 co-Yoneda 引理。这样得到从 $C$ 到 $Set$ 的逆变 hom 函子：$C(-, a)$。Yoneda 引理的逆变版本建立了从这个函子到任意其他逆变函子 $F$ 的自然变换，与集合 $F a$ 的元素之间的一一对应：
Nat(C(-, a), F) ~= F a
下面是 co-Yoneda 引理的 Haskell 版本：
forall x . (x -> a) -> F x ~= F a
注意，在某些文献中，被称为 Yoneda 引理的正是这个逆变版本。
15.3 挑战（Challenges）
- 说明在 Haskell 中构成 Yoneda 同构的两个函数
phi和psi互为逆。
phi :: (forall x . (a -> x) -> F x) -> F a
phi alpha = alpha id
psi :: F a -> (forall x . (a -> x) -> F x)
psi fa h = fmap h fa
-
离散范畴是这样一种范畴：它有对象，但除了恒等态射之外没有其他态射。对来自这种范畴的函子，Yoneda 引理如何发挥作用？
-
unit 列表
[()]除了长度之外不包含其他信息。因此，作为数据类型，它可以被看作整数的一种编码。空列表编码零，单元素列表[()]（一个值，而不是类型）编码一，依此类推。使用列表函子的 Yoneda 引理，为这个数据类型构造另一种表示。
15.4 参考资料（Bibliography）
- The Catsters, The Yoneda Lemma.