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

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

September 26, 2024

#Rust

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

首先定义自然数：

#[derive(Debug, Clone)]
enum Nat {
    Zero,
    Succ(Box<Nat>)
}

接着定义自然数列表：

#[derive(Debug, Clone)]
enum List {
    Nil,
    Cons(Nat, Box<List>)
}

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

#[derive(Debug)]
enum Bool {
    True,
    False
}

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

fn le(a: &Nat, b:&Nat) -> Bool {
    match (a, b) {
        (Nat::Zero, _) => Bool::True,
        (_, Nat::Zero) => Bool::False,
        (Nat::Succ(a), Nat::Succ(b)) => le(a, b)
    }
}

fn gt(a: &Nat, b:&Nat) -> Bool {
    match (a, b) {
        (Nat::Zero, Nat::Zero) => Bool::False,
        (Nat::Zero, _) => Bool::False,
        (_, Nat::Zero) => Bool::True,
        (Nat::Succ(a), Nat::Succ(b)) => gt(a, b)
    }
}

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

fn append(a: &List, b: &List) -> List {
    match a {
        List::Nil => b.clone(),
        List::Cons(n, l) => List::Cons(n.clone(), Box::new(append(l, b)))
    }
}

fn filter(a: &List, f: &dyn Fn(&Nat) -> Bool) -> List {
    match a {
        List::Nil => List::Nil,
        List::Cons(n, l) => {
            match f(n) {
                Bool::True => List::Cons(n.clone(), Box::new(filter(l, f))),
                Bool::False => filter(l, f)
            }
        }
    }
}

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

fn quick_sort(a: &List) -> List {
    match a {
        List::Nil => List::Nil,
        List::Cons(pivot, lst) => {
            let f = |x: &Nat| le(x, pivot);
            let g = |x: &Nat| gt(x, pivot);
            let l = filter(lst, &f);
            let r = filter(lst, &g);
            let sorted_l = quick_sort(&l);
            let sorted_r = quick_sort(&r);
            append(&sorted_l, &List::Cons(pivot.clone(), Box::new(sorted_r)))
        }
    }
}

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

fn u32_to_nat(n: u32) -> Nat {
    match n {
        0 => Nat::Zero,
        _ => Nat::Succ(Box::new(u32_to_nat(n - 1)))
    }
}

fn nat_to_32(n: Nat) -> u32 {
    match n {
        Nat::Zero => 0,
        Nat::Succ(prev) => nat_to_32(*prev) + 1
    }
}

fn array_to_list(a: &[u32]) -> List {
    match a {
        [] => List::Nil,
        [x, xs @ ..] => List::Cons(u32_to_nat(*x), Box::new(array_to_list(xs)))
    }
}

fn list_to_array(l: &List) -> Vec<u32> {
    match l {
        List::Nil => vec![],
        List::Cons(n, l) => {
            let mut v = list_to_array(l);
            v.insert(0, nat_to_32(n.clone()));
            v
        }
    }
}

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

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

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