Thanks to Haskell, I understand QUICKSORT!!

Oh quicksort, let me count the number of times I have learned thee.
1: Grade 11 Comp Sci
2: First year university
3: Second year university

Every time I restudied quicksort, I thought I had it. Then, no less than 30 minutes after the exam, GONE. I swear I have the memory of a bag of sand.

I have some very smart friends, and some of them work with me. One person in particular is into programming languages. This week, he mentioned Haskell. *sigh*, I thought, here comes another conversation where the other guys will talk and nod about something of which I know NOTHING. It's very humbling. So today I hit the StumbleUpon button on FireFox, and up comes Haskell. So I figure, it's a sign - time to read.


The first example, which of course highlights Haskell's strengths and exposes one of C's weaknesses, is quicksort. The idea behind quicksort is: pick an element from the array (the pivot), partition the remaining elements into those greater than and less than this pivot, and recursively sort the partitions. I don't know why that was so hard for me to remember, but there it is. Two solutions can be found at About Haskell, and I will paracode the Haskell solution here:

qsort []  = []
qsort (head:restOfList) =
 qsort elementsLT_head ++ [head] ++ qsort elementsGE_head
  where
   elementsLT_head = [ y | y <- restOfList, y < head ]
   elementsGE_head = [ y | y <- restOfList, y >= head ]

Six lines. Six. Wow. You can go see About Haskell if you really want to see the C solution, so I'm not going to list it here. Suffice to say that it's a lot longer and harder to understand. I may be biased because I love math (lines 6 and 7 are purposely designed to mimic mathematical set notation), but I think this is a beautiful way to express quicksort.

Explanation:
Line 1: The result of qsort on an empty list is an empty list. Yay.
Line 2: The result of qsort on a list of 1 or more elements, where the first element is called head and the rest of the list is called restOfList happens in the following way.
Line 3: qsort elementsLT_head, then insert head, then insert the qsort elementsGE_head.
Line 4: Where the following definitions apply:
Line 5: elementsLT_head is a list of all the elements y such that y is taken from restOfList, and y is less than head.
Line 6: elementsGE_head is a list of all the elements y such that y is taken from restOfList, and y is greater than or equal to head.

There are all sorts of pros and cons and what not, but the fact of the matter is that I re-understood quicksort as soon as I read this code, whereas the C code was far more cryptic. There are many places where you want to use C, or Perl, or Java, or InsertLanguageHere. This is not an argument for language superiority. To me, the biggest advantage of knowing multiple languages is knowing the right tool for the right job. Not to mention that you begin to see better ways of doing things in all the languages you use. Next time I'm asked to explain quicksort, this solution will come to mind, then I can write whatever code I need.



P.S. What are we sorting in the Haskell code? Any object or primitive that can be compared using <>=. Yay polymorphism!