第 16 章：Yoneda 嵌入（Yoneda Embedding）
原文：Bartosz Milewski, Category Theory for Programmers, Scala Edition, Chapter 16. 原书 PDF、
.tex源文件及相关图像采用 CC BY-SA 4.0；本译文按同一许可发布。
我们之前已经看到，当在范畴 $C$ 中固定一个对象 $a$ 时，映射 $C(a, -)$ 是一个从 $C$ 到 $Set$ 的（协变）函子。
x -> C(a, x)
（陪域是 $Set$，因为 hom-set $C(a, x)$ 是一个集合。）我们称这个映射为 hom 函子；之前也已经定义过它在态射上的作用。
现在让 $a$ 在这个映射中变化。我们得到一个新映射，它把 hom 函子 $C(a, -)$ 分配给任意 $a$。
a -> C(a, -)
这是一个从范畴 $C$ 到函子的对象映射，而函子是函子范畴中的对象（参见“自然变换”一章中关于函子范畴的部分）。用记法 $[C, Set]$ 表示从 $C$ 到 $Set$ 的函子范畴。你可能也记得，hom 函子是原型性的可表示函子。
每当我们有两个范畴之间的对象映射时，很自然会问这样的映射是否也是函子。换句话说，我们是否可以把一个范畴中的态射提升为另一个范畴中的态射。$C$ 中的态射只是 $C(a, b)$ 的元素，但函子范畴 $[C, Set]$ 中的态射是自然变换。所以我们要寻找一个把态射映射到自然变换的映射。
让我们看看能否找到与态射 $f : a \to b$ 对应的自然变换。首先看看 $a$ 和 $b$ 被映射到什么。它们被映射到两个函子：$C(a, -)$ 和 $C(b, -)$。我们需要的是这两个函子之间的自然变换。
这里有一个技巧：使用 Yoneda 引理：
[C, Set](C(a, -), F) ~= F a
并把泛化的 $F$ 替换为 hom 函子 $C(b, -)$。我们得到：
[C, Set](C(a, -), C(b, -)) ~= C(b, a)
这正是我们要找的两个 hom 函子之间的自然变换，不过带有一点转折：自然变换与态射之间的映射对应的是 $C(b, a)$ 的一个元素，也就是方向“反了”。但这没关系；它只表示我们正在看的这个函子是逆变的。
实际上，我们得到的甚至比预想更多。从 $C$ 到 $[C, Set]$ 的这个映射不仅是一个逆变函子，而且是一个全忠实函子。全性与忠实性是函子的性质，用来描述函子如何映射 hom-set。
忠实函子在 hom-set 上是单射，这意味着它把不同态射映射为不同态射。换句话说，它不会把它们合并。
满函子在 hom-set 上是满射，这意味着它把一个 hom-set 映射到另一个 hom-set 上，并完全覆盖后者。
全忠实函子 $F$ 在 hom-set 上是双射，也就是两个集合所有元素之间的一一匹配。对于源范畴 $C$ 中每对对象 $a$ 与 $b$，$C(a, b)$ 和 $D(Fa, Fb)$ 之间存在一个双射，其中 $D$ 是 $F$ 的目标范畴（在我们的情形中，是函子范畴 $[C, Set]$）。注意，这并不意味着 $F$ 在对象上是双射。$D$ 中可能有些对象不在 $F$ 的像中，而我们无法对那些对象的 hom-set 作出什么断言。
16.1 嵌入（The Embedding）
我们刚刚描述的（逆变）函子，也就是把 $C$ 中对象映射为 $[C, Set]$ 中函子的那个函子：
a -> C(a, -)
定义了 Yoneda 嵌入。它把范畴 $C$（严格说来，因为逆变性，是范畴 C^op）嵌入到函子范畴 $[C, Set]$ 中。它不仅把 $C$ 中对象映射为函子，还忠实地保留了它们之间的所有连接。
这是一个非常有用的结果，因为数学家对函子范畴知道很多，尤其是那些陪域为 $Set$ 的函子。通过把任意范畴 $C$ 嵌入函子范畴，我们可以获得很多关于 $C$ 的洞见。
当然，Yoneda 嵌入有一个对偶版本，有时称为 co-Yoneda 嵌入。注意，我们本来也可以固定每个 hom-set 的目标对象（而不是源对象）$C(-, a)$。那会给出一个逆变 hom 函子。从 $C$ 到 $Set$ 的逆变函子就是我们熟悉的预层（presheaf）（例如见“极限与余极限”一章）。co-Yoneda 嵌入定义了范畴 $C$ 到预层范畴中的嵌入。它在态射上的作用由下式给出：
[C, Set](C(-, a), C(-, b)) ~= C(a, b)
同样，数学家对预层范畴知道很多，因此能够把任意范畴嵌入其中，是一个巨大收获。
16.2 在 Haskell 中的应用（Application to Haskell）
在 Haskell 中，Yoneda 嵌入可以表示为：一边是 reader 函子之间的自然变换，另一边是函数（方向相反），二者之间存在同构：
forall x. (a -> x) -> (b -> x) ~= b -> a
（记住，reader 函子等价于 ((->) a)。）
这个等式左边是一个多态函数；给定一个从 a 到 x 的函数，以及一个类型为 b 的值，它可以产生一个类型为 x 的值（我在这里对 b -> x 这个函数做了反柯里化，也就是省略外层括号）。要对所有 x 都做到这一点，唯一办法是我们的函数知道如何把一个 b 转换成一个 a。它必须秘密访问到某个函数 b -> a。
给定这样一个转换器 btoa，可以定义左边，称为 fromY：
fromY :: (a -> x) -> b -> x
fromY f b = f (btoa b)
// 为了构造一个通用变换，需要引入另一个类型。
// 若想进一步了解 FunctionK (~>)：
// typelevel.org/cats/datatypes/functionk.html
trait ~>[F[_], G[_]] {
def apply[X](fa: F[X]): G[X]
}
def fromY[A, B]: (A => ?) ~> (B => ?) = new ~>[A => ?, B => ?] {
def apply[X](f: A => X): B => X =
b => f(btoa(b))
}
反过来，给定一个函数 fromY，可以用恒等函数调用 fromY 来恢复转换器：
fromY id :: b -> a
fromY(identity): B => A
这就建立了 fromY 类型的函数与 btoa 之间的双射。
另一种看待这个同构的方式是：它是从 b 到 a 的函数的一种 CPS 编码。参数 a -> x 是一个延续（处理器）。结果是一个从 b 到 x 的函数；当用一个类型为 b 的值调用它时，它会执行被编码函数预组合后的延续。
Yoneda 嵌入还解释了 Haskell 中一些数据结构的替代表示。特别是，它为 Control.Lens 库中的 lens 提供了一种非常有用的表示1.
16.3 预序例子（Preorder Example）
这个例子由 Robert Harper 提出。它是 Yoneda 嵌入应用于由预序定义的范畴。预序是一个集合，其元素之间带有一个传统上写作 $\leq$（小于等于）的序关系。之所以叫“预”序，是因为我们只要求这个关系满足传递性和自反性，而不一定满足反对称性（所以可能存在环）。
带预序关系的集合会产生一个范畴。对象是这个集合的元素。从对象 $a$ 到 $b$ 的态射要么不存在，也就是两个对象无法比较，或者 $a \leq b$ 不成立；要么在 $a \leq b$ 时存在，并且从 $a$ 指向 $b$。从一个对象到另一个对象永远不会有多个态射。因此，这种范畴中的任意 hom-set 要么是空集，要么是单元素集合。这样的范畴称为薄范畴（thin category）。
很容易说服自己这个构造确实是一个范畴：箭头可以组合，因为如果 $a \leq b$ 且 $b \leq c$，那么 $a \leq c$；并且组合满足结合律。我们也有恒等箭头，因为每个元素都（小于或）等于自身（底层关系的自反性）。
现在可以把 co-Yoneda 嵌入应用到预序范畴。特别地，我们关心它在态射上的作用：
[C, Set](C(-, a), C(-, b)) ~= C(a, b)
右边的 hom-set 非空，当且仅当 $a \leq b$；在这种情况下，它是一个单元素集合。因此，如果 $a \leq b$，左边就存在一个唯一的自然变换。否则，不存在自然变换。
那么，在预序中，hom 函子之间的自然变换是什么？它应该是集合 $C(-, a)$ 与 $C(-, b)$ 之间的一族函数。在预序中，这些集合每一个都可能是空集，也可能是单元素集合。看看我们可以使用哪些函数。
有一个从空集到自身的函数（作用在空集上的恒等函数），有一个从空集到单元素集合的 absurd 函数（它什么也不做，因为它只需要为一个空集的元素定义，而空集中没有元素），还有一个从单元素集合到自身的函数（作用在单元素集合上的恒等函数）。唯一禁止的组合，是从单元素集合到空集的映射（这样的函数作用在唯一元素上时，该返回什么值？）。
所以我们的自然变换永远不会把单元素 hom-set 连接到空 hom-set。换句话说，如果 $x \leq a$（单元素 hom-set $C(x, a)$），那么 $C(x, b)$ 就不能是空的。非空的 $C(x, b)$ 意味着 $x$ 小于等于 $b$。因此，所讨论自然变换的存在要求：对每个 $x$，如果 $x \leq a$，那么 $x \leq b$。
for all x, x <= a => x <= b
另一方面，co-Yoneda 告诉我们，这个自然变换的存在等价于 $C(a, b)$ 非空，也等价于 $a \leq b$。合在一起，我们得到：
a <= b if and only if for all x, x <= a => x <= b
我们本来也可以直接得到这个结果。直觉是：如果 $a \leq b$，那么所有位于 $a$ 之下的元素也都必须位于 $b$ 之下。反过来，如果在右边把 $a$ 代入 $x$，就能推出 $a \leq b$。不过你必须承认，通过 Yoneda 嵌入抵达这个结果要有趣得多。
16.4 自然性（Naturality）
Yoneda 引理建立了自然变换集合与 $Set$ 中一个对象之间的同构。自然变换是函子范畴 $[C, Set]$ 中的态射。任意两个函子之间的自然变换集合，是该范畴中的一个 hom-set。Yoneda 引理就是这个同构：
[C, Set](C(a, -), F) ~= F a
事实证明，这个同构在 $F$ 和 $a$ 两者上都是自然的。换句话说，它在 $(F, a)$ 上自然，而这个二元组来自积范畴 $[C, Set] \times C$。注意，我们现在把 $F$ 当作函子范畴中的一个对象。
稍微想一想这意味着什么。自然同构是两个函子之间的可逆自然变换。确实，我们同构右边是一个函子。它是从 $[C, Set] \times C$ 到 $Set$ 的函子。它对一对 $(F, a)$ 的作用是一个集合，也就是把函子 $F$ 在对象 $a$ 处求值的结果。这个函子称为求值函子（evaluation functor）。
左边也是一个函子，它把 $(F, a)$ 映射为自然变换集合 $[C, Set](C(a, -), F)$。
要说明它们真的是函子，我们还应该定义它们在态射上的作用。但 $(F, a)$ 与 $(G, b)$ 之间的态射是什么？它是一对态射 $(\Phi, f)$；第一个是函子之间的态射，也就是自然变换；第二个是 $C$ 中的普通态射。
求值函子接受这一对 $(\Phi, f)$，并把它映射为两个集合 $F a$ 与 $G b$ 之间的函数。可以很容易地用 $\Phi$ 在 $a$ 处的分量（它把 $F a$ 映射到 $G a$）以及由 $G$ 提升的态射 $f$ 构造这样的函数：
(G f) . Phi_a
注意，由于 $\Phi$ 的自然性，这与下面的式子相同：
Phi_b . (F f)
我不会证明整个同构的自然性；一旦你已经明确这些函子是什么，证明就相当机械。它来自这样一个事实：我们的同构由函子和自然变换构成。它根本没有出错的空间。
16.5 挑战（Challenges）
- 用 Haskell 表达 co-Yoneda 嵌入。
- 说明我们在
fromY和btoa之间建立的双射是一个同构（两个映射互为逆）。 - 为一个幺半群写出 Yoneda 嵌入。哪个函子对应于幺半群的单个对象？哪些自然变换对应于幺半群态射？
- 协变 Yoneda 嵌入应用到预序上会得到什么？（问题由 Gershom Bazerman 提出。）
- Yoneda 嵌入可以用来把任意函子范畴 $[C, D]$ 嵌入到函子范畴 $[[C, D], Set]$ 中。弄清楚它在态射上如何工作（在这种情况下，态射是自然变换）。