第 27 章：Kan 扩张（Kan Extensions）

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

到目前为止，我们大多一直在处理单个范畴，或者一对范畴。在某些情况下，这有点太受限制了。例如，在范畴 C 中定义极限时，我们引入了索引范畴 I，把它作为形成锥底部模式的模板。其实引入另一个平凡范畴来作为锥顶点的模板也很合理。可我们当时使用的是从 I 到 C 的常函子 Delta_c。

现在是时候修正这种别扭之处了。让我们用三个范畴定义极限。首先有一个从索引范畴 I 到 C 的函子 D。这个函子选择锥的底部，也就是图式函子。

新加入的是范畴 1，它只包含一个对象（以及一个恒等态射）。从 I 到这个范畴的函子 K 只有一种可能。它把所有对象映射到 1 中唯一的对象，把所有态射映射到恒等态射。任意从 1 到 C 的函子 F 都会为锥选择一个潜在顶点。

用三个范畴描述极限

锥是从 F . K 到 D 的自然变换 epsilon。注意，F . K 做的事情与原来的 Delta_c 完全相同。下面的图展示了这个变换。

锥作为自然变换

现在可以定义一个泛性质，用来挑选“最好”的这种函子 F。这个 F 会把 1 映射到 D 在 C 中的极限对象，而从 F . K 到 D 的自然变换 epsilon 会给出相应的投影。这个泛函子称为 D 沿 K 的右 Kan 扩张，记作 Ran_K D。

锥的自然变换

来表述这个泛性质。假设有另一个锥，也就是另一个函子 F'，以及一个从 F' . K 到 D 的自然变换 epsilon'。

另一个竞争锥

如果 Kan 扩张 F = Ran_K D 存在，那么必须有唯一自然变换 sigma 从 F' 到它，使得 epsilon' 通过 epsilon 分解，也就是：

epsilon' = epsilon . (sigma . K)

这里，sigma . K 是两个自然变换的水平组合（其中一个是 K 上的恒等自然变换）。随后这个变换再与 epsilon 做垂直组合。

右 Kan 扩张的极限泛性质

按分量看，当作用在 I 中对象 i 上时，得到：

epsilon'_i = epsilon_i . sigma_(K i)

在我们的例子中，sigma 只有一个分量，对应于 1 的唯一对象。所以，这确实就是从由 F' 定义的锥顶点到由 Ran_K D 定义的泛锥顶点的唯一态射。交换条件正是极限定义所要求的条件。

更重要的是，我们可以自由地把平凡范畴 1 替换成任意范畴 A，右 Kan 扩张的定义仍然有效。

27.1 右 Kan 扩张（Right Kan Extension）

函子 D :: I -> C 沿函子 K :: I -> A 的右 Kan 扩张，是一个函子 F :: A -> C（记为 Ran_K D），再配上一个自然变换：

epsilon :: F . K -> D

并且对于任意其他函子 F' :: A -> C 和自然变换：

epsilon' :: F' . K -> D

都存在唯一自然变换：

sigma :: F' -> F

使 epsilon' 分解为：

epsilon' = epsilon . (sigma . K)

这句话很绕，但可以用下面这个漂亮的图来可视化：

右 Kan 扩张的泛性质

一种有趣的看法是，Kan 扩张在某种意义上像“函子乘法”的逆。有些作者甚至把 Ran_K D 记作 D / K。确实，在这种记法下，epsilon 的定义，也就是右 Kan 扩张的余单位，看起来像简单的约消：

epsilon :: D / K . K -> D

Kan 扩张还有另一种解释。设想函子 K 把范畴 I 嵌入 A。在最简单的情况下，I 可以只是 A 的一个子范畴。我们有一个函子 D，它把 I 映射到 C。能否把 D 扩张成一个定义在整个 A 上的函子 F？理想情况下，这样的扩张会让组合 F . K 同构于 D。换句话说，F 会把 D 的定义域扩张到 A。不过，要求完整同构通常太多了，我们可以只取其中一半，也就是从 F . K 到 D 的单向自然变换 epsilon。（左 Kan 扩张选择另一个方向。）

