Skip to main content

第 14 章：可表示函子（Representable Functors）

原文：Bartosz Milewski, Category Theory for Programmers, Scala Edition, Chapter 14. 原书 PDF、.tex 源文件及相关图像采用 CC BY-SA 4.0；本译文按同一许可发布。

差不多该稍微谈谈集合了。数学家与集合论之间有一种爱恨交织的关系。它是数学的汇编语言，至少曾经是。范畴论在某种程度上试图离开集合论。例如，一个已知事实是“所有集合的集合”并不存在，但所有集合组成的范畴 $Set$ 存在。所以这很好。另一方面，我们又假设范畴中任意两个对象之间的态射形成一个集合。我们甚至称它为 hom-set。

公平地说，范畴论中有一个分支，其中态射不形成集合。相反，它们是另一个范畴中的对象。那些使用 hom-object 而不是 hom-set 的范畴，称为富范畴。接下来，我们仍会坚持使用带有老式 hom-set 的范畴。

在范畴对象之外，集合是最接近“无特征团块”的东西。集合有元素，但你不能对这些元素说太多。如果有一个有限集合，可以数元素个数。对无限集合，也可以用基数在某种意义上“计数”。例如，自然数集合比实数集合小，尽管二者都是无限的。但也许令人惊讶的是，有理数集合与自然数集合大小相同。

除此之外，关于集合的所有信息都可以编码在它们之间的函数中，尤其是那些可逆函数，也就是同构。出于所有实际目的，同构集合是相同的。在招来基础数学家的怒火之前，让我解释一下：相等与同构之间的区别具有根本重要性。事实上，这是最新数学分支之一，同伦类型论（HoTT）的主要关注点之一。我提到 HoTT，是因为它是一种受到计算启发的纯数学理论，而且它的主要推动者之一 Vladimir Voevodsky 在研究 Coq 定理证明器时获得了重大顿悟。数学与编程之间的互动是双向的。

关于集合的重要教训是：比较由不同类型元素组成的集合是可以的。例如，我们可以说某个自然变换集合与某个态射集合同构，因为集合就是集合。这里的同构只表示：一个集合中的每个自然变换，都与另一个集合中的唯一态射对应，反之亦然。它们可以成对匹配。如果苹果和橙子是不同范畴中的对象，就不能比较苹果和橙子；但可以比较苹果集合和橙子集合。把范畴问题转换成集合论问题，常常能提供必要洞见，甚至让我们证明有价值的定理。

14.1 Hom 函子（The Hom Functor）​

每个范畴都配备了一族到 $Set$ 的规范映射。这些映射实际上是函子，所以它们保持范畴结构。让我们构造其中一个。

固定 $C$ 中一个对象 a，再取 $C$ 中另一个对象 x。hom-set C(a, x) 是一个集合，也就是 $Set$ 中的对象。当改变 x 而保持 a 固定时，C(a, x) 也会在 $Set$ 中变化。因此，我们有一个从 x 到 $Set$ 的映射。

如果想强调我们正在把 hom-set 看作它第二个参数上的映射，可以使用记法 C(a, -)，其中短横线作为参数占位符。

Hom 函子在对象上的映射

这个对象映射很容易扩展为态射映射。取 $C$ 中两个任意对象 x 和 y 之间的态射 f。在刚刚定义的映射下，对象 x 被映射到集合 C(a, x)，对象 y 被映射到 C(a, y)。如果这个映射要成为函子，f 必须被映射为这两个集合之间的函数：

C(a, x) -> C(a, y)

逐点定义这个函数，也就是分别定义它对每个参数的作用。作为参数，应该取 C(a, x) 的任意元素，称为 h。如果态射首尾匹配，它们就可以组合。碰巧，h 的目标与 f 的源匹配，所以它们的组合：

f . h :: a -> y

是从 a 到 y 的态射。因此它是 C(a, y) 的成员。我们刚刚找到了从 C(a, x) 到 C(a, y) 的函数，它可以作为 f 的像。如果没有混淆风险，就把这个提升后的函数写作 C(a, f)，它作用在态射 h 上为：

C(a, f) h = f . h

Hom 函子在态射上的映射

由于这个构造适用于任意范畴，它也必须适用于 Haskell 类型范畴。在 Haskell 中，hom 函子更常被称为 Reader 函子：

type Reader a x = a -> x
type Reader[A, X] = A => X
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
}

现在考虑，如果固定 hom-set 的目标而不是源，会发生什么。换句话说，我们要问映射 C(-, a) 是否也是函子。它是函子，但不是协变的，而是逆变的。这是因为同样的态射首尾匹配，会导致由 f 后组合，而不是像 C(a, -) 中那样预组合。

我们已经在 Haskell 中见过这个逆变函子。当时称它为 Op：

type Op a x = x -> a
type Op[A, X] = X => A
instance Contravariant (Op a) where
    contramap f h = h . f
implicit def opContravariant[A] = new Contravariant[Op[A, ?]] {
  def contramap[X, B](f: B => X)(h: Op[A, X]): Op[A, B] =
    h compose f
}

