在有健忘症的情况下用 Rust 写快速排序

一觉醒来，我忘记了 Rust 中的绝大部分关键字

September 26, 2024

#Rust

一觉醒来，我忘记了 Rust 中的绝大部分关键字。我忘记了所有的整数类型，忘记了它们之间的大小关系，忘记了数组，忘记了布尔类型，忘记了 if，忘记了循环…我还能写出快速排序算法吗？

首先定义自然数：

1#[derive(Debug, Clone)]
2enum Nat {
3    Zero,
4    Succ(Box<Nat>)
5}

接着定义自然数列表：

1#[derive(Debug, Clone)]
2enum List {
3    Nil,
4    Cons(Nat, Box<List>)
5}

排序需要知道自然数之间的大小关系。定义布尔类型：

1#[derive(Debug)]
2enum Bool {
3    True,
4    False
5}

从而可以定义自然数上的序：

 1fn le(a: &Nat, b:&Nat) -> Bool {
 2    match (a, b) {
 3        (Nat::Zero, _) => Bool::True,
 4        (_, Nat::Zero) => Bool::False,
 5        (Nat::Succ(a), Nat::Succ(b)) => le(a, b)
 6    }
 7}
 8
 9fn gt(a: &Nat, b:&Nat) -> Bool {
10    match (a, b) {
11        (Nat::Zero, Nat::Zero) => Bool::False,
12        (Nat::Zero, _) => Bool::False,
13        (_, Nat::Zero) => Bool::True,
14        (Nat::Succ(a), Nat::Succ(b)) => gt(a, b)
15    }
16}

接着定义列表上的常用操作。由于模式匹配，我甚至不需要 car 和 cdr：

 1fn append(a: &List, b: &List) -> List {
 2    match a {
 3        List::Nil => b.clone(),
 4        List::Cons(n, l) => List::Cons(n.clone(), Box::new(append(l, b)))
 5    }
 6}
 7
 8fn filter(a: &List, f: &dyn Fn(&Nat) -> Bool) -> List {
 9    match a {
10        List::Nil => List::Nil,
11        List::Cons(n, l) => {
12            match f(n) {
13                Bool::True => List::Cons(n.clone(), Box::new(filter(l, f))),
14                Bool::False => filter(l, f)
15            }
16        }
17    }
18}

终于，我能写出快速排序了：

 1fn quick_sort(a: &List) -> List {
 2    match a {
 3        List::Nil => List::Nil,
 4        List::Cons(pivot, lst) => {
 5            let f = |x: &Nat| le(x, pivot);
 6            let g = |x: &Nat| gt(x, pivot);
 7            let l = filter(lst, &f);
 8            let r = filter(lst, &g);
 9            let sorted_l = quick_sort(&l);
10            let sorted_r = quick_sort(&r);
11            append(&sorted_l, &List::Cons(pivot.clone(), Box::new(sorted_r)))
12        }
13    }
14}

这时候，我突然想起了什么是 u32，什么是 Vec。写一段互相转换的代码：

 1fn u32_to_nat(n: u32) -> Nat {
 2    match n {
 3        0 => Nat::Zero,
 4        _ => Nat::Succ(Box::new(u32_to_nat(n - 1)))
 5    }
 6}
 7
 8fn nat_to_32(n: Nat) -> u32 {
 9    match n {
10        Nat::Zero => 0,
11        Nat::Succ(prev) => nat_to_32(*prev) + 1
12    }
13}
14
15fn array_to_list(a: &[u32]) -> List {
16    match a {
17        [] => List::Nil,
18        [x, xs @ ..] => List::Cons(u32_to_nat(*x), Box::new(array_to_list(xs)))
19    }
20}
21
22fn list_to_array(l: &List) -> Vec<u32> {
23    match l {
24        List::Nil => vec![],
25        List::Cons(n, l) => {
26            let mut v = list_to_array(l);
27            v.insert(0, nat_to_32(n.clone()));
28            v
29        }
30    }
31}

测试一下我们的快速排序吧！

1fn main() {
2    let l = vec![5, 4, 3, 2, 1, 0, 1, 2, 3];
3    let sorted = quick_sort(&array_to_list(&l));
4    println!("{:?}", list_to_array(&sorted));
5}

    Running `target/debug/forgot`
[0, 1, 1, 2, 2, 3, 3, 4, 5]