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

在本系列文章中，我們將使用 Rust 的類型系統(tǒng)（圖靈完備^[1]）在類型級別上實(shí)現(xiàn)冒泡排序算法。

我希望通過這些文章幫助你了解類型級別編程的感覺，嘗試弄清楚所有這些“特征（traits）”和“實(shí)現(xiàn)”的背后是什么，并展示 Rust 的類型系統(tǒng)的能力。

在開始之前，你可能需要對 Rust 編程語言有一個基本的了解（盡管對一些像 Haskell 或 Scala 這樣的 FP 語言的了解也應(yīng)該足夠好）。

基本上，類型級（type level）編程允許我們將計(jì)算帶到編譯器推斷類型之間關(guān)系的編譯階段，而不是在程序運(yùn)行時計(jì)算值。

1、我們?nèi)绾斡妙愋捅磉_(dá)條件邏輯？

我們將使用特征的力量。Traits 就像 C#/Java 中的接口，除了你可以為現(xiàn)有類型實(shí)現(xiàn) Trait（因此思維方式不是“一個類型實(shí)現(xiàn)此接口”而是“有一個類型的此 trait 實(shí)現(xiàn)”）。

結(jié)合泛型，它使我們能夠?yàn)閱蝹€類型編寫多個 trait 實(shí)現(xiàn)，只需使用不同的泛型類型參數(shù)，允許編譯器決定必須為特定情況選擇哪種實(shí)現(xiàn)。我們稱之為 multidispatch^[2]。

稍后我們將在實(shí)踐中看到這一點(diǎn)，我們先看數(shù)字。

2、數(shù)字

我們?nèi)绾伪硎绢愋图墑e的數(shù)字？我們當(dāng)然可以為每個可能的自然數(shù)聲明很多結(jié)構(gòu)體，struct Num1; struct Num2; 等，但這肯定不合適，（實(shí)際上是不可能的，因?yàn)橛袩o限數(shù)量的自然數(shù)）。我們將使用 Peano 數(shù)字編碼^[3]。

簡單地說，自然數(shù)就是從 0 到無窮大的所有非負(fù)數(shù)。1 在 0 之后，2 在 1 之后，所以我們可以說數(shù)字 1 是 0 的后繼者，而數(shù)字 2 是 0 的后繼者的后繼者。這就是 Peano 數(shù)字編碼的工作原理！

在 Rust 代碼中，它看起來是這樣的：

struct?Zero;
struct?Succ(N);

例如，為了表示數(shù)字 4，我們將這樣寫：

Succ>>>

3、數(shù)字比較

在排序的上下文中關(guān)于數(shù)字的下一個重要的事情是比較。

Peano 數(shù)字比較基于以下規(guī)則：

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

例如，讓我們嘗試借助上述規(guī)則計(jì)算 2 是否小于 3。2 小于 3 嗎？我們不能肯定回答，根據(jù)第二條規(guī)則我們需要比較他們的上一個數(shù)。1 小于 2 嗎？再說一次，我們不能判定。0 小于 1 嗎？是的，根據(jù)第一條規(guī)則是正確的，因此我們證明了 2 小于 3。

我們開始編碼。

我們將使用特征和相關(guān)類型?？纯催@個代碼片段：

trait?Compare?{
????type?Output;
}

此特征將針對自然數(shù)實(shí)現(xiàn)。

此外，我們將看到 multidispatch 的實(shí)際應(yīng)用。

我們?yōu)榈谝粋€比較規(guī)則編寫一個實(shí)現(xiàn)：

//?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:
}

這些 impl 的含義是 Comparing Zero with Zero produces EQ 和 Comparing Zero with Succ(A) produces LT。如你所見，實(shí)現(xiàn)特征的類型用作比較的左值，類型參數(shù)Rhs是右值。

為了調(diào)用實(shí)現(xiàn)，我們需要編寫：

as?Compare>::Output

這意味著“獲取特征 Compare 的實(shí)現(xiàn)，并從中獲取相關(guān)的輸出”。

編譯器推斷出我們需要的確切類型。我們剛剛進(jìn)行了類型級別的計(jì)算！

不過，>::Output 有點(diǎn)尷尬（想象一下，如果甚至有嵌套調(diào)用），我們可以使用類型別名來簡化它：

type?Cmp?=?as?Compare>::Output;

這讓代碼更具可讀性，并允許我們將特征視為僅對類型進(jìn)行操作的函數(shù)。泛型類型參數(shù) ( Lhs, Rhs) 是函數(shù)的參數(shù)，關(guān)聯(lián)類型是函數(shù)返回的 ( Output)。

請注意，我沒有編寫用于比較 Succ 和 Succ 的實(shí)現(xiàn)。這作為你的家庭作業(yè)（你可以在代碼庫中看到解決方案，鏈接在下面）。提示：它涉及遞歸。

感謝您閱讀本文，這就是今天的全部內(nèi)容！在本系列的下一部分中，我將討論類型級列表。

該項(xiàng)目的源代碼：

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

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

參考資料