第 6 章：简单代数数据类型（Simple Algebraic Data Types）

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

我们已经见过两种组合类型的基本方式：使用积与余积。事实证明，日常编程中的许多数据结构都可以只用这两种机制构建。这个事实有重要的实践后果。数据结构的许多性质是可组合的。例如，如果你知道如何比较基础类型的值是否相等，也知道如何把这些比较推广到积类型和余积类型，那么就可以自动推导复合类型的相等运算。在 Haskell 中，对很大一部分复合类型，可以自动派生相等性、比较、与字符串之间的转换等能力。在 Scala 中，也能通过 case class、sealed trait 以及派生机制获得类似收益。

让我们更仔细地看看编程中的积类型和和类型。

6.1 积类型（Product Types）

编程语言中两个类型的积的标准实现是 pair。在 Haskell 中，pair 是原始类型构造器；在 C++ 中，它是标准库定义的相对复杂的模板；在 Scala 中，二元组 (A, B) 是最直接的表示。

pair

pair 并不严格交换：(Int, Boolean) 不能替代 (Boolean, Int)，尽管它们携带相同信息。不过，它们在同构意义下交换；这个同构由 swap 函数给出，并且它本身就是自己的逆：

def swap[A, B]: ((A, B)) => (B, A) = {
  case (x, y) => (y, x)
}

可以把这两个 pair 想成用不同格式存储同一份数据。就像大端序与小端序。

可以通过在 pair 中嵌套 pair，把任意数量的类型组合成积。但还有更简单的方式：嵌套 pair 等价于 tuple。这是因为 pair 的不同嵌套方式彼此同构。如果想按顺序把三个类型 A、B 和 C 组合成积，可以有两种方式：

((A, B), C)

或者：

(A, (B, C))

这些类型不同，不能把一个传给期待另一个的函数，但它们的元素一一对应。存在一个函数把一种映射到另一种：

def alpha[A, B, C]: (((A, B), C)) => ((A, (B, C))) = {
  case ((x, y), z) => (x, (y, z))
}

这个函数可逆：

def alphaInv[A, B, C]: ((A, (B, C))) => (((A, B), C)) = {
  case (x, (y, z)) => ((x, y), z)
}

因此它是一个同构。它们只是重新打包同一份数据的不同方式。

可以把创建积类型解释为类型上的二元运算。从这个角度看，上面的同构很像我们在幺半群中见过的结合律：

$$ (a * b) * c = a * (b * c) $$

不同之处在于，幺半群中两种组合积的方式是相等的；而这里它们只是在“同构意义下”相等。

如果能接受同构，而不坚持严格相等，还可以进一步说明 unit 类型 Unit 是积的单位元，就像 1 是乘法的单位元一样。确实，把某个类型 A 的值与 unit 配成 pair，并不会增加任何信息。类型：

(A, Unit)

与 A 同构。同构如下：

def rho[A]: ((A, Unit)) => A = {
  case (x, ()) => x
}

def rhoInv[A]: A => (A, Unit) =
  x => (x, ())

这些观察可以形式化为：$Set$，也就是集合范畴，是一个幺半范畴（monoidal category）。它是一个同时也是幺半群的范畴，意思是可以“相乘”对象，这里就是取笛卡尔积。后面会更详细讨论幺半范畴，并给出完整定义。

在 Scala 中，除了使用普通 tuple，也可以用命名构造器定义积类型，尤其是当它们与和类型组合时。一个 pair 可以替代性地定义为：

sealed trait Pair[A, B]
case class P[A, B](a: A, b: B) extends Pair[A, B]

这里，Pair[A, B] 是由两个类型参数化的类型名，P 是数据构造器名。通过把两个类型传给 Pair 类型构造器来定义 pair 类型；通过把两个合适类型的值传给构造器 P 来构造 pair 值。例如，定义一个 stmt 值作为 String 和 Boolean 的 pair：

val stmt: Pair[String, Boolean] =
  P("This statement is", false)

第一行是类型签名，它使用类型构造器 Pair，并用 String 与 Boolean 替代泛型定义中的 A 和 B。第二行通过把具体字符串和具体布尔值传给数据构造器 P 来定义实际值。类型构造器用于构造类型；数据构造器用于构造值。

Scala 的 case class 可以更直接地表达同样想法：

case class Pair[A, B](a: A, b: B)

如果眯起眼睛看，也可以把内建 pair 类型看成这种声明的变体，只不过类型名和构造器换成了 tuple 语法：

val stmt = ("This statement is", false)

类似地，可以使用三元组、四元组，等等。

除了使用泛型 pair 或 tuple，也可以定义特定的命名积类型，例如：

case class Stmt(s: String, b: Boolean)

