Beginning Rust - solving Euler problem #1

Rust is a relatively new programming language (first alpha released in 2012) which recently caught my attention. Although I'm mostly a Python hacker and Web developer, I still do lower level coding from time to time, including some open source work in C++. Besides, I enjoy the elegance of Haskell; the functional approach to solving problems is quite enlightening. Where does Rust fit into that? The language is still a work-in-progress territory (as of this post the current version is 0.10), but there are already many interesting features. Memory safety, strong typing (with type inference), pattern matching and a slick concurrency model are just a few of those. Let's jump in!

Note: this blogpost series (well, hopefully a series) is not intended to be a Rust tutorial; rather a collection of insights and tips I'm discovering while learning Rust.

Euler #1

I tend to learn new languages by solving a few problems from Project Euler, so this was my natural choice for my first steps in Rust.

The first problem is stated as follows:

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23. Find the sum of all the multiples of 3 or 5 below 1000.

This is rather easy, you could possibly do it in a matter of seconds with a calculator. Anyway, let's make Rust calculate that for us.

Coming from a C/C++ background, a loop seems like a natural solution.

fn solution1 () -> int {
let mut sum = 0;
for i in range(1, 1000) {
if i % 3 == 0 || i % 5 == 0 {
sum += i;
}
}
sum
}

It works, but it irks me to write code in such an imperative way. There should be some better alternative. Haskell, for example, has a concept of folds. Folds are basically higher-order functions that take a binary operation, a list (or other foldable type, but let's keep it simple for a while) and a starting value and build up their return value by reducing the list with the given operation. If that sounds complicated, Learn You A Haskell For Great Good provides an explanation. Let's see an example of solving problem 1 with a left fold in Haskell.

solution1 = foldl (\x acc -> x + acc) 0 numbers where
numbers = [x | x <- [1..999], x `mod` 3 == 0 || x `mod` 5 == 0]

or simplified by reducing lambda to just the + operator:

solution1 = foldl (+) 0 numbers where
-- ...

Good news - Rust also has folds!

fn solution2 () -> int {
let mut numbers = range(1, 1000).filter(|i| i % 3 == 0 || i % 5  == 0);
numbers.fold(0, |acc, x| acc + x)
}

The return values of both range and filter implement an Iterator trait, which means they have lots of useful methods like map, any, all and yes, fold.

Can we do even better? Folding addition over a list is so common that Haskell has a builtin function sum in the standard Prelude.

solution1 = sum numbers where
-- ...

In case of Rust, this isn't as straightforward. Iterators don't have a sum method...

... unless we magically add it by including another trait definition - AdditiveIterator.

fn solution3 () -> int {