Rust is closer to Alan Turing than it is to Alonzo Church.
Rust is closer to Alan Turing than it is to Alonzo Church.
The code in this other post about implementing string distance metrics is also quite imperative: https://markkarpov.com/post/migrating-text-metrics.html
Mutable arrays: https://hackage.haskell.org/package/vector-0.12.0.1/docs/Dat...
Strict by default: Put {#- Language Strict #-} at the top of files where necessary but usually you'd just use bangpatterns and unbox-strict-fields.
Which is intentional, of course, but quite opposite to the imperative mindset.
About {#- Language Strict #-}, thank you - I was not aware of it.
I think the first example in this post https://markkarpov.com/post/migrating-text-metrics.html makes it clear that, while one can program in imperative style, it is not at all natural, and it is going to introduce as much boilerplate as, say, trying to program in functional style in Java 6
I think the first example in that post is a bit unfair. The Haskell code is unusually complicated because it avoids a complicated problem that exists in the C code. (Which is that 16-bit encodings can't cover all of UCS-4 with fixed character widths.)
Besides, I don't understand why they are making such a complicated solution. In this comparison [1], the first example in that post is the "target". The best performing solution is... you guessed it:
foldZip a b =
List.foldl' (\r (cha, chb) -> if cha /= chb then r+1 else r) 0 (Text.zip a b)
And a pet peeve: the way you say "only in the ST monad" is a funny rhetoric device. You make it sound like everyone agrees it's a bad thing to isolate mutation to local regions. Here's the thing: it's not. And the way you can integrate local mutation in your application with the ST monad is fantastic.By just typing "ST" a few extra times you get local mutation exactly where you want to, and nowhere you don't want it!
foldZip a b
| T.length a /= T.length b = Nothing
| otherwise = foldl' step 0 (T.zip a b)
where step acc (l, r) = if l == r then acc+1 else acc
This is slightly awkward because T.length is an O(n) operation, though. I think the optimal implementation would be a hyper optimized variant that depends on correct byte alignment and this as slow fallback method if that fails.What is fast – without reaching into the Text object internal representation – is good old tail-call recursion. And you can even integrate the length check into the traversal! Making it an O(min(n,m)) operation in total.
Ah, but there is! Recursion schemes.
>Usually an imperative algorithm will be much clearer in an imperative language than in Haskell, and easier to get right on the first try.
Not sure what an "imperative algorithm" is, but I agree there are tasks better suited to imperative languages.
Well, yes, there is: general recursion. You can recreate any loop with plain old recursion.
But stating that as a problem is a little like coming to Java and saying that "there's no general purpose idiom you can use to replace goto, only tons of special semantic branching constructs you must memorize." Sure, a valid complaint if you've been forced to only use goto in your life, but not a reflection on good programming practise.
import qualified Data.Vector.Mutable as V
import Control.Monad (when)
import qualified System.Random as R
main = do
v <- V.replicate 10 0
putStrLn "Initialised to zero"
printThemAll v
setIncreasing v
putStrLn "Set with values increasing by 2"
printThemAll v
addRandomness v
putStrLn "Added a random number to each"
printThemAll v
printThemAll v = loop 0 (V.length v)
where loop i n = do
when (i < n) $ do
e <- V.read v i
print e
loop (i + 1) n
setIncreasing v = loop 0 (V.length v)
where loop i n = do
when (i < n) $ do
V.write v i (i * 2)
loop (i + 1) n
addRandomness v = loop 0 (V.length v)
where loop i n = do
when (i < n) $ do
r <- R.randomIO
e <- V.read v i
V.write v i (e + r)
loop (i + 1) n import qualified Data.Vector.Mutable as V
import Control.Monad (when)
import qualified System.Random as R
import Control.Monad.ST
st = runST $ do
v <- V.replicate 10 0
setIncreasing v
addRandomness v
printThemAll v = loop 0 (V.length v)
where loop i n = do
when (i < n) $ do
e <- V.read v i
print e
loop (i + 1) n
setIncreasing v = loop 0 (V.length v)
where loop i n = do
when (i < n) $ do
V.write v i (i * 2)
loop (i + 1) n
addRandomness v = loop initial_g 0 (V.length v)
where seed = 1234
initial_g = R.mkStdGen 1234 -- Seed
loop g i n = do
when (i < n) $ do
let (r, next_g) = R.random g
e <- V.read v i
V.write v i (e + r)
loop next_g (i + 1) n----
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)
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 <- Vector.read a hi
i' <- newSTRef (lo - 1)
j' <- newSTRef lo
fix $ \loop -> do
j <- readSTRef j'
when (j < hi) $ do
aj <- Vector.read a j
when (aj <= pivot) $ do
i <- inc i'
when (i /= j) $
Vector.swap a i j
inc j'
loop
i <- inc i'
Vector.swap a i hi
pure i
Again, I'll walk through it part by part. partition a lo hi = do
pivot <- Vector.read a hi
i' <- newSTRef (lo - 1)
j' <- newSTRef lo
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 <- readSTRef j'
when (j < hi) $ do
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 <- Vector.read a j
when (aj <= pivot) $ do
i <- inc i'
when (i /= j) $
Vector.swap a i j
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 <- inc i'
Vector.swap a i hi
pure 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 <- state (randomR (lo, hi))
lift $ do
Vector.swap a hi p
-- pivot <- Vector.read a hi
-- ...
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 <- Vector.read a hi
-- ...
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.
Just a small note, randomness in quicksort can't be hidden in unsafePerformSomething, because it does lead to impurity. For example, sorting [(0,1),(0,2)] on fst will give different results depending on randomness. But that's not to detract from your main point.