这只是 String 与 Boolean 的积，但它有自己的名字和构造器。这种声明风格的优点是，可以定义许多内容相同但含义和功能不同的类型，而且它们不能彼此替代。

使用 tuple 和多参数构造器编程，可能会变得混乱且容易出错，因为你必须跟踪哪个分量代表什么。通常最好给分量命名。带命名字段的积类型在 Haskell 中称为 record，在 C 中称为 struct，在 Scala 中最常见的形式则是 case class。

6.2 记录（Records）

来看一个简单例子。我们想描述化学元素，把两个字符串（名称和符号）以及一个整数（原子序数）组合成一个数据结构。可以使用 tuple (String, String, Int)，并记住每个分量代表什么。可以通过模式匹配提取分量，例如下面这个函数检查元素符号是否是元素名称的前缀，像 He 是 Helium 的前缀：

val startsWithSymbol: ((String, String, Int)) => Boolean = {
  case (name, symbol, _) => name.startsWith(symbol)
}

这段代码容易出错，也不易阅读和维护。更好的做法是定义一个 record：

case class Element(
  name: String,
  symbol: String,
  atomicNumber: Int
)

这两种表示是同构的，下面两个转换函数互为逆：

val tupleToElem: ((String, String, Int)) => Element = {
  case (n, s, a) => Element(n, s, a)
}

val elemToTuple: Element => (String, String, Int) =
  e => (e.name, e.symbol, e.atomicNumber)

注意，record 字段名也可用于访问字段。例如，e.atomicNumber 会从 e 中取出 atomicNumber 字段。概念上，可以把字段访问器看作类型为：

val atomicNumber: Element => Int

的函数。

使用 Element 的记录语法后，startsWithSymbol 函数更易读：

val startsWithSymbol: Element => Boolean =
  e => e.name startsWith e.symbol

也可以写成类似句子的形式：

val startsWithSymbol: Element => Boolean =
  e => e.name startsWith e.symbol

这里的中缀调用只是 Scala 方法调用语法。

6.3 和类型（Sum Types）

正如集合范畴中的积产生积类型，余积产生和类型。Scala 中和类型的标准编码是 sealed trait 加 case class 或 case object。类似 Either 可以定义为：

sealed trait Either[+A, +B]
case class Left[A](v: A) extends Either[A, Nothing]
case class Right[B](v: B) extends Either[Nothing, B]

和 pair 一样，Either 在同构意义下也是交换的，可以嵌套，而且嵌套顺序在同构意义下无关紧要。例如，可以定义一个三者择一的和类型：

sealed trait OneOfThree[+A, +B, +C]
case class Sinistral[A](v: A) extends OneOfThree[A, Nothing, Nothing]
case class Medial[B](v: B) extends OneOfThree[Nothing, B, Nothing]
case class Dextral[C](v: C) extends OneOfThree[Nothing, Nothing, C]

事实证明，$Set$ 关于余积也是一个对称幺半范畴。二元运算由不交和扮演，单位元由始对象扮演。用类型来说，Either 是幺半运算符，而无值类型 Nothing 是其中性元素。可以把 Either 想成加法，把 Nothing 想成零。确实，给和类型加上 Nothing 不会改变内容。例如：

Either[A, Nothing]

与 A 同构。这是因为没有办法构造这个类型的 Right 版本，因为没有 Nothing 类型的值。Either[A, Nothing] 的唯一居民都由 Left 构造器构造，并且只是封装一个 A 类型的值。符号化地说，$a + 0 = a$。

和类型在 Haskell 和 Scala 中都很常见，但它们在 C++ 中的对应物 union 或 variant 要少见得多，原因有几个。

首先，最简单的和类型只是枚举，并用 C++ 的 enum 实现。Scala 中的和类型：

sealed trait Color
case object Red extends Color
case object Green extends Color
case object Blue extends Color

对应 C++ 中的：

enum { Red, Green, Blue };

更简单的和类型：

sealed trait Bool
case object True extends Bool
case object False extends Bool

对应 C++ 中的原始 bool。

编码值存在或缺失的简单和类型，在 C++ 中常常用特殊技巧和“不可能”的值实现，例如空字符串、负数、空指针等。如果有意表达这种可选性，在 Scala 中通常用 Option 类型：

sealed trait Option[+A]
case object None extends Option[Nothing]
case class Some[A](a: A) extends Option[A]

Option 是两个类型的和。把两个构造器分离成独立类型就能看出来。第一个类似：

case object NoneType

这是一个只有一个值 NoneType 的枚举。换句话说，它是单例，等价于 unit 类型 Unit。第二部分：

case class SomeType[A](a: A)

只是对类型 A 的封装。因此，可以把 Option 编码为：

