Haskell in less than five minutes
I have been playing with Haskell and the Glasgow Haskell Compiler today, refreshing my memory of the language. After spending the last two years coding mostly in C++ and Python with a smattering of C it is a rather pleasant experience. Note: the simplest way to try out these examples is with ghci or hugs; simply place the code in file.hs and load it from within the interpreter with :load file.hs and then call the function as normal.
To start with a simple example of the language, the following calculates the nth Fibonacci number:
fib n | n < 2 = 1
| n >= 2 = fib(n-1) + fib(n-2)
The boolean guards n < 2 and n >= 2 determine what is evaluated. We can then map this function onto the natural numbers using:
fibs = map fib [1..]
and subsequently get the first 10 Fibonacci numbers with take 10 fibs which returns the expected list. Higher order functions such as map are simple to define, such as:
map f xs = [f x | x <- xs]
The expression on the right of the equals is an example of list comprehension. The generator x <- xs takes each x from the input list xs in turn and the expression f x is applied forming a new list. Multiple generators can be used, for example the expression [(a,b) | a <- [1..3], b <- ['a', 'b']] evaluates to the list
[(1,'a'),(1,'b'),(2,'a'),(2,'b'),(3,'a'),(3,'b')]
Making use of list comprehension gives us the rather lovely Haskell rendering of the quicksort algorithm:
qsort [] = []
qsort (x:xs) = qsort [y | y <- xs, y < x] ++ [x]
++ qsort [y | y <- xs, y >= x]
Simple, concise and, in comparison to C or the pseudo code rendition in the textbooks I have to hand, very easy to understand. When supplied with an empty list the qsort function returns an empty list. When given a list (consisting of the first element, x, and the remainder of the list xs) we use the first element as the pivot and apply qsort recursively to all the elements less than x, concatenate that list, using the ++ operator, with [x] and then concatenate that with the result of qsort applied to all elements greater than x. We could even make this slightly shorter by replacing [y | y <- xs, y < x] with filter (< x) xs. Of course I have glossed over the fact that using the head of the list as the pivot is not a very good idea but it’s still a very aesthetically pleasing piece of code. 
