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!(
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.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.