Kan 扩张作为定义域扩张

当然，如果函子 K 在对象上不是单射，或者在 hom-set 上不是忠实的，就像极限的例子那样，嵌入图景就会失效。在这种情况下，Kan 扩张会尽最大努力外推丢失的信息。

27.2 作为伴随的 Kan 扩张（Kan Extension as Adjunction）

现在假设对于任意 D（以及固定的 K），右 Kan 扩张都存在。在这种情况下，Ran_K -（横线替换 D）是一个从函子范畴 [I, C] 到函子范畴 [A, C] 的函子。事实证明，这个函子是预组合函子 - . K 的右伴随。后者会把 [A, C] 中的函子映射到 [I, C] 中的函子。伴随为：

[I, C](F' . K, D) ~= [A, C](F', Ran_K D)

这只是重述了这样一个事实：每个我们称为 epsilon' 的自然变换，都对应唯一一个我们称为 sigma 的自然变换。

Kan 扩张作为预组合的伴随

进一步地，如果选择范畴 I 与 C 相同，就可以把恒等函子 I_C 代入 D。得到下面的恒等式：

[C, C](F' . K, I_C) ~= [A, C](F', Ran_K I_C)

现在选择 F' 等于 Ran_K I_C。在这种情况下，右侧包含恒等自然变换；与之对应，左侧给出下面的自然变换：

epsilon :: Ran_K I_C . K -> I_C

这看起来很像一个伴随的余单位：

Ran_K I_C -| K

确实，恒等函子沿函子 K 的右 Kan 扩张，可以用来计算 K 的左伴随。为此，还需要一个条件：右 Kan 扩张必须被函子 K 保持。保持扩张的意思是，如果计算预组合了 K 的函子的 Kan 扩张，结果应该等同于把原来的 Kan 扩张再预组合 K。在我们的例子中，这个条件化简为：

K . Ran_K I_C ~= Ran_K K

注意，使用“除以 K”的记法时，这个伴随可以写成：

I / K -| K

这确认了我们的直觉：伴随描述了某种逆。保持条件变成：

K . I / K ~= K / K

一个函子沿自身的右 Kan 扩张 K / K 称为 codensity monad。

伴随公式是一个重要结果，因为正如马上会看到的，我们可以用端（余端）计算 Kan 扩张，从而得到寻找右（以及左）伴随的实用手段。

27.3 左 Kan 扩张（Left Kan Extension）

对偶构造会给出左 Kan 扩张。为了建立直觉，可以从余极限的定义开始，并把它重构为使用单点范畴 1。我们用函子 D :: I -> C 形成它的底部，并用函子 F :: 1 -> C 选择它的顶点，由此构造余锥。

用三个范畴描述余极限

余锥的边，也就是注入，是从 D 到 F . K 的自然变换 eta 的分量。

余锥作为自然变换

余极限是泛余锥。因此，对于任意其他函子 F' 和自然变换：

eta' :: D -> F' . K

都存在从 F 到 F' 的唯一自然变换 sigma。

另一个竞争余锥

并且满足：

eta' = (sigma . K) . eta

这由下面的图说明：

左 Kan 扩张的余极限泛性质

把单点范畴 1 替换成 A 后，这个定义会自然推广为左 Kan 扩张的定义，记为 Lan_K D。自然变换：

eta :: D -> Lan_K D . K

称为左 Kan 扩张的单位。

左 Kan 扩张的泛性质

和之前一样，可以把自然变换之间的一一对应：

eta' = (sigma . K) . eta

改写为伴随：

[A, C](Lan_K D, F') ~= [I, C](D, F' . K)

换句话说，左 Kan 扩张是预组合 K 的左伴随，右 Kan 扩张是它的右伴随。

左 Kan 扩张泛性质的推广

