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
}

import Data.Functor.FoldablecollatzLength :: 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)
Input Language Time
2223 Rust 209 ns
10971 Rust 512 ns
106239 Rust 611 ns
837799 Rust 1.291 μs

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.