type Option[A] = Either[Unit, A]

更复杂的和类型在 C++ 中常常用指针伪装。指针要么为空，要么指向特定类型的值。例如，Scala 列表类型可以定义为一个递归和类型：

sealed trait List[+A]
case object Nil extends List[Nothing]
case class Cons[A](h: A, t: List[A]) extends List[A]

在 C++ 中，可以用空指针技巧来实现空列表：

template<typename A>
class List {
    Node<A> * _head;
public:
    List() : _head(nullptr) {} // Nil
    List(A a, List<A> l)       // Cons
      : _head(new Node<A>(a, l))
    {}
};

注意，Scala 的两个构造器 Nil 和 Cons 被翻译成两个重载的 List 构造器，它们具有类似参数：Nil 没有参数，Cons 有一个值和一个列表。List 类不需要标签来区分和类型的两个分量，而是使用 _head 的特殊 nullptr 值来编码 Nil。

不过，Scala/Haskell 与 C++ 类型之间的主要差异在于，函数式数据结构通常不可变。如果用某个特定构造器创建对象，对象会永远记住使用了哪个构造器，以及传入了哪些参数。因此，一个被创建为 Some("energy") 的 Option 对象永远不会变成 None。类似地，空列表会永远为空，三元素列表也会一直有同样三个元素。

正是这种不可变性让构造变得可逆。给定一个对象，你总能把它拆回构造它时使用的部分。这种解构通过模式匹配完成，并复用构造器作为模式。构造器参数如果存在，就替换为变量或其他模式。

List 数据类型有两个构造器，所以任意 List 的解构使用两个对应构造器的模式。一个匹配空 Nil 列表，另一个匹配由 Cons 构造的列表。例如，下面是一个作用在 List 上的简单函数：

def maybeTail[A]: List[A] => Option[List[A]] = {
  case Nil => None
  case Cons(_, t) => Some(t)
}

maybeTail 定义的第一部分使用 Nil 构造器作为模式，并返回 None。第二部分使用 Cons 构造器作为模式。它把第一个构造器参数替换为通配符，因为我们不关心它。Cons 的第二个参数绑定到变量 t，返回值是 Some(t)。根据你的 List 是如何创建的，它会匹配其中一个分支。如果它是用 Cons 创建的，传入构造器的两个参数会被取回，第一个会被丢弃。

更复杂的和类型在 C++ 中会用多态类层次结构实现。拥有共同祖先的一族类可以理解为一种 variant 类型，其中 vtable 充当隐藏标签。Haskell 或 Scala 通过对构造器做模式匹配并调用专门代码完成的事，在 C++ 中则通过基于 vtable 指针分派虚函数调用完成。

你很少会看到 C++ 的 union 被用作和类型，因为 union 能放入的内容有很严重限制。甚至不能把 std::string 放进 union，因为它有拷贝构造器。

6.4 类型代数（Algebra of Types）

单独来看，积类型和和类型都能用于定义各种有用数据结构，但真正的力量来自把二者组合起来。我们再次调用组合的力量。

总结一下目前发现的内容。我们已经看到类型系统底下有两种交换幺半结构：以 Nothing 为中性元素的和类型，以及以 unit 类型 Unit 为中性元素的积类型。我们想把它们类比为加法和乘法。在这个类比中，Nothing 对应零，而 unit () 对应一。

看看这个类比能走多远。例如，乘以零是否得到零？换句话说，如果积类型有一个分量是 Nothing，它是否同构于 Nothing？例如，能否创建一个由 Int 和 Nothing 组成的 pair？

要创建 pair，需要两个值。虽然很容易给出一个整数，但没有 Nothing 类型的值。因此，对任意类型 A，类型 (A, Nothing) 都没有居民，也就是没有值，因此等价于 Nothing。换句话说，$a \times 0 = 0$。

另一个连接加法与乘法的性质是分配律：

$$ a \times (b + c) = a \times b + a \times c $$

它对积类型和和类型也成立吗？是的，照例是在同构意义下成立。左边对应类型：

(A, Either[B, C])

右边对应类型：

Either[(A, B), (A, C)]

下面是从左到右的转换函数：

def prodToSum[A, B, C]: ((A, Either[B, C])) => Either[(A, B), (A, C)] = {
  case (x, e) => e match {
    case Left(y) => Left((x, y))
    case Right(z) => Right((x, z))
  }
}

下面是反方向函数：

def sumToProd[A, B, C]: Either[(A, B), (A, C)] => (A, Either[B, C]) = {
  case Left((x, y)) => (x, Left(y))
  case Right((x, z)) => (x, Right(z))
}

match 子句用于在函数内部做模式匹配。每个模式后面跟着箭头和匹配时求值的表达式。例如，如果用下面的值调用 prodToSum：

