Rust 中的冒泡排序：第一部分

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

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

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

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

Some memes

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>(N);

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

Succ<Succ<Succ<Succ<Zero>>>>

3、数字比较

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

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

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

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

我们开始编码。

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

trait Compare<Rhs> {
    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<Zero> for Zero {
    type Output = EQ;
}

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

这些 impl 的含义是 Comparing Zero with Zero produces EQ 和 Comparing Zero with Succ(A) produces LT。如你所见，实现特征的类型用作比较的左值，类型参数Rhs是右值。

为了调用实现，我们需要编写：

<Zero as Compare<Zero>>::Output

这意味着“获取特征 Compare<Zero> 的实现，并从中获取相关的输出”。

Inferred type 编译器推断出我们需要的确切类型。我们刚刚进行了类型级别的计算！

不过，<Zero as Compare<Zero>>::Output 有点尴尬（想象一下，如果甚至有嵌套调用），我们可以使用类型别名来简化它：

type Cmp<Lhs, Rhs> = <Lhs as Compare<Rhs>>::Output;

这让代码更具可读性，并允许我们将特征视为仅对类型进行操作的函数。泛型类型参数 ( Lhs, Rhs) 是函数的参数，关联类型是函数返回的 ( Output)。

请注意，我没有编写用于比较 Succ<A> 和 Succ<B> 的实现。这作为你的家庭作业（你可以在代码库中看到解决方案，链接在下面）。提示：它涉及递归。

感谢您阅读本文，这就是今天的全部内容！在本系列的下一部分中，我将讨论类型级列表。

该项目的源代码：

https://github.com/thedenisnikulin/type-level-sort

原文链接：https://dev.to/thedenisnikulin/type-level-bubble-sort-in-rust-part-1-3mcb

参考资料

[1]图灵完备: https://sdleffler.github.io/RustTypeSystemTuringComplete/

[2]multidispatch: http://smallcultfollowing.com/babysteps/blog/2014/09/30/multi-and-conditional-dispatch-in-traits/

[3]Peano 数字编码: https://en.wikipedia.org/wiki/Peano_axioms