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.

2) The second point you are missing is even bigger. Today languages as Clojure 
(and F# and a bit less Scala) are using more and more immutabe data structures. 
They reduce bugs, allow a quite simpler multi-processing (so they are 
multicore-friendly) and they allow a more functional-style coding (that in the 
hands of a modern compiler/VM allows gives enough semantic constraints to allow 
a good compilation. See pure functions). This of course puts more pressure on 
the garbage collector, but the GC of Haskell is designed for this purpose, and 
the compile is able to optimize away some of this work. The resulting code is 
not as efficient as C code on a single CPU but on many CPUs it may lead to 
efficient code.

Please ask if you have missed my two points, because they must be understood if 
you want to design a modern language.

Bye,
bearophile

Reply via email to