gistfile1.lhs

So I was watching an MIT lecture on algorithms, and they were talking about 
the quicksort, so I decided I should revisit it in haskell now that I have 
a little more experience.  The common example you see has issues with repeated
work.  I attempt to minimize this me avoiding list concatenation and 
using a partition instead.

I used literate Haskell because I plan to add better annotations later.

> {-# LANGUAGE PatternGuards #-}
> module Quicksort where 

This is the original version for reference.

> badQuicksort :: Ord a => [a] -> [a]
> badQuicksort []     = []
> badQuicksort (p:xs) = (quicksort lesser) ++ [p] ++ (quicksort greater)
>     where
>         lesser  = filter (< p) xs
>         greater = filter (>= p) xs

This is my verion, which is a tad longer due to the extra logic.  Note
that this is still stable.  It's not quite in place, as no linked list
can be sorted in place (save edge cases such as building an array with an 
entry for every node), but there should be very little element duplication.

> quicksort :: Ord a => [a] -> [a]
> quicksort = flip quicksort' []
>   where quicksort' [] = id
>         quicksort' [a] = (a:)
>         quicksort' (pivot:rest) =
>             quicksort' left . (pivot:) . quicksort' right
>           where (left, right) = partition (<pivot) rest

This is helper code that partions the list into two mathematical classes
on a predicate

> partition :: (a -> Bool) -> [a] -> ([a], [a])
> partition _ [] = ([], [])
> partition predicate (x:xs) = ((x:ls, rs) ?? (ls, x:rs)) $ predicate x
>   where (ls, rs) = partition predicate xs

A helper function because if ... then ... else ... isn't Haskelly enough.

> (??) :: a -> a -> Bool -> a
> (true ?? false) bool = if bool then true else false