This seems to be the Haskell equivalent

[Tim Matthews]

On 22/12/2009 1:16 p.m., Nick Sabalausky wrote:
> "Tim Matthews"<tim.matthews7 at gmail.com>  wrote in message
> news:hgp10e$2sj3$1 at digitalmars.com...
>> On 21/12/2009 8:57 p.m., Don wrote:
>>> retard wrote:
>>>> Sun, 20 Dec 2009 16:44:03 +0100, Don wrote:
>>>>
>>>>> downs wrote:
>>>>>> according to
>>>>>> http://www.mail-archive.com/haskell-cafe%40haskell.org/msg63381.html
>>>>>>
>>>>>> I'll let this speak for itself.
>>>>>>
>>>>>> import Data.Array.Base (unsafeRead, unsafeWrite)
>>>>> [snip]
>>>>>
>>>>> Brilliant.
>>>>
>>>> What is so brilliant? Referential transparency is broken unless single-
>>>> threadedness is forced through monadic computation or by some other
>>>> means (uniqueness types comes to mind).
>>>
>>> The brilliant bit is the idea of doing a fairer comparison of quicksort
>>> between D and Haskell.
>>
>>
>> Quicksort can be expressed in haskell just like this:
>>
>> qsort []     = []
>> qsort (x:xs) = qsort (filter (<  x) xs) ++ [x] ++ qsort (filter (>= x) xs)
>>
>>
>> It probably performs like a bitch but is a very beautiful way to express
>> quicksort.
>
> Quicksort is in-place and doesn't use the head as the pivot.

true

> Besides "It probably performs like a bitch" defeats the whole point of
> quicksort, doesn't it?

true

> And, going along with what Andrei pointed out in
> another thread, it's hard call a piece of code "beautiful" if it's either
> flat-out wrong or otherwise defeats its own point.
>

My stance on this is that the qsort code explains how you want the code 
to be sorted and a really good haskell compiler should optimize that 
out. Infact as haskell can't update in place anything without 
interfacing to c, I often blame the compiler but realistically most 
still have some way to go for that kind of optimizations.

As for the qsort algorithm using the head as the pivot. Thanks for 
pointing that out. I didn't write it but I copy/pasted it from the 
official wiki 
http://www.haskell.org/haskellwiki/Introduction#Quicksort_in_Haskell

Another place that describe quicksort in haskell and also a wiki incase 
you want to edit it http://en.literateprograms.org/Quicksort_%28Haskell%29