Rust 中的冒泡排序：第一部分-技术圈

在本系列文章中，我们将使用 Rust 的类型系统（图灵完备^[1]）在类型级别上实现冒泡排序算法。

我希望通过这些文章帮助你了解类型级别编程的感觉，尝试弄清楚所有这些“特征（traits）”和“实现”的背后是什么，并展示 Rust 的类型系统的能力。

在开始之前，你可能需要对 Rust 编程语言有一个基本的了解（尽管对一些像 Haskell 或 Scala 这样的 FP 语言的了解也应该足够好）。

基本上，类型级（type level）编程允许我们将计算带到编译器推断类型之间关系的编译阶段，而不是在程序运行时计算值。

1、我们如何用类型表达条件逻辑？

我们将使用特征的力量。Traits 就像 C#/Java 中的接口，除了你可以为现有类型实现 Trait（因此思维方式不是“一个类型实现此接口”而是“有一个类型的此 trait 实现”）。

结合泛型，它使我们能够为单个类型编写多个 trait 实现，只需使用不同的泛型类型参数，允许编译器决定必须为特定情况选择哪种实现。我们称之为 multidispatch^[2]。

稍后我们将在实践中看到这一点，我们先看数字。

2、数字

我们如何表示类型级别的数字？我们当然可以为每个可能的自然数声明很多结构体，struct Num1; struct Num2; 等，但这肯定不合适，（实际上是不可能的，因为有无限数量的自然数）。我们将使用 Peano 数字编码^[3]。

简单地说，自然数就是从 0 到无穷大的所有非负数。1 在 0 之后，2 在 1 之后，所以我们可以说数字 1 是 0 的后继者，而数字 2 是 0 的后继者的后继者。这就是 Peano 数字编码的工作原理！

在 Rust 代码中，它看起来是这样的：

struct Zero;
struct Succ(N);

例如，为了表示数字 4，我们将这样写：

Succ>>>

3、数字比较

在排序的上下文中关于数字的下一个重要的事情是比较。

Peano 数字比较基于以下规则：

对于每一个 X，0 <= X
Succ(X) >= Succ(Y) if X >= Y

例如，让我们尝试借助上述规则计算 2 是否小于 3。2 小于 3 吗？我们不能肯定回答，根据第二条规则我们需要比较他们的上一个数。1 小于 2 吗？再说一次，我们不能判定。0 小于 1 吗？是的，根据第一条规则是正确的，因此我们证明了 2 小于 3。

我们开始编码。

我们将使用特征和相关类型。看看这个代码片段：

trait Compare {
    type Output;
}

此特征将针对自然数实现。

此外，我们将看到 multidispatch 的实际应用。

我们为第一个比较规则编写一个实现：

// Some zero-sized types for representing equality
struct EQ;
struct LT;
struct GT;

// we've got to impls since we have no "less or equal to" type
impl Compare for Zero {
    type Output = EQ;
}

impl Compare> for Zero {
    type Output = LT:
}