第 23 章：余单子（Comonads）

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

既然已经讲过单子，我们就可以收获对偶性的好处：只要反转箭头并在相反范畴中工作，就能免费得到余单子。

回想一下，在最基本的层面上，单子关乎 Kleisli 箭头的组合：

a -> m b

A => M[B]

其中 m 是一个作为单子的函子。如果用字母 w（倒过来的 m）表示余单子，就可以把余 Kleisli 箭头定义为下面这种类型的态射：

w a -> b

W[A] => B

余 Kleisli 箭头的 fish 操作符类似物定义为：

(=>=) :: (w a -> b) -> (w b -> c) -> (w a -> c)

def =>=[A, B, C](w1: W[A] => B)(w2: W[B] => C): W[A] => C

为了让余 Kleisli 箭头形成范畴，还必须有一个恒等余 Kleisli 箭头，它称为 extract：

extract :: w a -> a

def extract[A](wa: W[A]): A

这是 return 的对偶。我们还必须施加结合律以及左、右恒等律。把这些放在一起，就可以在 Haskell 中这样定义余单子：

class Functor w => Comonad w where
    (=>=)  :: (w a -> b) -> (w b -> c) -> (w a -> c)
    extract :: w a -> a

trait Comonad[W[_]] extends Functor[W] {
  def =>=[A, B, C](w1: W[A] => B)(w2: W[B] => C): W[A] => C
  def extract[A](wa: W[A]): A
}

实践中，我们会使用稍微不同的原语，马上就会看到。

问题是：余单子在编程中有什么用？

23.1 使用余单子编程（Programming with Comonads）

让我们比较单子和余单子。单子提供一种使用 return 把值放进容器的方式。它不会让你访问容器内部的某个值或多个值。当然，实现单子的数据结构也许会提供访问其内容的接口，但那只能算额外赠品。并不存在一个从单子中提取值的通用接口。我们也见过 IO 单子的例子，它引以为傲的一点正是永远不暴露自己的内容。

另一方面，余单子提供从中提取单个值的手段。它不提供插入值的手段。因此，如果你想把余单子理解为容器，它总是预先填满了内容，并允许你向里面窥视。

正如 Kleisli 箭头接收一个值并产生某种被修饰的结果，也就是给结果加上上下文；余 Kleisli 箭头接收一个值连同完整上下文，并产生结果。它体现的是上下文中的计算。

23.2 Product 余单子（The Product Comonad）

还记得 reader 单子吗？我们引入它，是为了解决那些需要访问某个只读环境 e 的计算。这类计算可以表示为下面形式的纯函数：

(a, e) -> b

((A, E)) => B

我们使用柯里化把它们转换为 Kleisli 箭头：

a -> (e -> b)

A => (E => B)

但请注意，这些函数已经具有余 Kleisli 箭头的形式。让我们把它们的参数调整成更方便的函子形式：

data Product e a = Prod e a deriving Functor

case class Product[E, A](run: (E, A))
// implicit def productFunctor = ...

我们可以很容易定义组合操作符：让正在组合的两个箭头都能访问同一个环境：

(=>=) :: (Product e a -> b) -> (Product e b -> c) -> (Product e a -> c)
f =>= g = \(Prod e a) -> let b = f (Prod e a)
                             c = g (Prod e b)
                         in c

def =>=[E, A, B, C]: (Product[E, A] => B) => (Product[E, B] => C) =>
  (Product[E, A] => C) = f => g => {
    case Product((e, a)) =>
      val b = f(Product((e, a)))
      val c = g(Product((e, b)))
      c
  }

extract 的实现只是忽略环境：

extract (Prod e a) = a

def extract[E, A]: Product[E, A] => A = {
  case Product((e, a)) => a
}

不出所料，product 余单子可以执行和 reader 单子完全相同的计算。在某种意义上，环境的余单子实现更自然，因为它遵循“上下文中的计算”这种精神。另一方面，单子有 do 记法这种方便的语法糖。

reader 单子与 product 余单子之间有更深的联系，这与 reader 函子是 product 函子的右伴随有关。不过，一般而言，余单子覆盖的是与单子不同的计算观念。稍后我们会看到更多例子。

