Natural Transformations - 自然变换

Natural Transformations

<译> 自然变换

函子可以在维持范畴结构的前提下实现范畴之间的映射。函子可以将一个范畴嵌入到另一个范畴，它也可以让多个范畴坍缩为一个范畴且不会破坏范畴的结构。将一个范畴嵌入到另一个范畴可能有许多种方式。有时这些方式是等价的，有时它们不等价。可以将整个的范畴坍缩为另一个范畴中的一个对象，也可以将一个范畴中的每个对象映射为另一个范畴中不同的对象，将前者中的每个态射映射为后者中的不同的态射。自然变换可以对比这些实现。自然变换是函子之间的映射——可以保持函子性质不变的特殊映射。

对于范畴 C 与 D 之间的两个函子 F 与 G，如果我们只关注 C 中的一个对象 a，它被映射为 D 中的两个对象：F a 与 G a，那么应该存在一个函子映射，它可以将 F a 映射为 G a。由于在同一范畴中的对象映射应该不会脱离该范畴，而且我们不想人工建立 F a 与 G a 的联系，因此很自然的考虑使用既有的联系——所谓的态射。自然变换本质上是如何选取态射：对于任意对象 α ，自然变换就是选取一个从 F a 到 G a 的态射。如果将一个自然变换称为 α，那么这个态射就被称为在 a 上的 α 分量（Component of α at a），记作 $\alpha_a$ α_a: α_a :: F a -> G a

记住，a 是一个在 C 中的对象，而 α_a 是 D 中的一个态射。 对于某个 a，如果在 F a 与 G a 之间没有态射，那么 F 与 G 之间也就不存在自然变换。

函子所映射的不止是对象，它们也能映射态射，自然变换应该如何对待这种映射？答案是，态射的映射是固定的——在 F 与 G 之间的任何一个自然变换下，F f 必须变换成 G f。也就是说，两个函子对态射所形成的映射会彻底限制与之相适的自然变换的定义。来考虑在范畴 C 中的两个对象 a 与 b 之间的态射 f，它被映射为范畴 D 中的两个态射 F f 与 G f：

1
2

F f :: F a -> F b
G f :: G a -> G b

自然变换 α 提供两个附加的态射来补全 D 中的结构：

1
2

α_a :: F a -> G a
α_b :: F b -> G b

现在，便有了两个从 F a 到 G b 的途径。为了保证这两种途径等价，必须引入自然性条件（Naturality condition）：G f ∘ α_a = α_b ∘ F f 这个条件应该对于任意的 f 都成立。

自然性条件非常有用。例如，如果态射 F f 是可逆的，自然性决定了以 α_a 形式表示的 α_b。通过 f，基于自然性条件可将 α_a 变换为：α_b = (G f) ∘ α_a ∘ (F f)^(-1)

Polymorphic Functions - 多态函数

之前讲过函子（更确切的说，是自函子）在编程中所扮演的角色。它们相当于类型构造子——将类型映射为类型。不过，函子也能将函数映射为函数，这种映射是通过一个高阶函数 fmap（在 C++ 中则是 transform, then 之类的行为）。

为了构造一个自然变换，我们从一个对象开始，也就是一种类型，设为 a。一个函子 F，可以将 a 映射为类型 F a。另一个函子 G，可以将 a 映射为 G a。在 a 上的自然变换 alpha 的分量是一个从 F a 到 G a 的函数。使用用伪 Haskell 代码，可将其表示为：alpha_a :: F a -> G a 通常，可将其写为：alpha :: F a -> G a 这是由 a 参数化的一个函数族。这是 Haskell 语法简洁性的又一个示例。在 C++ 中，与之类似的构造要麻烦一些： template<Class A> G<A> alpha(F<A>);

Haskell 的多态函数与 C++ 的泛型函数之间存在很大的区别，主要体现为函数的实现方式以及类型检查方式上。在 Haskell 中，一个多态函数必须对于所有类型是唯一的。一个公式必须适用于所有的类型。这就是所谓的参数化多态（Parametric polymorphism）。C++ 默认提供的是特设多态（Ad hoc polymorphism），这意味着模板不一定涵盖所有类型。一份模板是否适用于某种给定的类型需要在实例化时方能确定，彼时，编译器会用一种具体的类型来替换模板的类型参数。类型检测是以推导的形式实现的，编译器经常会给出难以理解的错误信息。在 C++ 中，还有一种函数重载与模板特化机制，通过这种机制可以为不同的类型定义函数的不同版本。Haskell 也有类似的机制，即类型类（Type class）与类型族（Type family）。

Haskell 的参数化多态有一个一个不可预料的结果。凡是像这种类型的多态函数：alpha :: F a -> G a 函子 F 与 G 自动满足自然性条件。这里，我们再回到范畴论的概念（f 是一个函数，f::a->b）：G f ∘ α_a = α_b ∘ F f 在 Haskell 中，函子 G 作用于一个态射 f 是通过 fmap 实现的。可使用 Haskell 伪码将上述概念表示为：fmap_G f . alphaa = alphab . fmap_F f 归功于 Haskell 的类型推导，上述类型标记是不需要的，因此可写为以下形式：fmap f . alpha = alpha . fmap f 这依然不是真正的 Haskell 代码——在代码中无法表示函数等式——不过，上式是恒等的，程序员在等式推导中可以使用这个公式，此外，编译器也可以利用这个公式对代码进行优化。