最后，如果让两个对象都变化，就得到 profunctor C(-, =), 它在第一个参数上逆变，在第二个参数上协变（为了强调两个参数可以独立变化，我们使用双横线作为第二个占位符）。讨论函子性时，我们已经见过这个 profunctor：

instance Profunctor (->) where
    dimap ab cd bc = cd . bc . ab
    lmap = flip (.)
    rmap = (.)
implicit def arrowProfunctor = new Profunctor[Function1] {
  def dimap[A, B, C, D](ab: A => B)(cd: C => D)(bc: B => C): A => D =
    cd compose bc compose ab

  def lmap[A, B, C](f: C => A)(ab: A => B): C => B =
    f andThen ab

  def rmap[A, B, C](f: B => C)(ab: A => B): A => C =
    f compose ab
}

重要教训是，这个观察在任意范畴中都成立：把对象映射到 hom-set 的映射是函子性的。由于逆变等价于来自反范畴的映射，可以简洁地陈述为：

C(-, =) :: C^op x C -> Set

14.2 可表示函子（Representable Functors）​

我们已经看到，对 $C$ 中每个对象 a 的选择，都得到一个从 $C$ 到 $Set$ 的函子。这种到 $Set$ 的保持结构映射通常称为一种表示（representation）。我们把 $C$ 中的对象和态射表示为 $Set$ 中的集合和函数。

函子 C(a, -) 本身有时称为可表示的。更一般地，任意函子 $F$，只要它与某个对象 a 所给出的 hom 函子自然同构，就称为可表示函子。这样的函子必然是 $Set$ 值函子，因为 C(a, -) 就是 $Set$ 值的。

前面说过，我们常常把同构集合看作相同。更一般地，我们把范畴中的同构对象看作相同。这是因为对象除了通过态射与其他对象（以及自身）发生关系之外，没有其他结构。

例如，我们之前讨论过幺半群范畴 $Mon$，它最初用集合建模。但我们谨慎地只把保持这些集合幺半结构的函数选作态射。所以，如果 $Mon$ 中两个对象同构，也就是说它们之间存在可逆态射，那么它们具有完全相同的结构。如果偷看它们所基于的集合和函数，就会看到一个幺半群的单位元被映射到另一个幺半群的单位元，两个元素的积被映射到它们的像的积。

同样的推理也适用于函子。两个范畴之间的函子形成一个范畴，其中自然变换扮演态射。因此，如果两个函子之间存在可逆自然变换，那么它们就是同构的，也可以被视为相同。

从这个角度分析可表示函子的定义。为了让 $F$ 可表示，要求存在 $C$ 中一个对象 a；存在一个从 C(a, -) 到 $F$ 的自然变换 alpha；存在另一个反向自然变换 beta；并且它们的组合是恒等自然变换。

看看 alpha 在某个对象 x 处的分量。它是 $Set$ 中的函数：

alpha_x :: C(a, x) -> F x

这个变换的自然性条件告诉我们，对任意从 x 到 y 的态射 f，下面的图交换：

F f . alpha_x = alpha_y . C(a, f)

在 Haskell 中，会用多态函数替换自然变换：

alpha :: forall x. (a -> x) -> F x
// In order to make a universal transformation,
// another type needs to be introduced.
// To read more about FunctionK (~>):
// typelevel.org/cats/datatypes/functionk.html
trait ~>[F[_], G[_]] {
  def apply[B](fa: F[B]): G[B]
}

// Kind Projector plugin provides
// a more concise syntax for type lambdas:
def alpha[A]: (A => ?) ~> F

其中 forall 量词是可选的。自然性条件：

fmap f . alpha = alpha . fmap f
(fmap(f) _ compose alpha.apply) == (alpha.apply _ compose fmap(f))

由于参数性会自动满足（这就是前面提到的免费定理之一），但要理解左侧的 fmap 由函子 $F$ 定义，而右侧的 fmap 由 reader 函子定义。由于 reader 的 fmap 只是函数预组合，可以更显式一些。作用在 h，也就是 C(a, x) 的元素上时，自然性条件简化为：

fmap f (alpha h) = alpha (f . h)
fmap(f)(alpha(h)) == alpha(f compose h)

另一个变换 beta 方向相反：

beta :: forall x. F x -> (a -> x)
def beta[A]: F ~> (A => ?)

它也必须满足自然性条件，并且必须是 alpha 的逆：

alpha . beta = id = beta . alpha

稍后会看到，从 C(a, -) 到任意 $Set$ 值函子的自然变换总是存在（Yoneda 引理），但它不一定可逆。

给一个 Haskell 例子，使用列表函子并把 Int 作为 a。下面是一个可用的自然变换：

alpha :: forall x. (Int -> x) -> [x]
alpha h = map h [12]
def alpha: (Int => ?) ~> List = new ~>[Int => ?, List] {
  def apply[A](fa: Int => A) =
    List(12).map(fa)
}