把 Product 余单子推广到任意 product 类型也很容易，包括元组和记录。

23.3 剖析组合（Dissecting the Composition）

继续对偶化过程，我们可以直接对单子的 bind 和 join 做对偶化。或者，我们也可以重复之前研究 fish 操作符结构时所用的过程。这种方式看起来更有启发性。

起点是意识到：组合操作符必须产生一个余 Kleisli 箭头，它接收 w a 并产生 c。产生 c 的唯一方式，是把第二个函数应用到某个类型为 w b 的参数上：

(=>=) :: (w a -> b) -> (w b -> c) -> (w a -> c)
f =>= g = g ...

def =>=[W[_], A, B, C]: (W[A] => B) => (W[B] => C) => (W[A] => C) =
  f => g => g ...

但怎样才能产生一个可以喂给 g 的 w b 类型的值呢？我们手头有类型为 w a 的参数，还有函数 f :: w a -> b。解决办法是定义 bind 的对偶，它称为 extend：

extend :: (w a -> b) -> w a -> w b

def extend[W[_], A, B]: (W[A] => B) => W[A] => W[B]

利用 extend，我们可以实现组合：

f =>= g = g . extend f

def =>=[W[_], A, B, C]: (W[A] => B) => (W[B] => C) => (W[A] => C) =
  f => g => g compose extend(f)

接下来能不能剖析 extend？你也许会想，为什么不直接把函数 w a -> b 应用于参数 w a 呢？但你很快就会意识到，这样得到的是 b，却没有办法把它转换成 w b。记住，余单子不提供提升值的手段。

在这里，单子那边的类似构造会使用 fmap。而我们在这里使用 fmap 的唯一方式，是手头有某个类型为 w (w a) 的东西。如果我们能够把 w a 转换成 w (w a) 就好了。方便的是，这正是 join 的对偶。我们称之为 duplicate：

duplicate :: w a -> w (w a)

def duplicate[W[_], A]: W[A] => W[W[A]]

因此，就像单子的定义一样，余单子也有三种等价定义：使用余 Kleisli 箭头、使用 extend，或者使用 duplicate。下面是直接取自 Control.Comonad 库的 Haskell 定义：

class Functor w => Comonad w where
    extract :: w a -> a

    duplicate :: w a -> w (w a)
    duplicate = extend id

    extend :: (w a -> b) -> w a -> w b
    extend f = fmap f . duplicate

trait Comonad[W[_]] extends Functor[W] {
  def extract[A](wa: W[A]): A

  def duplicate[A](wa: W[A]): W[W[A]] =
    extend(identity[W[A]])(wa)

  def extend[A, B](f: W[A] => B)(wa: W[A]): W[B] =
    (fmap(f) _ compose duplicate)(wa)
}

这里提供了用 duplicate 定义 extend，以及用 extend 定义 duplicate 的默认实现，所以只需要覆盖其中一个。

这些函数背后的直觉基于这样一个想法：一般来说，余单子可以看作一个装满 a 类型值的容器（product 余单子只是只含一个值的特殊情况）。其中有一个“当前”值的概念，并且可以通过 extract 轻易访问它。余 Kleisli 箭头执行某个聚焦在当前值上的计算，但它能够访问周围的所有值。

想想 Conway 的生命游戏。每个单元格包含一个值（通常只是 True 或 False）。与生命游戏对应的余单子会是一个单元格网格，并聚焦在“当前”单元格上。

那么 duplicate 做了什么？它接收一个余单子容器 w a，并产生一个容器的容器 w (w a)。想法是，这些容器中的每一个都聚焦在原来 w a 内部不同的 a 上。在生命游戏中，你会得到一个网格的网格：外层网格的每个单元格都包含一个内层网格，而这个内层网格聚焦在不同单元格上。

现在看 extend。它接收一个余 Kleisli 箭头和一个装满 a 的余单子容器 w a。它把这个计算应用到所有这些 a 上，把它们替换为 b。结果是一个装满 b 的余单子容器。extend 通过把焦点从一个 a 移动到另一个 a，并依次对每个焦点应用余 Kleisli 箭头来做到这一点。在生命游戏中，余 Kleisli 箭头会计算当前单元格的新状态。为此，它会查看自己的上下文，也就是很可能查看最近的邻居。

