On Jun 27, 2007, at 12:15 PM, Stewart Stremler wrote:
begin quoting Tracy R Reed as of Wed, Jun 27, 2007 at 01:16:51AM
-0700:
A neat example is to compare quicksort in haskell:
quicksort :: (Ord a) => [a] -> [a]
quicksort [] = []
quicksort (p:xs) = quicksort [ x | x <- xs, x <= p ] ++ [ p ] ++
quicksort [ x | x <- xs, x > p ]
Unexpected truncation?
Huh?
Plus, it needs comments.
I disagree here. You need to know the language to interpret it, but
even without that, if you have a familiarity with the quicksort
algorithm, it is very easy to see what is happening here.
Also, as it seems to be a standard implementation of quicksort, it's
going to have _lousy_ worst-case performance.
Sure. I don't believe this was meant to be an example of "best sort
EVAR!". Simply how easy it is to write.
How easy is it to add such things?
Again, one can reasonably extrapolate from the code sample just how
difficult this is.
Oh, and it's broken -- the pivot is *always* the lowest element in the
array, which means it's a pretty sad (and slow) quicksort.
Statistically, it will be just as efficient as any other single pivot
sample based selection process. Yes, it has a really crappy corner
case, but so did the Haskell example. It is an apples to apples
comparison.
Better to look at Arrays.sort, which is part of Java, and generally
implemented with a good quicksort...and as this is what's used in the
standard library, it arguably counts as "typical" (but it's not so
succinct as the Haskell version, but it probably runs a hell of a lot
...quicker... than the Haskell version too).
If only Haskell had a fast and efficient sort algorithm... oh wait. ;-)
Seriously, you're missing the point of the post.
Once you read up on the fundamentals of haskell you realize (I did,
anyway) that the haskell code expresses the idea that you have a
pivot
point and you put everything greater than the pivot on one side and
everything less than the pivot on the other side...and then you do it
again. Until you have the whole list sorted.
How about an exploded description of the syntax. I see most of it,
except that I don't see how the pivot is selected, which is really
the key to quicksort.
It's grabbing the head of the list as the pivot, so it is
algorithmically consistent with the Java solution.
I don't buy "You gotta drink the koolaid" arguments.
Hey, functional programming has fairly obvious gotchas, but it
clearly has some advantages and you don't have to drink the koolaid
to recognize that.
--Chris
--
KPLUG-LPSG@kernel-panic.org
http://www.kernel-panic.org/cgi-bin/mailman/listinfo/kplug-lpsg
