I’ve recently started to learn Haskell (used it at Uni over a decade ago, but I’m trying to actually appreciate it this time :)). Here is an example I found when working through the recursion chapter of the excellent Learn you a Haskell tutorial. Yes, I know this is a very corny example, but the fact I was able to figure it out just from the algorithm description in the tutorial, despite being a Haskell newbie, really impressed the beauty of the language upon me.

Remember quicksort? Picking a pivot, then putting it in the middle of the sorted smaller elements and sorted larger elements? Typically you end up with a wad of procedural code, such as this fairly typical C# example.

In Haskell, you work more with describing what something is, rather than how it works. So we end up with something like this:

quicksort :: (Ord a) => [a] -> [a]
quicksort [] = []
quicksort (x:xs) = smaller_sorted ++ [x] ++ larger_sorted
    where smaller_sorted = quicksort [y | y <- xs, y <= x]
          larger_sorted = quicksort [y | y <- xs, y > x]

The first line is defining the type of the function, it takes a list of orderable types and returns a list of those types. The second line is our recursion edge case: sorting an empty list returns an empty list.

The third line is the definition of our algorithm. Given (x:xs), the list head (x) and tail (xs), we put the head between the sorted list of everything smaller and the sorted list of everything larger.

The where clause has our recursive calls using list comprehensions. The line [y | y <- xs, y<=x] selects the elements of the tail (xs) which are less that our pivot (x).

Neat huh?

We can also try and bring the functional-style with us to C#, but you pretty quickly start missing pattern matching, and built-in list syntax like head, tail and concatenation. In many cases (like this one) the C# compiler also won’t be able to get you the tail call elimination possible in functional languages like Haskell, which tends to make recursive implementations less desirable.

public static IEnumerable<int> QuickSort(IEnumerable<int> elements) {
    if (!elements.Any()) return new int[0];

    var head = elements.First();
    var tail = elements.Skip(1);

    var sortedSmaller = tail.Where(x => x <= head);
    var sortedLarger = tail.Where(x => x > head);

    return QuickSort(sortedSmaller).Concat(new [] {head}).Concat(QuickSort(sortedLarger)); 
}

This is simpler than the more procedural version, but not as simple as the Haskell version. And we still have to stay concious of differences such as how tail recursion is handled over different platforms which can have a huge impact on performance. With that in mind though, it’s neat enough for me to keep digging into functional programming, as even if I don’t end up doing much with pure functional languages the techniques can provide some very interesting alternative ways of solving problems in any language.