正如恒等函子的右 Kan 扩张可以用来计算 K 的左伴随，恒等函子的左 Kan 扩张则是 K 的右伴随（其中 eta 是伴随的单位）：

K -| Lan_K I_C

把两个结果合在一起，得到：

Ran_K I_C -| K -| Lan_K I_C

27.4 作为端的 Kan 扩张（Kan Extensions as Ends）

Kan 扩张真正的力量来自这样一个事实：它们可以用端（和余端）计算。为简单起见，我们把注意力限制在目标范畴 C 是 Set 的情况，但这些公式可以推广到任意范畴。

让我们重新审视 Kan 扩张可以把函子的作用扩展到原定义域之外这个想法。假设 K 把 I 嵌入 A。函子 D 把 I 映射到 Set。我们可以说，对于 K 的像中的任意对象 a，也就是 a = K i，扩张后的函子把 a 映射到 D i。问题在于，对 A 中那些不在 K 的像里的对象该怎么办？想法是，每个这样的对象都可能通过许多态射连接到 K 的像中的每个对象。函子必须保持这些态射。从对象 a 到 K 的像的全部态射由 hom-函子刻画：

A(a, K -)

注意，这个 hom-函子是两个函子的组合：

A(a, K -) = A(a, -) . K

右 Kan 扩张是函子组合的右伴随：

[I, Set](F' . K, D) ~= [A, Set](F', Ran_K D)

看看把 F' 替换成 hom-函子后会发生什么：

[I, Set](A(a, -) . K, D) ~= [A, Set](A(a, -), Ran_K D)

再把组合内联：

[I, Set](A(a, K -), D) ~= [A, Set](A(a, -), Ran_K D)

右侧可以用 Yoneda 引理化简：

[I, Set](A(a, K -), D) ~= Ran_K D a

现在可以把自然变换集合重写为端，得到右 Kan 扩张非常方便的公式：

Ran_K D a ~= ∫_i Set(A(a, K i), D i)

右 Kan 扩张的端公式

左 Kan 扩张也有一个类似公式，用余端表示：

Lan_K D a = ∫^i A(K i, a) x D i

为了说明确实如此，我们将证明它确实是函子组合的左伴随：

[A, Set](Lan_K D, F') ~= [I, Set](D, F' . K)

把公式代入左侧：

