(continued from previous comment)
But what's really interesting is the partitioning procedure. That's where things get complicated. According to Wikipedia, it can be implemented in an imperative language like so:
algorithm partition(A, lo, hi) is
pivot := A[hi]
i := lo - 1
for j := lo to hi - 1 do
if A[j] ≤ pivot then
i := i + 1
if i ≠ j then
swap A[i] with A[j]
swap A[i+1] with A[hi]
return i + 1
This is the Haskell translation I came up with:
partition a lo hi = do
pivot do
j
Again, I'll walk through it part by part.
partition a lo hi = do
pivot
Since we're already running this as part of an ST expression, we don't need to specify "runST". First thing, we read the last element of the vector as our pivot, and we define two new references to mutable values i' and j'. (I like to indicate references with ticks like that to distinguish them from the value they contain. Ticks sort of remind me of the C pointer asterisk so it works out.)
fix $ \loop -> do
j
Okay, so last time we created a named loop through the "let" keyword, which defines new variables and functions. We could do that here as well, but I think this other approach generates neater code in this case. The "fix" combinator might twist your mind the first few times you see it, but suffice it to say that it creates a recursive function from an anonymous function, by supplying the function with itself as its first argument. You'll see soon one of the reasons I preferred it in this case.
Then we read the value of the j' reference and use it as our loop condition. The loop should run as long as j is less than hi.
aj
We read the value under j in the array, and if it is less than the pivot we increment the value in the i' reference. If the incremented value is different from j, we swap the two in the array.
inc j'
loop
Regardless of how aj compared to the pivot, we increment the value under the j' reference and go back to the top again to start a new iteration.
i
When the loop has finished, we increment i', swap the pivot element back in to its right place, and then return i.
There are three things of note here:
1) One of the major differences with the imperative code is that in imperative Haskell code, we sometimes need to "dereference" mutable variables in a separate statement. We (generally) cannot do that as part of an expression.
There are some structured ways around this even in Haskell, but at that point it might no longer be worth using Haskell to write imperative code. Why do I say that? Because it's actually a good thing that we need to dereference mutable variables in a separate statement. Several "safe coding standards" over the decades have evolved toward "keep expressions free from side-effects and have one statement per side effect".
2) When we defined the loop with fix we didn't have to call it separately from its definition. That's one of the benefits I was talking about.
3) I forgot what number three was.
----
Randomness, you said? That's a common optimisation to the quicksort shown above. The pivot is picked at random in the inclusive range [lo,hi] instead of fixed at hi.
It is child's play to include it by simply passing a random generator as a parameter down the call chain to partition, so I'm not going to show that. What I'm going to show instead is how trivial it is to abstract that parameter away into a state transformer wrapper.
I intentionally ignored this aspect until now to get honest results about shimming randomness in there. Here are the changes:
1.
partition a lo hi = do
p
I converted the partition method to a state transformer, which makes it possible to compute a random number in the [lo,hi] range and implicitly update the generator state. Then I swap the highest element and the chosen pivot, and the rest of the algorithm is the same as before.
The state transformer also means that the rest of the partition function is now lifted, but that's no biggie.
2.
quicksort gen vec = runST . flip evalStateT gen $ do
-- pivot
The quicksort function needs to wrap the ST expression in a state transformer, but is otherwise exactly the same as before.
Since we need some sort of generator to start with, the quicksort function now also takes a generator as an argument and puts it in the state.
This is not super clean – the quicksort needs to receive a generator each time it is called? Well, yeah, sorta–kinda. This is probably one of those places where it's legitimate to do an "unsafePerformSomething" – the randomness does not cause any actual impurity in the code.
----
What I did not attempt, and what is a complicated subject anyway, was the issue of arbitrary pivot selection strategies. It's easy to integrate support for random pivots, but what if the user wants to specify a pivot selection strategy of their own?
That's fine if it's pure, or at least only relies on randomness, but what if it's unrestricted in its effects? What if they want to supply a strategy that calls your grandmother and asks her for a good pivot, or one that launches nuclear missies and counts the casualties to determine a pivot?
That's clearly some serious international side effects, and I think that we do want to prevent the user from inserting strategies with arbitrary effects. But where to draw the line? And how to distinguish these kinds of effects? Haskell only throws them all into the IO bin, which is a problem.
But the problem is not that effects are controlled, it's that even in Haskell there's a certain lack of control over effects.