extend 的默认实现说明了这个过程。首先调用 duplicate 产生所有可能的焦点，然后把 f 应用于每一个焦点。

23.4 Stream 余单子（The Stream Comonad）

从容器的一个元素移动焦点到另一个元素，这个过程最适合用无限流的例子说明。这种流就像列表，只是没有空构造器：

data Stream a = Cons a (Stream a)

case class Stream[A](h: () => A, t: () => Stream[A])

它显然是一个 Functor：

instance Functor Stream where
    fmap f (Cons a as) = Cons (f a) (fmap f as)

implicit val streamFunctor = new Functor[Stream] {
  def fmap[A, B](f: A => B)(fa: Stream[A]): Stream[B] = fa match {
    case Stream(a, as) =>
      Stream(() => f(a()), () => fmap(f)(as()))
  }
}

流的焦点是它的第一个元素，因此 extract 的实现如下：

extract (Cons a _) = a

def extract[A](wa: Stream[A]): A = wa match {
  case Stream(a, _) => a()
}

duplicate 产生一个流的流，每个流都聚焦在不同元素上。

duplicate (Cons a as) = Cons (Cons a as) (duplicate as)

def duplicateS[A](wa: Stream[A]): Stream[Stream[A]] = wa match {
  case s @ Stream(a, as) =>
    Stream(() => s, () => duplicateS(as()))
}

第一个元素是原始流，第二个元素是原始流的尾部，第三个元素是尾部的尾部，如此无穷无尽。下面是完整实例：

instance Comonad Stream where
    extract (Cons a _) = a
    duplicate (Cons a as) = Cons (Cons a as) (duplicate as)

implicit val streamComonad = new Comonad[Stream] {
  def extract[A](wa: Stream[A]): A =
    wa match {
      case Stream(a, _) => a()
    }

  def duplicate[A](wa: Stream[A]): Stream[Stream[A]] = wa match {
    case s @ Stream(a, as) =>
      Stream(() => s, () => duplicate(as()))
  }
}

这是看待流的一种非常函数式的方式。在命令式语言中，我们大概会从一个 advance 方法开始，它把流向前移动一个位置。而在这里，duplicate 一次性产生所有移动后的流。Haskell 的惰性让这成为可能，甚至成为可取的做法。当然，为了让 Stream 变得实用，我们也会实现 advance 的类似物：

tail :: Stream a -> Stream a
tail (Cons a as) = as

def tail[A]: Stream[A] => Stream[A] = {
  case Stream(a, as) => as()
}

但它永远不是余单子接口的一部分。

如果你有数字信号处理经验，就会立刻看出，流的余 Kleisli 箭头就是一个数字滤波器，而 extend 产生一个过滤后的流。

作为一个简单例子，让我们实现移动平均滤波器。下面这个函数对流的前 n 个元素求和：

sumS :: Num a => Int -> Stream a -> a
sumS n (Cons a as) = if n <= 0 then 0 else a + sumS (n - 1) as

def sumS[A](n: Int)(stm: Stream[A])(implicit numeric: Numeric[A]): A =
  stm match {
    case Stream(a, as) =>
      import numeric._
      if (n <= 0) zero else a() + sumS(n - 1)(as())
  }

下面这个函数计算流的前 n 个元素的平均值：

average :: Fractional a => Int -> Stream a -> a
average n stm = (sumS n stm) / (fromIntegral n)

def average[A](n: Int)
  (implicit fractional: Fractional[A]): Stream[A] => A = stm => {
    import fractional._
    sumS(n)(stm) / fromInt(n)
  }

部分应用的 average n 是一个余 Kleisli 箭头，因此我们可以把它扩展到整个流上：

movingAvg :: Fractional a => Int -> Stream a -> Stream a
movingAvg n = extend (average n)

def movingAvg[A](n: Int)(stm: Stream[A])
  (implicit fractional: Fractional[A]): Stream[A] =
    streamComonad.
      extend(average(n)(fractional))(stm)

