[plug] qsort

[The Thought Assassin]

On Mon, 10 Jun 2002, Simon Scott wrote:
> > On Mon, Jun 10, 2002 at 01:34:55PM +0800, The Thought Assassin wrote:
> > > Now that is a thing of beauty.
> I just wish I understood a single line of that code.

It's easy. Let me explain it to you:


qsort is a function that takes two arguments. The first one (lt) is a
function that returns True if its first argument is less than its second,
and False otherwise. The second is a list. If that list is empty, then the
result/output is of course an empty list, which is sorted by definition -
we define this as follows:

> > > qsort lt []     = []

If the second argument is not empty, then it is of the form x-then-xs
where x is the first element and xs is the list of all other elements.
Now remember how quicksort works: it takes a starting element (called a
"pivot"), then splits the list in half: the first half (call it y)
contains those elements less than the pivot, the second half contains
those greater (call it z). Now we want our output to be:
First:  the sorted list of all numbers less than the pivot (y).
Then:   the pivot element. (x)
Lastly: the sorted list of all numbers less than the pivot (z).
We use "qsort lt" to sort y and z, then construct our output list thus:

> > > qsort lt (x:xs) = qsort lt y ++ [x] ++ qsort lt z

But how did we generate y and z in the first place? The partition function
will do that for us. It takes two arguments, the first a Boolean-valued
function, and the second a list, and returns the pair of lists we seek:
(naturally, "lt x" returns true if its argument is less than x.)

> > >                   where (y,z) = partition (lt x) xs

Now if you could just explain to me how all that horrific C worked... :)

> On Monday 10 June 2002 4:31 pm, Cameron Patrick wrote:
> > Here's a challenge: rewrite my bogosort in Haskell using monads.
> Better yet, whats a monad?

A way of encapsulating destructive data updates so that they won't have
unwanted side-effects on the rest of your program.

> Even better yet, whats Haskell?

A state-of-the-art declarative functional language that uses monads,
although my code above did not need them.

-Greg