Skip to main content

第 4 章：Kleisli 范畴（Kleisli Categories）

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

你已经看到如何把类型和纯函数建模为一个范畴。我也提到过，范畴论中有办法建模副作用，或者说非纯函数。我们来看一个例子：记录或跟踪执行过程的函数。在命令式语言中，这类功能很可能通过修改某个全局状态实现，例如：

string logger;

bool negate(bool b) {
    logger += "Not so! ";
    return !b;
}

你知道这不是纯函数，因为它的记忆化版本无法产生日志。这个函数有副作用（side effects）。

在现代编程中，我们尽量远离全局可变状态，哪怕只是因为并发会带来复杂性。你也绝不会把这样的代码放进库里。

幸运的是，可以把这个函数变成纯函数。只需要把日志显式地传入和传出。我们添加一个字符串参数，并把常规输出与包含更新后日志的字符串配成一对：

pair<bool, string> negate(bool b, string logger) {
    return make_pair(!b, logger + "Not so! ");
}

这个函数是纯的，没有副作用。用相同参数调用时，它每次都返回同一对值，并且必要时可以被记忆化。不过，考虑到日志具有累积性质，你必须记忆化所有可能导致给定调用的历史。例如，下面两个调用会对应不同的记忆化条目：

negate(true, "It was the best of times. ");

以及：

negate(true, "It was the worst of times. ");

如此等等。

这也不是一个很好的库函数接口。调用者可以自由忽略返回类型中的字符串，所以负担不算太大；但他们被迫传入一个字符串，这可能很不方便。

有没有更不侵入的方式完成同一件事？有没有办法分离关注点？在这个简单例子中，negate 函数的主要目的，是把一个 Boolean 转成另一个 Boolean。日志是次要的。诚然，记录的消息是函数特有的，但把消息聚合成连续日志这项任务，是另一个关注点。我们仍然希望函数产生字符串，但不希望让它负责生成完整日志。因此折中方案如下：

pair<bool, string> negate(bool b) {
    return make_pair(!b, "Not so! ");
}

想法是：日志会在函数调用之间聚合。

为了看看这如何完成，换一个稍微更现实的例子。我们有一个从字符串到字符串的函数，它把小写字符转成大写：

string toUpper(string s) {
    string result;
    int (*toupperp)(int) = &toupper; // toupper is overloaded
    transform(begin(s), end(s), back_inserter(result), toupperp);
    return result;
}

还有另一个函数，它把字符串按空白边界拆分为字符串向量：

vector<string> toWords(string s) {
    return words(s);
}

实际工作由辅助函数 words 完成：

vector<string> words(string s) {
    vector<string> result{""};
    for (auto i = begin(s); i != end(s); ++i)
    {
        if (isspace(*i))
            result.push_back("");
        else
            result.back() += *i;
    }
    return result;
}

我们想修改 toUpper 和 toWords，让它们在常规返回值之外附带一条消息字符串。

附加在返回值上的日志消息

我们会“装饰”这些函数的返回值。先用泛型方式定义一个 Writer，它封装一对值：第一部分是任意类型 A 的值，第二部分是字符串。

type Writer[A] = (A, String)

下面是装饰后的函数：

val upCase: String => Writer[String] =
  s => (s.toUpperCase, "upCase ")

val toWords: String => Writer[List[String]] =
  s => (s.split(' ').toList, "toWords ")

我们想把这两个函数组合成另一个装饰函数：它把字符串变成大写并拆分成单词，同时生成这些动作的日志。可以这样做：

val process: String => Writer[List[String]] =
  s => {
    val p1 = upCase(s)
    val p2 = toWords(p1._1)
    (p2._1, p1._2 + p2._2)
  }

目标已经达成：日志聚合不再是单个函数的职责。它们只生成自己的消息，然后在外部连接成更大的日志。

现在想象整个程序都以这种风格编写。那会是一场重复且容易出错的噩梦。但我们是程序员，知道如何处理重复代码：抽象它！不过这不是普通抽象，我们必须抽象函数组合本身。组合正是范畴论的本质，所以在写更多代码之前，我们先从范畴角度分析这个问题。