我任意选了数字 12，并用它创建了单元素列表。然后可以把函数 h 映射到这个列表上，得到一个返回类型为 h 返回类型的列表。（这样的变换实际上有多少个，取决于整数列表有多少个。）

自然性条件等价于 map（列表版本的 fmap）的可组合性：

map f (map h [12]) = map (f . h) [12]
fmap(f)(fmap(h)(List(12))) == fmap(f compose h)(List(12))
// Or using scala stdlib:
List(12).map(h).map(f) == List(12).map(f compose h)

但如果试图寻找逆变换，就必须从任意类型 x 的列表到返回 x 的函数：

beta :: forall x. [x] -> (Int -> x)
def beta: List ~> (Int => ?)

你可能会想到从列表中取出一个 x，比如用 head，但空列表时这无法工作。注意，这里没有哪个类型 a（替代 Int）能让它可行。所以列表函子不可表示。

还记得我们说过 Haskell 的（自）函子有点像容器吗？同样，可以把可表示函子看作存储函数调用记忆化结果的容器（Haskell 中 hom-set 的成员就是函数）。表示对象，也就是 C(a, -) 中的类型 a，被看作键类型，我们可以用它访问函数的制表值。前面称为 alpha 的变换称为 tabulate，它的逆 beta 称为 index。

下面是一个略微简化的 Representable 类定义：

class Representable f where
    type Rep f :: *
    tabulate :: (Rep f -> x) -> f x
    index    :: f x -> Rep f -> x
trait Representable[F[_]] {
  type Rep
  def tabulate[X](f: Rep => X): F[X]
  def index[X]: F[X] => Rep => X
}

注意，表示类型，也就是我们的 a，这里称为 Rep f，是 Representable 定义的一部分。星号只是表示 Rep f 是一个类型（而不是类型构造器或其他更奇异的 kind）。

无限列表，或者 stream，不可能为空，因此是可表示的。

data Stream x = Cons x (Stream x)
case class Stream[X](
  h: () => X,
  t: () => Stream[X]
)

可以把它们看作接受 Integer 参数的函数的记忆化值。（严格来说，我应该使用非负自然数，但我不想让代码复杂化。）

为了制表这样的函数，需要创建无限值流。当然，这只有在 Haskell 惰性求值时才可能。值按需求值。可以用 index 访问记忆化值：

instance Representable Stream where
    type Rep Stream = Integer
    tabulate f = Cons (f 0) (tabulate (f . (+1)))
    index (Cons b bs) n = if n == 0 then b else index bs (n - 1)
implicit val streamRepresentable = new Representable[Stream] {
  type Rep = Int

  def tabulate[X](f: Rep => X): Stream[X] =
    Stream[X](() => f(0), () => tabulate(f compose (_ + 1)))

  def index[X]: Stream[X] => Rep => X = {
    case Stream(b, bs) =>
      n =>
        if (n == 0) b()
        else index(bs())(n - 1)
  }
}

有趣的是，可以实现一个单一的记忆化方案，覆盖一整族返回类型任意的函数。

逆变函子的可表示性定义类似，只是我们固定 C(-, a) 的第二个参数。或者等价地，可以考虑从 C^op 到 $Set$ 的函子，因为 C^op(a, -) 与 C(-, a) 相同。

可表示性还有一个有趣转折。记住，在笛卡尔闭范畴中，hom-set 可以在内部被看作指数对象。hom-set C(a, x) 等价于 x^a，对可表示函子 $F$ 可以写作：

(-)^a = F

只是开个玩笑，对两边取对数：

a = log F

当然，这只是形式变换，但如果了解一些对数性质，它很有帮助。特别是，事实证明，基于积类型的函子可以用和类型来表示，而和类型函子通常不可表示（例子：列表函子）。

最后注意，可表示函子给了我们同一件事的两种不同实现：一种是函数，一种是数据结构。它们有完全相同的内容，也就是用相同键取回相同值。这就是我前面谈到的“相同”意义。两个自然同构函子就其内容而言是相同的。另一方面，这两种表示通常以不同方式实现，并且可能具有不同性能特征。记忆化被用作性能增强，可能显著降低运行时间。能够为同一底层计算生成不同表示，在实践中非常有价值。所以，令人惊讶的是，尽管范畴论完全不关心性能，却提供了大量探索具有实际价值的替代实现的机会。

14.3 挑战（Challenges）​

  1. 说明 hom 函子把 $C$ 中的恒等态射映射到 $Set$ 中相应的恒等函数。
  2. 说明 Maybe 不可表示。
  3. Reader 函子可表示吗？
  4. 使用 Stream 表示，记忆化一个对参数求平方的函数。
  5. 说明 Stream 的 tabulate 和 index 确实互为逆。（提示：使用归纳法。）
  6. 函子：
Pair a = Pair a a

是可表示的。你能猜出表示它的类型吗？实现 tabulate 和 index。

14.4 参考资料（Bibliography）​

  1. The Catsters, Representable Functors.