Rust as a gateway drug to Haskell

AFAIK only the core language is fully ported, for the libraries ... it is a work in progress.

Cache locality will never beat algorithmic complexity as a performance factor. Don't exaggerate its importance.

This is an oversimplification. Some compute intensive parts can get significant speed ups through careful use of data parallelism (such as SIMD). Others needs parallelism at the thread level. Etc. Optimizing for memory patterns is important as is trying to keep the working set within a near-level cache.

I think you're confusing higher-kinded types with type classes. You're right that neither has type classes.

It wasn't busted with .NET Core 1.0.1 005db40cd1.

Is F# working with .NET Core 2.0 Preview 1 for you?

A few months ago I read monomorphism is the way to go performance wise.

Something about people writing fast code with Flow/TypeScript than with plain JavaScript because the typing leads to less polymorphic code which is easier to optimize for the compiler.

I agree with all that, particularly the bit about the c ffi call. It's more relevant to compare Rust with C and C++, as Rust is a language that could reasonably display C for the ffi call.

But then remember that @wyager is claiming

>80% as fast as hand-optimized C for only 10% of the effort of hand-optimized C

If it's really only 10% of the effort then one shouldn't really have "to work on it" to get semi-decent performance.

A more modest claim of say:

50% as fast as hand-optimized C for only 20% of the effort of hand-optimized C

would have been more credible and still a big win for many use cases.

That pi-digits program does not "build on [your] machine no problem".

It cannot.

The line "main = putStr.pidgits.read.head =<< getArgs" has been commented out because the program author has optimised-away some of the work that must be done.

>> The make errors are a bit weird because the programs build on my machine no problem. <<

My fault (except for pi-digits and regex-redux).

I neglected to work-through the force-reinstalls that inevitably follow my update of the GHC compiler.

Done.

Isn't Haskell intended to be a general purpose programming language?

That's OK!

Well, if you want to do full imperative programming with warts and all, you'll probably want to stick to the IO monad for your entire program anyway. You just have to be aware that you're actively handicapping your compiler by choosing to do full imperative programming. (In most other languages, the compilers come handicapped out of the box...)

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!

[1]: http://i.xkqr.org/scrot_20170615032548.png

What's wrong with this?

    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

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)

(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 <- 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.