The first time I saw this quicksort in Haskell was an eye opening moment,
qsort [] = [] qsort (x:xs) = qsort (filter (< x) xs) ++ [x] ++ qsort (filter (>= x) xs)The first line reads: “When you sort an empty list (
[]
), the result is another empty list”. The second line reads: “To sort a list whose first element is namedx
and the rest of which is namedxs
, sort the elements ofxs
that are less thanx
, sort the elements ofxs
that are greater than or equal tox
, and concatenate (++
) the results, withx
sandwiched in the middle.”
The code is so concise, yet clear (even with cryptic variable names like xs
). The day my professor wrote it on the whiteboard was the first time I internalized that there might be something good about the alien world of functional programming.
The biggest revelation to me was, filter (< x) xs
. It’s amazing that (< x)
builds a temporary, unnamed, function equivalent to C++,
bool lessThanX(AnyOrderedType y){ return y < X; } //plus the definition of X somewhere...
Building a function! It’s still profound stuff to me. And clearly it really uses fewer lines of code. Amazingly, using list comprehension syntax is not more concise,
qsort (x:xs) = qsort [i | i <- xs, i < x] ++ [x] ++ qsort [i | i <- xs, i <= x]
compared to the original,
qsort (x:xs) = qsort (filter (< x) xs) ++ [x] ++ qsort (filter (>= x) xs)
I hope this is an ah-ah moment for someone else too. I’d love to know what made you interested in functional programming; or if you know of a more elegant quicksort implementation.