Go rant

[bearophile]

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