结果是由运行平均值组成的流。

流是一种单向、一维的余单子例子。它很容易变成双向的，也很容易扩展到二维或更多维。

23.5 范畴意义下的余单子（Comonad Categorically）

在范畴论中定义余单子，是一个直接的对偶化练习。和单子一样，我们从自函子 T 开始。定义单子的两个自然变换 eta 和 mu，在余单子中只是被反转：

epsilon :: T -> I
delta   :: T -> T^2

这些变换的分量对应 extract 和 duplicate。余单子律是单子律的镜像。这里没有什么意外。

然后还有从伴随推导单子的过程。对偶性会反转一个伴随：左伴随变成右伴随，右伴随变成左伴随。既然组合 R . L 定义一个单子，那么 L . R 必定定义一个余单子。伴随的余单位：

epsilon :: L . R -> I

确实就是我们在余单子定义中看到的同一个 epsilon；按分量看，就是 Haskell 的 extract。我们还可以使用伴随的单位：

eta :: I -> R . L

把一个 R . L 插入 L . R 中间，从而产生 L . R . L . R。从 T 构造 T^2 定义了 delta，这就完成了余单子的定义。

我们还看到过，单子是幺半群。这个陈述的对偶会需要用到余幺半群。那么什么是余幺半群？把幺半群原本作为单对象范畴的定义对偶化，并不会得到什么有趣的东西。当你反转所有自同态的方向时，只会得到另一个幺半群。

不过请回忆，我们讨论单子时使用了更一般的幺半群定义：幺半范畴中的对象。这个构造基于两个态射：

mu  :: m * m -> m
eta :: i -> m

反转这些态射，就在幺半范畴中产生了一个余幺半群：

delta   :: m -> m * m
epsilon :: m -> i

可以在 Haskell 中写出余幺半群的定义：

class Comonoid m where
    split   :: m -> (m, m)
    destroy :: m -> ()

trait Comonoid[M] {
  def split(x: M): (M, M)
  def destroy(x: M): Unit
}

但它相当平凡。显然，destroy 会忽略自己的参数。

destroy _ = ()

def destroy(x: M): Unit = ()

split 只是一对函数：

split x = (f x, g x)

def split(x: M): (M, M) = (f(x), g(x))

现在考虑与幺半群单位律对偶的余幺半群律。

lambda . bimap destroy id . split = id
rho . bimap id destroy . split = id

(lambda compose bimap(destroy)(identity[M]))
  .compose(split) == identity[M]

(rho compose bimap(identity[M])(destroy))
  .compose(split) == identity[M]

这里，lambda 和 rho 分别是左、右单位子（参见幺半范畴的定义）。代入定义后得到：

lambda (bimap destroy id (split x))
= lambda (bimap destroy id (f x, g x))
= lambda ((), g x)
= g x

lambda(bimap(destroy)(identity[M])(split(x))) ==
lambda(bimap(destroy)(identity[M])((f(x), g(x)))) ==
lambda(((), g(x))) ==
g(x)

这证明 g = id。类似地，第二条律展开后得到 f = id。因此：

split x = (x, x)

def split(x: M): (M, M) = (x, x)

这说明在 Haskell 中（更一般地，在范畴 Set 中），每个对象都是平凡的余幺半群。

幸运的是，还有其他更有趣的幺半范畴可以用来定义余幺半群。自函子范畴就是其中之一。事实证明，正如单子是自函子范畴中的幺半群：

余单子是自函子范畴中的余幺半群。

23.6 Store 余单子（The Store Comonad）

余单子的另一个重要例子是状态单子的对偶。它称为余状态余单子，或者也叫 store 余单子。

我们之前看到，状态单子由定义指数对象的伴随生成：

L z = z x s
R a = s => a

我们将使用同一个伴随来定义余状态余单子。余单子由组合 L . R 定义：

L (R a) = (s => a) x s

把它翻译到 Haskell，我们从左侧的 Product 函子与右侧的 Reader 函子之间的伴随开始。把 Product 组合在 Reader 之后，等价于下面的定义：

data Store s a = Store (s -> a) s

case class Store[S, A](run: S => A, s: S)

