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:

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)

Input Lanugage Time
2223 Haskell 395.6 ns
2223 Rust 200 ns
10971 Haskell 598.1 ns
10971 Rust 336 ns
106239 Haskell 907.9 ns
106239 Rust 766 ns
837799 Haskell 1.363 μs
837799 Rust 980 ns

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