val prod1: (Int, Either[String, Float]) =
  (2, Left("Hi!"))

那么 e match 中的 e 等于 Left("Hi!")。它会匹配模式 Left(y)，把 "Hi!" 替换给 y。由于 x 已经匹配为 2，所以 match 子句以及整个函数的结果会是 Left((2, "Hi!"))，正如预期。

我不会证明这两个函数互为逆，但只要想一想，它们必然如此！它们只是平凡地重新打包两个数据结构的内容。数据相同，只是格式不同。

数学家给这种相互交织的两个幺半群起了名字：半环（semiring）。它不是完整的环（ring），因为无法定义类型的减法。所以半环有时也称为 rig，这是 “ring without an n” 的双关，也就是没有负数。但除此以外，把关于自然数这类 rig 的陈述翻译成关于类型的陈述，能带来很多收获。下面是一张包含一些有趣条目的翻译表：

数字	类型
$0$	`Nothing`
$1$	`Unit` / `()`
$a + b$	`Either[A, B]`
$a \times b$	`(A, B)` 或 `case class Pair[A, B](a: A, b: B)`
$2 = 1 + 1$	`sealed trait Bool; case object True; case object False`
$1 + a$	`Option[A]`

列表类型很有趣，因为它被定义为一个方程的解。正在定义的类型出现在方程两边：

sealed trait List[+A]
case object Nil extends List[Nothing]
case class Cons[A](h: A, t: List[A]) extends List[A]

如果做通常的替换，并把 List[A] 换成 x，就得到方程：

x = 1 + a * x

无法用传统代数方法求解它，因为不能对类型做减法或除法。但可以尝试一系列替换：不断把右侧的 x 替换为 1 + a*x，并使用分配律。这会得到如下序列：

x = 1 + a*x
x = 1 + a*(1 + a*x) = 1 + a + a*a*x
x = 1 + a + a*a*(1 + a*x) = 1 + a + a*a + a*a*a*x
...
x = 1 + a + a*a + a*a*a + a*a*a*a...

最终得到一个积（tuple）的无限和，可以解释为：列表要么为空，即 1；要么是单元素，即 a；要么是 pair，即 a*a；要么是 triple，即 a*a*a；如此等等。嗯，这正是列表：一串 a！

列表还有更多内容。在学习函子和不动点之后，会回到列表和其他递归数据结构。

用符号变量解方程，这就是代数！这也是这些类型被称为代数数据类型的原因。

最后，还应该提到类型代数的一个非常重要的解释。注意，两个类型 A 和 B 的积必须同时包含一个 A 类型值和一个 B 类型值，这意味着两个类型都必须有居民。另一方面，两个类型的和包含一个 A 类型值或一个 B 类型值，因此只要其中一个有居民就足够。逻辑中的与和或也形成半环，并且它也可以映射到类型论：

逻辑	类型
false	`Nothing`
true	`Unit` / `()`
`a
`a && b`	`(A, B)`

这个类比还可以走得更深，它是逻辑与类型论之间 Curry-Howard 同构的基础。讨论函数类型时，我们会再回到它。

挑战

展示 Option[A] 与 Either[Unit, A] 之间的同构。
下面是在 Haskell 中定义的和类型：

data Shape = Circle Float
           | Rect Float Float

当想定义作用在 Shape 上的函数，例如 area，可以对两个构造器做模式匹配：

area :: Shape -> Float
area (Circle r) = pi * r * r
area (Rect d h) = d * h

在 C++ 或 Java 中把 Shape 实现为接口，并创建两个类：Circle 和 Rect。把 area 实现为虚函数。

继续上一个例子：我们可以轻易添加一个新函数 circ，计算 Shape 的周长。无需触碰 Shape 的定义即可做到：

circ :: Shape -> Float
circ (Circle r) = 2.0 * pi * r
circ (Rect d h) = 2.0 * (d + h)

把 circ 加到你的 C++ 或 Java 实现中。你必须触碰原代码的哪些部分？

继续：给 Shape 添加一个新形状 Square，并完成所有必要更新。在 Haskell 与 C++ 或 Java 中，你分别必须触碰哪些代码？即使你不是 Haskell 程序员，修改也应该相当明显。
证明 $a + a = 2 \times a$ 对类型成立（在同构意义下）。记住，根据翻译表，$2$ 对应 Bool。

6.1 积类型（Product Types）​

6.2 记录（Records）​

6.3 和类型（Sum Types）​

6.4 类型代数（Algebra of Types）​

挑战​

6.1 积类型（Product Types）

6.2 记录（Records）

6.3 和类型（Sum Types）

6.4 类型代数（Algebra of Types）

挑战