Difference between revisions of "Introduction/Direct Translation"

From HaskellWiki
Jump to: navigation, search
Line 1: Line 1:
The quicksort quoted in [[Introduction]] isn't the "real" quicksort and doesn't scale for longer lists like the c code does. To be fair, here are some points to how the "real" quicksort would look in haskell.
+
The quicksort quoted in [[Introduction]] isn't the "real" quicksort and doesn't scale for longer lists like the c code does.
  +
  +
http://programming.reddit.com/info/5yutf/comments/
  +
  +
Here are some points to how the "real" quicksort would look in haskell.
   
 
Lennart Augustsson has a quicksort entry on his blog which is pure (no unsafe):
 
Lennart Augustsson has a quicksort entry on his blog which is pure (no unsafe):
Line 5: Line 5:
 
http://augustss.blogspot.com/2007/08/quicksort-in-haskell-quicksort-is.html
 
http://augustss.blogspot.com/2007/08/quicksort-in-haskell-quicksort-is.html
   
(copy/paste didn't compile for me I'm afraid.
 
 
Another version (uses System.IO.Unsafe), is below.
 
Another version (uses System.IO.Unsafe), is below. Doesn't run in ghc either, I'm afraid.
 
   
Can someone fix either of these programs to actually run? I think this would be a great way to learn a lot about some of the less "intro" aspects of haskell.
 
  +
Unfortunately neither version seems to compile as given, when copy/pasted into ghci. Can someone fix?
   
 
<haskell>
 
<haskell>

Revision as of 19:43, 22 October 2007

The quicksort quoted in Introduction isn't the "real" quicksort and doesn't scale for longer lists like the c code does.

http://programming.reddit.com/info/5yutf/comments/

Here are some points to how the "real" quicksort would look in haskell.

Lennart Augustsson has a quicksort entry on his blog which is pure (no unsafe):

http://augustss.blogspot.com/2007/08/quicksort-in-haskell-quicksort-is.html

Another version (uses System.IO.Unsafe), is below.

Unfortunately neither version seems to compile as given, when copy/pasted into ghci. Can someone fix?

import Control.Monad (when)
import Control.Monad.ST
import Data.Array.ST
import Data.Array.IArray
import Data.Array.MArray
import System.IO.Unsafe

qsort :: (IArray a e,Ix i,Enum i,Ord e) => a i e -> a i e
qsort arr = processArray quickSort arr

processArray 
    :: (IArray a e,IArray b e,Ix i) 
    => (forall s. (STArray s) i e -> ST s ()) -> a i e -> b i e
processArray f (arr :: a i e) = runST (do
                arr' <- thaw arr :: ST s (STArray s i e)
                f arr'
                unsafeFreeze arr')

quickSort :: (MArray a e m, Ix i, Enum i, Ord e) => a i e -> m ()
quickSort arr = case bounds arr of (lo,hi) -> qsort lo hi
    where qsort lo hi | lo >= hi  = return ()
                      | otherwise = do
              p <- readArray arr hi
              l <- mainLoop p lo hi
              swap l hi
              qsort lo (pred l)
              qsort (succ l) hi
            
          mainLoop p l h | l >= h    = return l
                         | otherwise = do
              l' <- doTil (\l' b -> l' < h && b <= p) succ l                  
              h' <- doTil (\h' b -> h' > l' && b >= p) pred h
              when (l' < h') $
                  swap l' h'
              mainLoop p l' h'
          
          doTil pred op ix = do
              b <- readArray arr ix
              if pred ix b then doTil pred op (op ix) else return ix

          swap xi yi = do
              x <- readArray arr xi
              readArray arr yi >>= writeArray arr xi
              writeArray arr yi x

This uses various extensions to make the types ridiculously general, but the actual algorithm (quickSort) is plain Haskell.