伴随的余单位在对象 a 处是下面这个态射：

epsilon_a :: ((s => a) x s) -> a

或者用 Haskell 记法写成：

counit (Prod (Reader f) s) = f s

def counit[S, A](a: Product[S, Reader[S, A]]): A = a match {
  case Product((Reader(f), s)) => f(s)
}

这会成为我们的 extract：

extract (Store f s) = f s

def extract[A](wa: Store[S, A]): A = wa match {
  case Store(f, s) => f(s)
}

伴随的单位：

unit :: a -> Reader s (Product a s)
unit a = Reader (\s -> Prod a s)

def unit[S, A](a: A): Reader[S, Product[S, A]] =
  Reader(s => Product((a, s)))

可以重写为部分应用的数据构造器：

Store f :: s -> Store f s

object Store {
  def apply[S, A](run: S => A): S => Store[S, A] =
    s => new Store(run, s)
}

我们把 delta，也就是 duplicate，构造为水平组合：

delta :: L . R -> L . R . L . R
delta = L . eta . R

我们必须把 eta 偷渡过最左边的 L，也就是 Product 函子。这意味着用 eta，或者说 Store f，作用在 pair 的左分量上（这也正是 Product 的 fmap 会做的事情）。得到：

duplicate (Store f s) = Store (Store f) s

def duplicate[A](wa: Store[S, A]): Store[S, Store[S, A]] = wa match {
  case Store(f, s) => Store(Store(f), s)
}

（记住，在 delta 的公式中，L 和 R 代表恒等自然变换，其分量是恒等态射。）

下面是 Store 余单子的完整定义：

instance Comonad (Store s) where
    extract (Store f s) = f s
    duplicate (Store f s) = Store (Store f) s

implicit def storeComonad[S] = new Comonad[Store[S, ?]] {
  def extract[A](wa: Store[S, A]): A = wa match {
    case Store(f, s) => f(s)
  }

  override def duplicate[A](wa: Store[S, A]): Store[S, Store[S, A]] =
    wa match {
      case Store(f, s) => Store(Store(f), s)
    }
}

你可以把 Store 的 Reader 部分想成一个广义容器，其中的 a 由类型 s 的元素作为键来索引。例如，如果 s 是 Int，那么 Reader Int a 就是一个由 a 组成的无限双向流。Store 把这个容器与一个键类型的值配对。例如，Reader Int a 会与一个 Int 配对。在这种情况下，extract 使用这个整数索引到无限流中。你可以把 Store 的第二个分量看作当前位置。

继续这个例子，duplicate 会创建一个新的无限流，它由 Int 索引。这个流以流作为元素。特别地，在当前位置上，它包含原始流。但如果你使用其他 Int（正数或负数）作为键，就会得到一个移动后的流，它定位在那个新索引上。

一般来说，你可以说服自己，当 extract 作用在被 duplicate 过的 Store 上时，会产生原始的 Store（事实上，余单子的恒等律声明 extract . duplicate = id）。

Store 余单子在 Lens 库的理论基础中扮演重要角色。概念上，Store s a 余单子封装了“聚焦”到数据类型 a 中某个特定子结构的思想（就像透镜一样），并使用类型 s 作为索引。特别是，一个类型为下面这样的函数：

a -> Store s a

A => Store[S, A]

等价于一对函数：

set :: a -> s -> a
get :: a -> s

def set[A, S]: A => S => A
def get[A, S]: A => S

如果 a 是 product 类型，那么 set 可以实现为设置 a 内部类型为 s 的字段，并返回修改后的 a。类似地，get 可以实现为读取 a 中 s 字段的值。下一节我们会继续探索这些思想。

23.7 挑战（Challenges）

使用 Store 余单子实现 Conway 的生命游戏。提示：你会为 s 选择什么类型？

23.1 使用余单子编程（Programming with Comonads）​

23.2 Product 余单子（The Product Comonad）​

23.3 剖析组合（Dissecting the Composition）​

23.4 Stream 余单子（The Stream Comonad）​

23.5 范畴意义下的余单子（Comonad Categorically）​

23.6 Store 余单子（The Store Comonad）​

23.7 挑战（Challenges）​