Andrei Alexandrescu wrote:
bearophile wrote:
Walter Bright:
Ain't that cool? But look closer. The advantage of quicksort is
that it is an *in-place* sort. The Haskell one creates new arrays
for every state in the sort. The other fundamental problem with the
Haskell version is that it selects the first array element as the
"pivot". This is the worst choice, since arrays to be sorted tend
to already be mostly sorted, and quicksort gives quadratic
performance to sort an already sorted array with the first element
as the pivot.
You are missing two big things, Walter:
1) The first one is big: that was not an example of a general-purpose
sort routine to be used to sort items. If you go look at how normal
system sort is done in Haskell you will see a much longer and much
more efficient implementation. The point of that example was to show
how you can compactly express a computational idea in Haskell, in a
safe, very compact and readable enough way. In a normal program a
significant percentage of the code doesn't need to be top
performance, in both runtime performance and memory used, because
it's used rarely and/or on small data sets. So for this code it's not
good to write an extremely efficient implementation, it's better to
use a safe, very compact and readable implementation. Haskell gives
you both safety and compact code. Note that for real sorting purposes
you don't use that onliner, you use some kind of system sort. So what
I am says applies to new code, absent in the standard library.
It's a piece of crap. A crappy example is a crappy example is a crappy
example. It consistently does more harm than good.
What's that argument?
