8.1 代数类型系统

代数，我们以前都学过。比如，给定一个整数 x，我们可以对它执行一些数学运算，像加法、乘法之类的：

rust

x + 1
2 * x

我们还可以从中总结出一些规律，比如，任何一个整数与 0 之和等于它本身，任何数与 0 之积等于 0，任何一个整数与 1 之积等于它本身。用数学语言描述，可以这样写：

rust

0 + x = x
0 * x = 0
1 * x = x

在代数里面，我们的变量 x 代表的是某个集合内的数字，执行的操作一般是加减乘除一类的数学运算。而对应到代数类型系统上，我们可以把类型类比为代数中的变量，把类型之间的组合关系类比为代数中的数学运算。

我们可以做这样一个假定，一个类型所有取值的可能性叫作这个类型的“基数”（cardinality）。那么在此基础上，我们可以得出结论：最简单的类型unit()的基数就是1，它可能的取值范围只能是()。再比如说，bool 类型的基数就是 2，可能的取值范围有两个，分别是true和false。对于 i32 类型，它的取值范围是232，我们用 Cardinality(i32) 来代表 i32 的基数。

我们把多个类型组合到一起形成新的复合类型，这个新的类型就会有新的基数。如果两个类型的基数是一样的，那么我们可以说它们携带的信息量其实是一样的，我们也可以说它们是“同构”的。下面是一个典型的例子：

rust

type T1 = [i32; 2];
type T2 = (i32, i32);
struct T3(i32, i32);
struct T4 {
    field1: i32,
    field2: i32,
}

上面出现了四个类型，在实践中，它们不是同一个类型，是无法通用的。但是从数学上讲，这四个类型表达出来的信息量是完全一样的，它们都只能装下两个 i32 类型的成员。它们的基数都是 Cardinality(i32) * Cardinality(i32)。

tuple、struct、tuple struct 这几种类型，实质上是同样的内存布局，区别仅仅在于是否给类型及成员起了名字。这几个类型都可以类比为代数中的“求积”运算。没有成员的 tuple 类型，它的基数就是1。同理，任意一个空 struct 类型，基数也是 1，它们都可以类比为代数运算中的数字 1。

那么，如果 struct 里面有多个成员，比如：

rust

struct R {
    var1 : bool,
    var2 : bool,
}

R 类型包括了两个成员。分别是var1和var2。它的基数是：

rust

Cardinality(R) = Cardinality(var1) * Cardinality(var2) = 2 * 2 = 4

如果我们在结构体里面加入一个 unit 类型的成员：

rust

struct Prod {
    field1: i32,
    field2: (),
}

这个field2成员实际上对这个结构体没有带来什么贡献，它并没有带来额外的信息量：

rust

Cardinality(Prod) = Cardinality(field1) * 1 = Cardinality(i32)

对于数组类型，可以对应为每个成员类型都相同的 tuple 类型（或者 struct 是一样的）。用数学公式类比，则比较像乘方运算。

从函数式程序员的角度看，结构体和枚举也称为代数数据类型（Algebraic Data Type， ADT），因为可以使用代数规则来表示它们能够表达的值的取值区间。例如，枚举被称为求和类型，是因为它可以容纳的值的范围基本上是其变体的取值范围的总和；而结构体被称为乘积类型，是因为它的取值区间是其每个字段取值区间的笛卡儿积。在谈到它们时，我们有时会将它们称为 ADT。

Rust 中的 enum 类型就相当于代数中的“求和”运算。比如，某个类型可以代表“东南西北”四个方向，我们可以如下设计：

rust

enum Direction {
    North, East, South, West
}

它可能的取值范围是四种可能性，它的基数就是4。我们可以把它看作是四个无成员的 struct 的“或”关系。

rust

Cardinality(Direction) = Cardinality(North) + Cardinality(East)
                                   + Cardinality(South) + Cardinality(West)
                                   = 4

实际上，我们甚至可以将内置的 bool 类型定义为一个标准库中的 enum：

rust

enum Bool { True, False }

这样定义的 Bool 类型和目前的内置 bool 类型表达能力上是没有什么差别的。

标准库中有一个极其常见的类型叫作Option<T>，它是这么定义的：

rust

enum Option<T> {
    None,
    Some(T),
}

由于它实在是太常用，标准库将 Option 以及它的成员 Some、None 都加入到了 Prelude 中，用户甚至不需要use语句声明就可以直接使用。其中 T 是一个泛型参数，在使用的时候可以被替换为实际类型。例如，Option<i32>类型实际上等同于：

rust

enum Option<i32> {
    Some(i32),
    None
}

因此它的基数是：

rust

Cardinality(Option<i32>) = Cardinality(i32) + 1

同理，我们可以得出一个空的 enum，基数是 0。

通过上文中的示例，我们可以为“代数类型系统”和“代数”建立一个直观的类比关系。

空的 enum 可以类比为数字0；
unit 类型或者空结构体可以类比为数字1；
enum 类型可以类比为代数运算中的求和；
tuple、struct 可以类比为代数运算中的求积；
数组可以类比为代数运算中的乘方。

同理，我们还能继续做更多的类比。

enum 类型的每个成员还允许包含更多关联数据：

rust

enum Message {
    Quit,
    ChangeColor(i32, i32, i32),
    Move { x: i32, y: i32 }
}

这就好比 enum 的每个成员还可以是 tuple 或者 struct。类比到代数，相当于加法乘法混合运算：

rust

Cardinality(Message) = Cardinality(Quit) + Cardinality(ChangeColor) + Cardinality(Move)
          = 1 + Cardinality(i32)^3 + Cardinality(i32)^2
// 此处用 ^ 代表乘方，不是异或

加法具有交换率，同理，enum 中的成员交换位置，也不会影响它的表达能力；乘法具有交换率，同理，struct 中的成员交换位置，也不影响它的表达能力。

乘法具有结合律：x * (y * z) = (x * y) * z，同理，对于 tuple 类型(A, (B, C))和((A, B), C)的表达能力是一样的。

继续列下去，我们还能做出更多的类比，这是一个非常庞大的话题。读者可以到网上搜索更多、更详尽的关于 ADT 的讲解文章.

8.1 代数类型系统 ​

8.1 代数类型系统