4.1 Writer 范畴（The Writer Category）​

把一组函数的返回类型装饰起来，从而附带某些额外功能，这个想法非常有成果。后面会看到更多例子。起点是通常的类型与函数范畴。我们保留类型作为对象，但把态射重新定义为装饰函数。

例如，假设想装饰函数 isEven，它从 Int 到 Boolean。我们把它变成一个由装饰函数表示的态射。关键点是：这个态射仍然被看作对象 Int 与 Boolean 之间的箭头，尽管装饰函数返回的是一对值：

val isEven: Int => Writer[Boolean] =
  n => (n % 2 == 0, "isEven ")

根据范畴法则，应该能把这个态射与另一个从对象 Boolean 到某个对象的态射组合。特别是，应该能把它与前面的 negate 组合：

val negate: Boolean => Writer[Boolean] =
  b => (!b, "Not so! ")

显然，不能像组合普通函数那样组合这两个态射，因为输入输出并不匹配。它们的组合更像这样：

val isOdd: Int => Writer[Boolean] =
  n => {
    val p1 = isEven(n)
    val p2 = negate(p1._1)
    (p2._1, p1._2 + p2._2)
  }

因此，在我们正在构造的新范畴中，两个态射的组合配方如下：

  1. 执行第一个态射对应的装饰函数。
  2. 提取结果对的第一部分，并把它传给第二个态射对应的装饰函数。
  3. 连接第一个结果的第二部分（字符串）和第二个结果的第二部分（字符串）。
  4. 返回一个新对，它把最终结果的第一部分与连接后的字符串组合起来。

如果要在 Scala 中把这种组合作为高阶函数抽象，可以用三个类型参数对应范畴中的三个对象。它接收两个按规则可组合的装饰函数，并返回第三个装饰函数：

def compose[A, B, C](
    m1: A => Writer[B],
    m2: B => Writer[C]
): A => Writer[C] =
  x => {
    val p1 = m1(x)
    val p2 = m2(p1._1)
    (p2._1, p1._2 + p2._2)
  }

现在可以回到前面的例子，用这个新函数实现 upCase 与 toWords 的组合：

val process: String => Writer[List[String]] =
  compose(upCase, toWords)

但还没结束。我们已经定义了新范畴中的组合，那么恒等态射是什么？它们不是普通恒等函数！它们必须是从类型 A 回到类型 A 的态射，也就是说，它们是如下形式的装饰函数：

A => Writer[A]

它们必须相对于组合表现为单位元。观察组合定义可知，恒等态射应该原样传递参数，并且只向日志贡献空字符串：

def pure[A](x: A): Writer[A] = (x, "")

很容易说服自己：刚才定义的确实是合法范畴。特别是，我们的组合显然满足结合律。如果跟踪每个 pair 的第一部分，会发现它只是普通函数组合，而普通函数组合满足结合律。第二部分则是字符串连接，而字符串连接也满足结合律。

敏锐的读者可能注意到，这个构造很容易推广到任意幺半群，而不只是字符串幺半群。在 compose 中使用幺半群的 combine，在 pure 中使用 empty，替代 + 和 "" 即可。没有理由把日志限制为字符串。优秀的库作者应该能识别让库运转所需的最小约束。这里，日志库唯一的要求就是日志具有幺半群性质。

4.2 Scala 中的 Writer（Writer in Scala）​

同样的东西在 Scala 中可以写得更紧凑，而且编译器也能提供更多帮助。先定义 Writer 类型：

type Writer[A] = (A, String)

这里定义的是类型别名，等价于 C++ 中的 typedef 或 using。Writer 由类型变量 A 参数化，等价于 A 与 String 的二元组。元组语法很小：两个元素放在括号中，用逗号分隔。

我们的态射是从任意类型到某个 Writer 类型的函数：

A => Writer[B]

把组合声明成一个有趣的中缀操作符，通常称为“fish”：

def >=>[A, B, C](m1: A => Writer[B], m2: B => Writer[C]): A => Writer[C]

