## 26-Jul-2006

Filed under: programming — jlm @ 17:03

Every time I think about learning Haskell, I head over to haskell.org, read the Introduction link, and am offended by the astoundingly absurd quicksort example they provide for its superiority over C and leave in disgust.

First, let’s take a look at their Haskell implementation of quicksort:

``    qsort (x:xs) = qsort (filter (< x) xs) ++ [x] ++ qsort (filter (>= x) xs)``

Wait one second here! Something’s fishy. At the bottom, the basic operation quicksort does is a swap. Where’re the swaps? I don’t see any swapping. I do see splicing though; quicksort doesn’t splice. This isn’t quicksort; quicksort is an in-place sort, this thing here is a list sort. This is not just an implementation detail, it’s fundamental to what quicksort is. It doesn’t splice, it makes swaps. If you have some linked lists, you sort them with something like mergesort. But for arrays, you can’t beat quicksort.

Now, we can start on the C implementation they provide…

``    qsort( a, lo, hi ) int a[], hi, lo;``

Huh?

If you’re a C programmer, your first impression is to boggle at this syntax. It’s been deprecated for 17 years, and most C programmers nowadays probably don’t even recognize it. What moth-eaten tome did they dig this out of? Variables of `hi` and `lo` and `h` and `l`? `l+1` and `l-1` as expressions? That’s the kind of thing you see at the IOCCC. Let’s choose an actual decent example of quicksort for a more honest comparison, like the one from K&R2:

``````
/* qsort:  sort v[left]...v[right] into increasing order */
void qsort(int v[], int left, int right)
{
int i, last;
void swap(int v[], int i, int j);

if (left >= right)    /* do nothing if array contains */
return;           /* fewer than two elements */
swap(v, left, (left + right)/2); /* move partition elem */
last = left;                     /* to v[0] */
for (i = left+1; i <= right; i++)   /* partition */
if (v[i] < v[left])
swap(v, ++last, i);
swap(v, left, last);        /* restore partition elem */
qsort(v, left, last-1);
qsort(v, last+1, right);
}
``````

Much more readable than that strawman example they have on the Haskell intro page!
But it’s still an apples-to-oranges comparison, because the C implementation is doing a real quicksort, and the Haskell is doing a list sort. Show me a real in-place quicksort in Haskell: It’ll turn out looking almost like the implementation in K&R, I wager.

Now, Haskell was written by people who know their computer science. They know all about quicksort, they know their example is comparing different algorithms, and they can write better C code than what they use. Why do they have to be dishonest when promoting the virtues of Haskell, hmm?

1. Because Haskell does not include variable assignment an in-place sort is impossible in Haskell.

According to this page http://en.wikipedia.org/wiki/Quicksort#The_algorithm the in-place aspect of the sort is not part of the algorithm but is a possible implementation optimization.

I agree that the old style C declaration is off puttingly out of date.

Comment by fenric — 27-Jul-2006 @ 03:24

2. C.A.R. Hoare’s description of his new sorting algorithm said “The entire contents of the store may be sorted, since no extra space is required. The average number of comparisons made is 2(M-N) ln(N-M), and the average number of exchanges is one sixth this amount.” So he was clearly thinking about sorting in-place with swaps. But I think the most important aspect is the problem domain: Quicksort is the best we have for sorting arrays in place, but it’s not that stellar when adapted to sort linked lists. Sure it makes a for a nice compact implementation in Haskell that way, but I think the main thing that highlights is merely Haskell’s list operators and built in handling of lists. Surely haskell.org wants to claim more than Haskell is a list based language so handles lists pithily? Might as well use Lisp then!

Even if you call what the Haskell implementation does “a” quicksort, it’s not the same quicksort the C is doing. You can do assignment in Haskell, just that involves using a big scary monad that’ll frighten away the newbies (doubtful) and will make the Haskell implementation look too much like the C they’re comparing it against (the real reason, methinks). If you’re going to compare them honestly, you need to implement the same algorithm, but that doesn’t serve their purpose if it shows Haskell being as expressive as C.

Comment by jlm — 27-Jul-2006 @ 09:04

3. Your argument is flawed becose in the Haskell world there isn’t the concept of “place”! The relation between “list” and “arrays” in Haskell is somewhat similar to the relation between “variable” and “register” in C (i.e there is a “register” keyword but there is not an exact definition of his effects).

Comment by no_name — 16-Nov-2006 @ 10:28