自然性条件之所以在 Haskell 里会自动被满足，这是『免费的定理』的自然结果。在 Haskell 里，参数化多态，将其用于定义自然变换，会引入非常强的限制条件——一个公式适应所有类型。这些限制条件会变成面向这些函数的方程一样的定理。对于能够对函子进行变换的函数，免费的定理是自然性条件。

在 Haskell 里，可以将函子视为泛型容器。我们可以继续这个类比，将自然变换视为一种重组方法，即将一个容器里的东西取出来放到另一个容器里。我们不会触碰这些东西：不修改，也不创造。我们只是将它们（或它们的一部分）复制到新的容器里，在这个过程中有时候会对它们作几次乘法。于是，自然性条件就是，首先它不关心我们是先通过 fmap 修改这些东西，然后再将它们放到新容器里，还是先把它们放到新容器里再用适用于这个容器的 fmap 去修改它们。重组与 fmap，它们是正交的

来看一下 Haskell 里的自然变换。首先来看列表与 Maybe 这两种函子之间的自然变换，它的功能是，当且仅当列表非空时返回列表的首元素：

1
2
3

safeHead :: [a] -> Maybe a
safeHead [] = Nothing
safeHead (x:xs) = Just x

它是面向 a 的函数多态化。它可以不受限制地作用于任意一种类型 a，因此它是一个参数化多态的例子。从而，它就是两个函子之间的一个自然变换。不过，现在这只是我们在自以为是，下面来验证它是否符合自然性条件。fmap f . safeHead = safeHead . fmap f

1
2
3
4
5
6
7

-- 考虑两种情况；一个空列表：
fmap f (safeHead []) = fmap f Nothing = Nothing
safeHead (fmap f []) = safeHead [] = Nothing

-- 和一个非空列表：
fmap f (safeHead (x:xs)) = fmap f (Just x) = Just (f x)
safeHead (fmap f (x:xs)) = safeHead (f x : fmap f xs) = Just (f x)

当函子之一是 Const 函子的时候，会发生一件有趣的事。一个以 Const 函子为始点或终点的自然变换，看上去就像一个函数，它即面向它的返回类型多态，也面向它的参数类型多态。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

-- 可将 length 视为从列表函子到 Const Int 函子的自然变换：
length :: [a] -> Const Int a
length [] = Const 0
length (x:xs) = Const (1 + unConst (length xs))

-- unConst 用于剥除 Const 构造子：
unConst :: Const c a -> c
unConst (Const x) = x

-- 实际上 length 的定义是下面这样：
length :: [a] -> Int

-- 这个定义有效地掩盖了 length 作为自然变换的本质。

寻找一个以 Const 函子为始点的参数化多态函数有点难，因为这需要无中生有创造一个值出来。我们所能想到的最好的办法是：

1
2

scam :: Const Int a -> Maybe a
scam (Const x) = Nothing

还有一个不同寻常的函子，在 Yoneda 引理中扮演了重要的角色。这个函子就是 Reader 函子。下面我用 newtype 来重写一下它的定义：newtype Reader e a = Reader (e -> a) 这个函子被两种类型参数化了，但是它的（协变）函子性仅着落在第二个类型上：instance Functor (Reader e) where fmap f (Reader g) = Reader (\x -> f (g x)) 对于每种类型 e，都可以定义从 Reader e 到任何其他函子的自然变换家族。以后会看到，这个家族的成员总是与 f e 的元素壹壹对应（Yoneda 引理）。

例如，考虑有时会被忽略的仅有一个值 () 的 unit 类型 ()。函子 Reader () 接受任何一种类型 a，将它射入函数类型 () -> a。这些函数可以从集合 a 中拮取一个元素。这些函数的数量与 a 中元素的数量一样多。现在，来看一下从这种函子到 Maybe 函子的自然变换：alpha :: Reader () a -> Maybe a 这样的自然变换只有 dumb：dumb (Reader _) = Nothing 与 obvious：obvious (Reader g) = Just (g ()) （用 g 能做的事情仅仅是让它作用于 ()。）

Beyond Naturality - 超自然性

两个函子之间的参数化多态函数（包括 Const 函子这种边界情况）必定是自然变换。因为所有的标准代数数据类型都是函子，在这些类型之间的任何一个多态函数都是自然变换。我们还掌握了函数类型，它们对于它们的返回类型而言具有着函子性。我们可以使用它们来构造函子（例如 Reader 函子），并为这些函子构造自然变换——更高阶的函数。

不过，对于参数类型而言，函数类型不具备协变性，它们具备逆变性。当然，逆变函子就是相反范畴中的协变函子。在范畴意义上，两个逆变函子之间的多态函数依然可视为自然变换，除了它们只能作用于 Haskell 类型所构成的两个相反的范畴里的函子。