它是一个接收两个参数的函数，而每个参数本身都是函数，并且返回一个函数。第一个参数类型为 A => Writer[B]，第二个参数类型为 B => Writer[C]，结果类型为 A => Writer[C]。

下面是这个中缀操作符的定义。为了能把 >=> 用作中缀操作符，我们把它放在隐式类中：

object kleisli {
  // allows us to use >=> as an infix operator
  implicit class KleisliOps[A, B](m1: A => Writer[B]) {
    def >=>[C](m2: B => Writer[C]): A => Writer[C] =
      x => {
        val (y, s1) = m1(x)
        val (z, s2) = m2(y)
        (z, s1 + s2)
      }
    }
}

结果是一个接收参数 x 的 lambda 函数。这里先把调用 m1 的结果模式匹配为一对变量 (y, s1)；再用第一个模式中的参数 y 调用 m2，并把结果匹配为 (z, s2)。最后返回一个 pair，第一部分是 z，第二部分是两个字符串 s1 + s2 的连接。

在 Scala 中，也经常通过模式匹配拆开 tuple，而不是使用访问器。除此之外，这个实现与 C++ 版本有直接对应关系。

还要定义这个范畴的恒等态射。为了与 Scala 生态中更常见的命名接近，这里称为 pure：

def pure[A](x: A): Writer[A] = (x, "")

为了完整起见，下面是装饰函数 upCase 和 toWords 的 Scala 版本：

val upCase: String => Writer[String] =
  s => (s.toUpperCase, "upCase ")

val toWords: String => Writer[List[String]] =
  s => (s.split(' ').toList, "toWords ")

最后，借助 fish 操作符完成两个函数的组合：

val process: String => Writer[List[String]] = {
  import kleisli._
  upCase >=> toWords
}

4.3 Kleisli 范畴（Kleisli Categories）​

你可能已经猜到，我并不是当场发明了这个范畴。它是所谓 Kleisli 范畴的一个例子，也就是基于单子的范畴。我们还没准备好讨论单子，但我想让你先尝尝它们能做什么。就当前有限目的而言，Kleisli 范畴的对象是底层编程语言中的类型。从类型 $A$ 到类型 $B$ 的态射，是从 $A$ 到某个由 $B$ 经过特定装饰得到的类型的函数。每个 Kleisli 范畴都会定义自己组合这些态射的方式，以及相对于该组合的恒等态射。稍后会看到，“装饰”这个不精确术语对应于范畴中自函子的概念。

本章中作为这个范畴基础的特定单子称为 writer monad，它用于记录日志或跟踪函数执行。它也是把效果嵌入纯计算这一更一般机制的例子。前面已经看到，可以在集合范畴中建模编程语言的类型和函数，照例忽略底。这里，我们把模型扩展到一个略有不同的范畴。在这个范畴中，态射由装饰函数表示，它们的组合不只是把一个函数的输出传给另一个函数的输入。我们获得了一个额外自由度：组合本身。事实证明，正是这个自由度让我们能够为那些在命令式语言中传统上用副作用实现的程序，给出简单的指称语义。

挑战​

没有为所有可能参数值定义的函数称为部分函数。它在数学意义上并不是真正的函数，因此不适合标准范畴模型。不过，可以用返回装饰类型 optional 的函数表示它：

template<typename A>
class optional {
    bool _isValid;
    A _value;
public:
    optional()    : _isValid(false) {}
    optional(A v) : _isValid(true), _value(v) {}
    bool isValid() const { return _isValid; }
    A value() const { return _value; }
};

例如，下面是装饰函数 safe_root 的实现：

optional<double> safe_root(double x) {
    if (x >= 0) return optional<double>{sqrt(x)};
    else return optional<double>{};
}

挑战如下：

  1. 为部分函数构造 Kleisli 范畴，定义组合与恒等态射。
  2. 实现装饰函数 safe_reciprocal：如果参数不为零，就返回有效的倒数。
  3. 组合函数 safe_root 和 safe_reciprocal，实现 safe_root_reciprocal，在可能时计算 sqrt(1/x)。