# Difference between revisions of "Introduction/Direct Translation"

From HaskellWiki

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. |
+ | 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. |
||

⚫ | |||

− | |||

⚫ | |||

− | 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.