jlm-blog
~jlm

26-Jul-2006

Haskell vs. C readability stawman

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?

19-Jul-2006

Latest thoughts

Filed under: philosophy — jlm @ 13:37

Why is it that things we find very easy to do in our minds (process language, identify people, etc.) are things we can’t get machines to do, but things we find very cumbersome (arithmetic, data manipulation, etc.) we can make machines to do extremely well?

This dilemma, that stuff we can do easily doesn’t imply easy automatability, leads to all kinds of optimism on how human-like computers and other machines are. So what’s the root of it? I think it’s because we don’t know how to understand language, identify faces, etc. We do it, but we don’t know how! For all of recorded history, we’ve been refining mathematics, improving manufacturing processes, so we know in fine detail how to do arithmetic, how to weave cloth, etc. and we teach it to the next generation, write it down in books — whereas we don’t teach our children how to understand language, how to identify their parents and friends, these are mysteries that our brains do for us without being taught, processes which we have no visibility into the internals of. We can make a step by step guide to how to multiply numbers, and make a machine to do it. But we don’t have step-by-step guides to language. The steps are inside our brains and we get only the output. We don’t understand how we understand language, and so find it impossible to make a machine that does it.


Update: For the ~0 of you who’ll read this, I’ve just learned that this is called Moravec’s paradox.

Powered by WordPress