# Introduction/Direct Translation

### From HaskellWiki

< Introduction(Difference between revisions)

Derek Elkins (Talk | contribs) m |
(add some context for quicksort in haskell) |
||

Line 1: | Line 1: | ||

+ | This code seems to have been created because the quicksort quoted in the introduction isn't the "real" quicksort and doesn't scale for longer lists like the c code does. To be fair, this is 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): | ||

+ | |||

<haskell> | <haskell> | ||

import Control.Monad (when) | import Control.Monad (when) |

## Revision as of 19:08, 22 October 2007

This code seems to have been created because the quicksort quoted in the introduction isn't the "real" quicksort and doesn't scale for longer lists like the c code does. To be fair, this is 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):

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.