[Haskell-cafe] qsort

[Daniel Fischer]

Am Samstag 15 August 2009 10:09:28 schrieb Peter Verswyvelen:
> I was reading the introduction at
> http://www.haskell.org/haskellwiki/Introduction
> where the typical Haskell version of qsort is given
>
> qsort [] = []
> qsort (x:xs) = qsort
> (filter<http://haskell.org/ghc/docs/latest/html/libraries/base/Prelude.html
>#v:filter> (< x) xs)
> ++<http://haskell.org/ghc/docs/latest/html/libraries/base/Prelude.html#v:.>
> [x]
> ++<http://haskell.org/ghc/docs/latest/html/libraries/base/Prelude.html#v:.>
>qsort
> (filter<http://haskell.org/ghc/docs/latest/html/libraries/base/Prelude.html
>#v:filter>
> (>=<http://haskell.org/ghc/docs/latest/html/libraries/base/Prelude.html#v:&
>gt;=>x ) xs
>
> which is then compared to the inplace C version, showing off how much
> shorter the Haskell version is.
>
> However, the page also has a link to a "semi-direct" translation of the C
> version, which then brings the user to all kinds of confusing threads and
> texts, like
>
> *"**Unfortunately none of the above "real" quicksorts seems to compile as
> given, when copy/pasted into ghci. Can someone fix? The "parallel"
> quicksort gave error "unknown package concurrent" when I ran make in
> quicksort/gransim. Has anyone got a functioning "real" quicksort that works
> on copy/paste? The program below is working very very slowly. It's probably
> slowsort... :o)"*
> *
> *
> Furthermore the inplace versions of qsort in Haskell are IMO less readable
> than the C version.
>
> I'm not sure but if I would be a beginner I might get confused by this.

Okay, the more direct translation of the C code

----------------------------------------------------------
import Data.Array.Base (unsafeRead, unsafeWrite)
import Data.Array.ST
import Control.Monad.ST

myqsort :: STUArray s Int Int -> Int -> Int -> ST s ()
myqsort a lo hi
    | lo < hi   = do
        let lscan p h i
                | i < h = do
                    v <- unsafeRead a i
                    if p < v then return i else lscan p h (i+1)
                | otherwise = return i
            rscan p l i
                | l < i = do
                    v <- unsafeRead a i
                    if v < p then return i else rscan p l (i-1)
                | otherwise = return i
            swap i j = do
                v <- unsafeRead a i
                unsafeRead a j >>= unsafeWrite a i
                unsafeWrite a j v
            sloop p l h
                | l < h = do
                    l1 <- lscan p h l
                    h1 <- rscan p l1 h
                    if (l1 < h1) then (swap l1 h1 >> sloop p l1 h1) else return l1
                | otherwise = return l
        piv <- unsafeRead a hi
        i <- sloop piv lo hi
        swap i hi
        myqsort a lo (i-1)
        myqsort a (i+1) hi
    | otherwise = return ()
----------------------------------------------------------------------------------------

doesn't sacrifice performance for polymorphism (the C code isn't polymorphic either) - in 
my tests, it took less than twice the time the C code took to sort the same array, not too 
bad.

It compiles as is, and if it satisfies readability requirements, somebody can put it on 
the wiki.

>
> It is often claimed that compiler technology will make it possible to
> compile high level code into efficient low level code that is almost as
> efficient as the C or asm routines. How does this apply to qsort today?

If you give it a chance to optimise, it isn't too bad.
The code from the wiki takes about three times as long as the code above,
** if it's compiled
a) with -O2 and
b) in a setting where it specialises to the appropriate unboxed array type, be it by 
giving {-# SPECIALISE #-} pragmas or by having the code in the same module as the use 
(with a good type, e.g. STUArray s Int Int) **.

If you disable optimisations by requiring fully polymorphic code and only that, the factor 
is about 80.

>
> Cheers,
> Peter Verswyvelen