Functional programming in Rust?

Graham Hutton's Functional Programming class is entirely online this semester and he's making the videos available on Youtube!

The course is being taught with Haskell. I just finished week 1 and I decided to try the quicksort example in Rust. I started by putting the Haskell code in a comment at the top of my file for reference.

// -- qsort :: Ord a => [a] -> [a]
// qsort [] = []
// qsort (x:xs) = qsort ys ++ [x] ++ qsort zs
//          where
//              ys = [a | a <- xs, a <= x]
//              zs = [a | a <- xs, a > x]

Then I started writing the Rust version. When I was done, I realized I could used Haskell's literate programming support to make it work in Haskell as well! I changed the line comments to a block comment and then added the birds to the Haskell code lines. Then I made a symbolic link from qsort.lhs to src/main.rs. Now cargo run runs the Rust code and ghci qsort.lhs runs the Haskell code!

fn main() {
    assert_eq!(qsort(&[3, 1, 4, 2]), vec![1, 2, 3, 4]);

    assert_eq!(
        qsort(&"Haskell".chars().collect::<Vec<_>>()),
        vec!['H', 'a', 'e', 'k', 'l', 'l', 's']
    );

    dbg!(qsort(&"Rust".chars().collect::<Vec<_>>()),);

    dbg!(qsort(&["foo", "bar", "baz"]));

    // Strings have Clone, but not Copy.
    dbg!(qsort(&[
        "foo".to_string(),
        "bar".to_string(),
        "baz".to_string(),
    ]));
}

/*

> -- qsort :: Ord a => [a] -> [a]
> qsort [] = []
> qsort (x:xs) = qsort ys ++ [x] ++ qsort zs
>          where
>              ys = [a | a <- xs, a <= x]
>              zs = [a | a <- xs, a > x]

*/
fn qsort<T: Ord + Clone>(s: &[T]) -> Vec<T> {
    match s.len() {
        0 => Vec::new(),
        _ => {
            let x = s[0].clone();
            let xs = &s[1..];

            let ys = xs.iter().cloned().filter(|a| *a <= x).collect::<Vec<T>>();
            let zs = xs.iter().cloned().filter(|a| *a > x).collect::<Vec<T>>();

            [qsort(&ys[..]), vec![x], qsort(&zs[..])].concat()
        }
    }
}

Please note that I am just playing around here for comparison purposes. Rust is not a proper functional programming language. In one of the videos, Hutton gives a really nice definition of a functional programming language: one that supports and encourages the functional style. Like many languages these days, Rust has some support for functional programming, but it doesn't really encourage it.

This seems similar to F# describing itself as a functional-first programming language. As the years go by, C# adds more and more support for the functional style, but it will never be functional-first.

Anyway, I just wanted to see how similar it would be if I coded up more or less the same algorithm from the Haskell class in Rust. If you actually need a quicksort in Rust, you should probably use sort_unstable in the standard library.