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.