A brief introduction to Haskell for math people.
2016-04-15
Do you like math? If so, check this out:
qs :: (Ord a) => [a] -> [a]
qs [] = []
qs (x:xs) = qs (filter (<=x) xs) ++ [x] ++ qs (filter (>x) xs)
This is Haskell. It's Quicksort implemented in two lines of code. (The first line is optional.) Lemme break it down.
qs [] = []
This is the base case.
It says that the result of qs applied to an empty list (alternatively qs, where the argument given to that formal parameter matches the pattern of an empty list) is the empty list.
You can think of this as the "base case".
qs (x:xs)
If the first pattern isn't matched, evaluation "falls through" to the second case, where the list is matched against the pattern (x:xs).
The function (:) is called "cons", for "list constructor".
All lists (which are implemented as linked lists in Haskell) can be viewed as successive applications of cons (with whatever values) to the empty list.
In fact, the list [1,2,3] is just syntactic sugar (a nice way of writing things) for 1:2:3:[], which evaluates to 1:2:[3] = 1:[2,3] = [1,2,3].
Anyway, any list (that isn't the empty list) can be viewed as some value x cons with some list xs.
Thus, the pattern (x:xs) allows us to deconstruct the list into its head and its tail.
Note that we use x as the pivot — in Quicksort, it's arbitrary which element is chosen as the pivot.
filter (>x) xs
filter is a higher-order function that takes a single-parameter function that returns a boolean value, and a list, and filters that list's elements by that predicate.
But why is (>x) a function?
In Haskell, all operators are functions (as they should be in any language), they're simply written in infix notation instead of prefix notation.
Infix functions can be surrounded by parens to be treated as a prefix function (useful for passing into other functions, like in this case), and (>x) is the function (>) partially applied with the value x.
All Haskell functions really take one argument — though it seems like they take multiple, it's all successive applications of arguments.
Thus (>x) is a single-argument function that will return a boolean result, and filter (>x) xs will return a list made up of all elements in xs which are >x.
qs (filter (<=x) xs) ++ [x] ++ qs (filter (>x) xs)
++ is list concatenation.
Simply enough, this sorts the list recursively.
qs :: (Ord a) => [a] -> [a]
This is the type declaration, which is optional.
It says that qs takes a list of some type a, and returns a list of some type a, where a is orderable.
This allows for really simple parametric polymorphism on types — qs will work on exactly the types it should.
Imagine how cool this gets when you add more restrictions!
TL;DR: If you like math, learn Haskell! The grumpy computer science students who whine about it are wrong. (Hot take.) It's like math on a computer and it's beautiful.
P.S. This is not the most efficient way to implement Quicksort, but it's an illustrative example.