之前我们见过的一个逆变函子的示例：newtype Op r a = Op (a -> r) 这个函子对于 a 而言具有逆变性：instance Contravariant (Op r) where contramap f (Op g) = Op (g . f) 我们可以写一个函数，假设它从 Op Bool 到 Op String：predToStr (Op f) = Op (\x -> if f x then "T" else "F") 由于这两个函子不具备协变性，它并非 Hask 范畴中的自然变换。不过，由于它们都具备逆变性，所以它们满足『相反的』自然性条件：contramap f . predToStr = predToStr . contramap f 注意，函数 f 必须得走与 fmap 的作用下的方向相反的方向，因为 contramap 的签名是：contramap :: (b -> a) -> (Op Bool a -> Op Bool b)

存在不是函子的类型构造子吗，它是协变的还是逆变的？看下面的例子：a -> a 这不是一个函子，因为同一类型的 a 出现在负（逆变）位与正（协变）位上。对于这种类型，fmap 或 contramap 都无法实现。因此，函数签名：(a -> a) -> f a 其中 f 是任意函子，这个函数不是自然变换。

Functor Category - 函子范畴

现在有了函子之间的映射——自然变换——因此很自然地就会想到，函子是否能够形成范畴？可以。对于每对范畴而言，仅存在一个函子范畴。在这个范畴里，对象是从 C 到 D 的函子，而态射就是这些函子之间的自然变换。

必须得定义两个自然变换的复合，这相当容易。自然变换的分量是态射，而我们知道怎样实现态射的复合。

以从函子 F 到函子 G 的自然变换 α 为例。它在对象 a 上的分量是某个态射：α_a :: F a -> G a 打算用对 α 与 β 进行复合，后者是从 G 到 H 的自然变换。β 在 a 上的分量是一个态射：β_a :: G a -> H a 这些态射是可复合的，复合结果又是一个态射：β_a ∘ α_a :: F a -> H a 可以用这个态射作为自然变换 β . α 的分量——自然变换 β 在 a 之后的复合：(β ⋅ α)_a = β_a ∘ α_a 这种复合的结果是从 F 到 H 的自然变换： H f ∘ (β ⋅ α)_a = (β ⋅ α)_b ∘ F f 自然变换的复合遵循结合律，因为它们的分量都是常规态射，而后者的复合是遵循结合律的。最后，对于每个函子 F，存在一个恒等自然变换 1_F，它的分量是恒等态射：id_{F a} :: F a -> F a 所以，函子的确能形成范畴。

2-Categories - 2-范畴

根据定义，Cat 里的任意 Hom-集都是函子集合。但是两个对象之间的函子有着比集合更丰满的结构。它们形成一个范畴，以自然变换为态射。由于在 Cat 里，函子被认为是态射，自然变换就是态射之间的态射。这个更丰满的结构是 2-范畴的一个例子。2 -范畴是一个广义的范畴，其中，除了对象和态射（这里应该叫 1-态射）之外，还有 2-态射，它就是态射之间的态射。Cat 的 2-范畴具有：对象：（小）范畴; 1-态射：范畴之间的函子; 2-态射：函子之间的自然变换

用 Hom-范畴——函子范畴 D^C 来代替范畴 C 与 D 之间的 Hom-集。有常规的函子复合：来自 D^C 的函子 F 与来自 E^D 的函子 G 复合，可以得到来自 E^C 的函子 G ∘ F。但是，在每个 Hom-范畴内部，也存在着复合——函子之间自然变换或 2-态射的竖向复合。

先选在 Cat 里选两个函子，或者 1-态射：F :: C -> D G :: D -> E 与它们的复合：G ∘ F :: C -> E 假设我们有两个自然变换，α 与 β，它们分别作用于函子 F 与 G：α :: F -> F' β :: G -> G' 注意，我们不能对这两个自然变换应用竖向复合，因为 α 的终点与 β 的始点不重合。实际上，它们分别属于两个不同的函子范畴 D^C 与 E^D。不过，我们能够复合函子 F’ 与 G’，因为 F’ 的终点与 G’ 的起点重合——它就是范畴 D。函子 G’∘ F’ 与 G ∘ F 之间有什么关系呢？ 这个自然变换称为 α 与 β 的横向复合：β ∘ α :: G ∘ F -> G'∘ F'

Conclusion

对象与范畴是名词；态射、函子以及自然变换是动词。态射连接了对象，函子连接了范畴，自然变换连接了函子。

已经看到了，一个抽象层上的一个动作，在下一个抽象层次上就变成了一个对象。态射的集合变成了函数对象。作为对象，它可以是另一个态射的始点或终点。这就是高阶函数背后的思想。

函子，将对象映射为对象，因此我们将其作为类型构造子，或者作为一种参数化的类型。函子，也能将态射映射为态射，因此它也是高阶函数——fmap。有一些简单的函子，例如 Const、积以及余积，它们可以产生大量的代数数据类型。函数类型也具有函子性，协变性与逆变性，它们可以用于扩充代数数据类型。

函子在函子范畴里可以视为对象。这样，它们就变成了态射的始点与终点，于是有了自然变换。自然变换就是特定形式的多态函数。