Algorithms: Quicksort with Haskell

So our function definitions only add O(1) extra memory for the temporary values.

Since the stack depth is, on average, O(log n), that is the asymptotic memory usage for this algorithm.

In-Place Quicksort (Haskell)Now that we are familiar with the in-place algorithm, let’s see what it looks like in Haskell.

We want to do this with STArray, but we will still write a function with pure input and output.

Unfortunately, this means we will end up using O(n) memory anyway.

The thaw function must copy the array to make a mutable version of it.

However, the rest of our operations will work in-place on the mutable array.

We will follow the same patterns as our Java code.

Let's start simple and write our swapfunction:swap :: ST s Int a -> Int -> Int -> ST s ()swap arr i j = do elem1 <- readArray arr i elem2 <- readArray arr j writeArray arr i elem2 writeArray arr j elem1Now let’s write out our partition function.

We are going to make it look as much like our Java version as possible, but it's a little tricky because we don't have for-loops.

We will deal with this problem head on, designing a function to handle the loop.

The loop produces our value for the final pivot index, but we have to keep track of its current value.

This sounds like a job for the State monad.

Our state function will take the pivotElement and the array itself as a parameter, then it will take a final parameter for the i value we have in our partition loop in the Java version.

partitionLoop :: (Ord a) => STArray s Int a -> a -> Int -> StateT Int (ST s) ()partitionLoop arr pivotElement i = do .

We fill this with code comparable to our Java version.

We read the current pivot and the element for the current i index, then, if it's smaller, we swap them in our array and increment the pivot:partitionLoop :: (Ord a) => STArray s Int a -> a -> Int -> StateT Int (ST s) ()partitionLoop arr pivotElement i = do pivotIndex <- get thisElement <- lift $ readArray arr i when (thisElement <= pivotElement) $ do lift $ swap arr i pivotIndex put (pivotIndex + 1)Next we incorporate this loop into our primary partition function, after getting the pivot element.

We'll use mapM to sequence the state actions together and pass that to execStateT.

Then we will return the final pivot (subtracting 1).

Don't forget to swap the pivot into the middle of the array!partition :: (Ord a) => STArray s Int a -> Int -> Int -> ST s Intpartition arr start end = do pivotElement <- readArray arr start let pivotIndex_0 = start + 1 finalPivotIndex <- execStateT (mapM (partitionLoop arr pivotElement) [(start+1).

(end-1)]) pivotIndex_0 swap arr start (finalPivotIndex – 1) return $ finalPivotIndex – 1Now it is easy to incorporate these into our final function:quicksort2 :: (Ord a) => Array Int a -> Array Int aquicksort2 inputArr = runSTArray $ do stArr <- thaw inputArr let (minIndex, maxIndex) = bounds inputArr quicksort2Helper minIndex (maxIndex + 1) stArr return stArrquicksort2Helper :: (Ord a) => Int -> Int -> STArray s Int a -> ST s ()quicksort2Helper start end stArr = when (start + 1 < end) $ do pivotIndex <- partition stArr start end quicksort2Helper start pivotIndex stArr quicksort2Helper (pivotIndex + 1) end stArrThis completes our algorithm!.Notice again though, that we use thaw and freeze.

This means our main quicksort2 function can have pure inputs and outputs, but it comes at the price of extra memory.

Still, it's cool that we can use mutable data inside a pure function!ConclusionAs we have to copy the list, this example doesn’t result in much improvement.

In fact, when we benchmark these functions, we find that the first one actually performs quite a bit faster.

However, it is still useful to understand how we can manipulate data “in-place” in Haskell.

The STmonad allows us to do this in a "pure" way.

If we are willing to accept impure code, the IO monad is also possible.


. More details

Leave a Reply