As you may have read in one of my past posts or elsewhere, performance across languages can be complicated, and it's not always as obvious as you'd expect.

The following is an example of a case where Haskell performs admirably, and still lets us use the high-level control structures that we'd like to.

The task is simple: find out how long the Collatz sequence associated with a number is.

Our Rust code:

fn modular(a: i64, b: i64) -> i64 {
    ((a % b) + b) % b
}
pub fn collatz_length(mut i: i64) -> i64 {
    let mut l = 1;
    while i != 1 {
        i = match modular(i, 2) {
            0 => i / 2,
            _ => 3 * i + 1,
        };
        l += 1;
    }
    l
}

Our Haskell code:

import Data.Functor.Foldable
collatzLength :: Int -> Int
collatzLength = elgot algebra elgotCoalgebra
    where algebra Nil        = 0
          algebra (Cons _ x) = x + 1
          elgotCoalgebra 1 = Left 1
          elgotCoalgebra n
             | n `mod` 2 == 0 = Right $ Cons n (div n 2)
             | otherwise = Right $ Cons n (3 * n + 1)

To emulate these benchmarks, clone the morphism-zoo repo and then enter cabal new-bench collatz-bench for the Haskell and cd rust/ && cargo bench -- collatz_length for the Rust.

Conclusion

So, what to conclude? After all the Haskell code is (as expected) slower than the Rust code. Well, several things:

A) The languages achieve parity because the meat of the problem (arithmetic) is tractable. Laziness, as much as people like to bloviate, is not really problematic here.

B) Haskell's more expressive control structures are in fact feasible. For small values, Haskell achieves performance within 50% of that of Rust, and it does even better for larger values.

C) When approaching a problem where memory management isn't crucial, garbage-collected languages can perform well.

D) The Rust wasn't actually that bad anyhow. Elgot algebras are definitely more fun, but an 8-line function and a 15-line function are both pretty manageable. The disadvantage of the Rust shown here is mainly that code reuse suffers.