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)]