[A, Set](∫^i A(K i, -) x D i, F')

这是一个自然变换集合，因此可以重写为端：

∫_a Set(∫^i A(K i, a) x D i, F' a)

利用 hom-函子的连续性，可以把余端替换成端：

∫_a ∫_i Set(A(K i, a) x D i, F' a)

可以使用积-指数伴随：

∫_a ∫_i Set(A(K i, a), (F' a)^(D i))

指数同构于对应的 hom-set：

∫_a ∫_i Set(A(K i, a), A(D i, F' a))

有一个称为 Fubini 定理的定理，允许我们交换两个端：

∫_i ∫_a Set(A(K i, a), A(D i, F' a))

内层端表示两个函子之间的自然变换集合，因此可以使用 Yoneda 引理：

∫_i A(D i, F'(K i))

这确实就是我们要证明的伴随右侧所形成的自然变换集合：

[I, Set](D, F' . K)

这些使用端、余端和 Yoneda 引理的计算，是端的“微积分”中相当典型的计算。

27.5 Haskell 中的 Kan 扩张（Kan Extensions in Haskell）

Kan 扩张的端/余端公式可以很容易翻译到 Haskell。先看右扩张：

Ran_K D a ~= ∫_i Set(A(a, K i), D i)

把端替换成全称量词，把 hom-set 替换成函数类型：

newtype Ran k d a = Ran (forall i. (a -> k i) -> d i)

// Another type needs to be introduced.
// To read more about FunctionK (~>):
// typelevel.org/cats/datatypes/functionk.html
trait ~>[F[_], G[_]] {
  def apply[C](fa: F[C]): G[C]
}

trait Ran[K[_], D[_], A] {
  // partially-applied type
  type AtoK[I] = A => K[I]
  def apply: AtoK ~> D
}

看这个定义很清楚：Ran 必须包含一个类型为 a 的值，以便函数可以应用到它上面；还包含两个函子 k 与 d 之间的自然变换。例如，假设 k 是树函子，d 是列表函子，并且给了你一个 Ran Tree [] String。如果你传入一个函数：

f :: String -> Tree Int

def f: String => Tree[Int]

就会得到一个 Int 列表，依此类推。右 Kan 扩张会用你的函数产生一棵树，然后把它重新包装成列表。例如，你可以传入一个解析器，它从字符串生成解析树，然后会得到一个与这棵树的深度优先遍历对应的列表。

右 Kan 扩张可以通过把函子 d 替换成恒等函子，来计算给定函子的左伴随。这会让函子 k 的左伴随表示为下面这种类型的多态函数集合：

forall i. (a -> k i) -> i

type Id[I] = I

trait PolyFunc[A, K[_]] {
  type AtoK[I] = A => K[I]
  def apply(): AtoK ~> Id
}

假设 k 是来自幺半群范畴的遗忘函子。于是，全称量词会遍历所有幺半群。当然，在 Haskell 中我们无法表达幺半群律，但下面是所得自由函子的一个不错近似（遗忘函子 k 在对象上是恒等的）：

type Lst a = forall i. Monoid i => (a -> i) -> i

trait `PolyFunctionM`[F[_], G[_]] {
  def apply[I: Monoid](fa: F[I]): G[I]
}

trait Lst[A] {
  type aTo[X] = A => X
  def apply(): aTo `PolyFunctionM` Id
}

如预期，它生成自由幺半群，也就是 Haskell 列表：

toLst :: [a] -> Lst a
toLst as = \f -> foldMap f as

fromLst :: Lst a -> [a]
fromLst f = f (\a -> [a])

// Read more about foldMap:
// typelevel.org/cats/typeclasses/foldable.html
def foldMap[F[_], A, B](fa: F[A])(f: A => B)
  (implicit B: Monoid[B]): B = ???

implicit def listMonoid[A]: Monoid[List[A]] = ???

def toLst[A]: List[A] => Lst[A] = as => new Lst[A] {
  def apply(): `PolyFunctionM`[aTo, Id] =
    new `PolyFunctionM`[aTo, Id] {
      def apply[I: Monoid](fa: aTo[I]): Id[I] =
        foldMap(as)(fa)
    }
}

def fromLst[A]: Lst[A] => List[A] =
  f => f().apply(a => List(a))

左 Kan 扩张是一个余端：

Lan_K D a = ∫^i A(K i, a) x D i

所以它会翻译成存在量词。符号化写作：

Lan k d a = exists i. (k i -> a, d i)

这可以在 Haskell 中用 GADT 编码，或者用全称量化的数据构造器编码：

data Lan k d a = forall i. Lan (k i -> a) (d i)

trait Lan[K[_], +D[_], A] {
  def fk[I](ki: K[I]): A
  def di[I]: D[I]
}

这个数据结构的解释是：它包含一个函数，接收由某个未知 i 组成的容器并产生一个 a。它也有一个装着那些 i 的容器。由于你不知道这些 i 是什么，唯一能用这个数据结构做的，就是取出 i 的容器，用自然变换把它重新包装进函子 k 定义的容器，然后调用函数来得到 a。例如，如果 d 是树，k 是列表，你可以序列化这棵树，用得到的列表调用函数，从而获得一个 a。

左 Kan 扩张可以用来计算函子的右伴随。我们知道 product 函子的右伴随是指数对象，所以试着用 Kan 扩张实现它：

type Exp a b = Lan ((,) a) I b

type Exp[A, B] = Lan[(A, ?), I, B]

下面这对函数见证了它确实同构于函数类型：

toExp :: (a -> b) -> Exp a b
toExp f = Lan (f . fst) (I ())

fromExp :: Exp a b -> (a -> b)
fromExp (Lan f (I x)) = \a -> f (a, x)

def fst[I]: ((I, _)) => I = _._1

def toExp[A, B]: (A => B) => Exp[A, B] = f => new Lan[(A, ?), I, B] {
  def fk[L](ki: (A, L)): B =
    f.compose(fst[A])(ki)

  def di[L]: I[L] = I()
}

def fromExp[A, B]: Exp[A, B] => (A => B) =
  lan => a => lan.fk((a, lan.di))

注意，正如前面一般情况中描述的，我们执行了以下步骤：

取出 x 的容器（这里它只是一个平凡的 identity 容器）以及函数 f。
使用恒等函子与 pair 函子之间的自然变换重新包装容器。
调用函数 f。

27.6 自由函子（Free Functor）

Kan 扩张的一个有趣应用，是构造自由函子。它解决了下面这个实际问题：假设你有一个类型构造器，也就是一个对象映射。是否可以基于这个类型构造器定义一个函子？换句话说，能否定义一个态射映射，把这个类型构造器扩展成一个完整的自函子？

关键观察是：类型构造器可以描述为一个定义域为离散范畴的函子。离散范畴除了恒等态射以外没有其他态射。给定一个范畴 C，总可以通过直接丢弃所有非恒等态射来构造一个离散范畴 |C|。从 |C| 到 C 的函子 F 于是只是一个简单的对象映射，也就是 Haskell 中所谓的类型构造器。还存在一个典范函子 J，把 |C| 注入 C：它在对象上（以及恒等态射上）是恒等的。F 沿 J 的左 Kan 扩张如果存在，就是一个从 C 到 C 的函子：

Lan_J F a = ∫^i C(J i, a) x F i

它称为基于 F 的自由函子。

在 Haskell 中会写成：

data FreeF f a = forall i. FMap (i -> a) (f i)

trait FreeF[F[_], A] {
  def h[I]: I => A
  def fi[I]: F[I]
}

确实，对于任意类型构造器 f，FreeF f 都是函子：

instance Functor (FreeF f) where
    fmap g (FMap h fi) = FMap (g . h) fi

implicit def freeFunctor[F[_]] = new Functor[FreeF[F, ?]] {
  def fmap[A, B](g: A => B)(fa: FreeF[F, A]): FreeF[F, B] = {
    new FreeF[F, B] {
      def h[I]: I => B = g compose fa.h
      def fi[I]: F[I] = fi
    }
  }
}

如你所见，自由函子通过同时记录函数和它的参数，来伪造函数提升。它通过记录组合来累积被提升的函数。函子律会自动满足。这个构造曾用于论文 Freer Monads, More Extensible Effects¹。

或者，也可以用右 Kan 扩张达成同样目的：

newtype FreeF f a = FreeF (forall i. (a -> i) -> f i)

case class FreeF[F[_], A](r: (A => ?) ~> F)

很容易检查这确实是一个函子：

instance Functor (FreeF f) where
    fmap g (FreeF r) = FreeF (\bi -> r (bi . g))

implicit def freeFunctor[F[_]] = new Functor[FreeF[F, ?]] {
  def fmap[A, B](g: A => B)(fa: FreeF[F, A]): FreeF[F, B] = fa match {
    case FreeF(r) => FreeF {
      new ~>[B => ?, F] {
        def apply[C](bi: B => C): F[C] =
          r(bi compose g)
      }
    }
  }
}

Oleg Kiselyov, Hiromi Ishii, Freer Monads, More Extensible Effects. ↩

27.1 右 Kan 扩张（Right Kan Extension）​

27.2 作为伴随的 Kan 扩张（Kan Extension as Adjunction）​

27.3 左 Kan 扩张（Left Kan Extension）​

27.4 作为端的 Kan 扩张（Kan Extensions as Ends）​

27.5 Haskell 中的 Kan 扩张（Kan Extensions in Haskell）​

27.6 自由函子（Free Functor）​

Footnotes​