This is the most Monadic code I have written to date :-) and I'd welcome comments.
I'm also struck how much faster this mutable approach is than the immutable version I first wrote (see end). OK, so QuickSort is pretty much on mutability, but most algorithms seems to involve significant manipulation of elements in the data structure and immutability leads to slowness due to the endless copying of e.g. Arrays. I'm left wondering whether immutability is practical in the real world?
-- qsort :: Array -> beginning of subsection -> end of subsection
qsort :: (IOArray Int Int) -> Int -> Int -> IO ()
qsort arr min mx =
if mx - min < 1 then do
return ()
else do
p <- readArray arr min
--foldM :: Monad m => (a -> b -> m a) -> a -> [b] -> m a
final_i <- foldM (partitioner p) (min+1) [(min+1)..mx]
swap min $ final_i - 1
qsort arr min (final_i-2)
qsort arr final_i mx
where
swap i j = do
arr_i <- readArray arr i
arr_j <- readArray arr j
writeArray arr i arr_j
writeArray arr j arr_i
partitioner p i idx = do
arr_idx <- readArray arr idx
if arr_idx > p then
return i
else do
swap i idx
return $ i+1
I have since made the minor modifications to use an ST Monad (Gist). Not sure which is to be considered better Haskell though.
qsort :: (V.Vector Int) -> Int -> Int -> (V.Vector Int)
qsort v i j
| len < 2 = v
| j > len - 1 =
let
-- should really switch pivot with last point in < group
--swap 0 (i-1)
(less, greater) = V.splitAt i v
less_sorted = qsort (V.tail less) 1 1
great_sorted = qsort greater 1 1
in less_sorted V.++ cons (V.head less) great_sorted
| vector_j > p =
qsort v i (j + 1)
| otherwise =
qsort (swap i j) (i+1) (j+1)
where
len = V.length v
p = v ! 0
vector_i = v ! i
vector_j = v ! j
swap i' j' = update v $ fromList [(i', v!j),(j', v!i)]
