3 ms·
If you need writeArray and randomness and you don't like loop combinators, there is absolutely no problem using general recursion. That's one of the beauties of
by kqr 9y ago
If you need writeArray and randomness and you don't like loop combinators, there is absolutely no problem using general recursion. That's one of the beauties of the monadic interface – it composes very well!
----
I'm going to show you some Haskell code now. This is code that could probably use improvement, but the reason it may look sketchy in some places is that I – surprise! – reliably wrote it on a napkin.
Excepting some typos, obvious brainfarts and missed imports, this is actually the first draft of the code. Here's the quicksort algorithm as it is written on Wikipedia:
algorithm quicksort(A, lo, hi) is
if lo < hi then
p := partition(A, lo, hi)
quicksort(A, lo, p – 1)
quicksort(A, p + 1, hi)
It's Haskell implementation will be very similar:
quicksort vec = runST $ do
mvec <- thaw vec
let loop lo hi = when (lo < hi) $ do
p <- partition mvec lo hi
loop lo (p-1)
loop (p+1) hi
loop 0 (Vector.length mvec - 1)
freeze mvec
I'll walk through it line by line, even though most of it is very similar to the Wikipedia imperative pseudocode.
quicksort vec = runST $ do
mvec <- thaw vec
We run this stuff as an ST expression, which is the Haskell way of saying "hey this block of code does actual mutation, be careful". The first thing we do is thaw the vector, which means making it mutable.
let loop lo hi = when (lo < hi) $ do
We define a loop that is going to depend on two variables for iteration: lo and hi. It runs for as long as lo is less than hi, and will break when hi is equal to or less than lo.
p <- partition mvec lo hi
loop lo (p-1)
First, we call the partition procedure which divides the vector into two halves and returns to us the index of the pivot element between the two.
Then, since we are in a function called "loop" we can continue to the next iteration by calling "loop". The neat thing about this is how it looks like we almost defined our own keyword, which acts somewhat like a "continue" statement in imperative languages.
There is a difference, though. The "continue" statement in an imperative language would abort the current iteration, go back to the top of the loop and run another Iteration. The "loop" statement in our code also goes back to the top of the loop, but it doesn't abort the current iteration. Which means we can
loop (p+1) hi
also run a second iteration. This is in principle independent from the previous execution, so you can sort of view this as a "multi-continue" that starts two new iterations of the loop in parallel. In reality, though, the execution is sequential because the compiler doesn't have enough information to determine that they are indeed independent.
loop 0 (Vector.length mvec - 1)
Note that until now, the loop was only defined – it was never executed. But now we execute it with the initial values for lo and hi. It may seem weird that definition and execution of a loop can be separate from each other, but I haven't been able to come up with any reason that could end up bad.
freeze mvec
After we're done, we freeze the vector to make it immutable again. It might sound like an expensive operation, but it's not. Hopefully, the compiler will understand that nobody else has simultaneous access to the array so it will perform the modifications in-place and optimise away the thawing and freezing.
(continued in second comment)