FizzBuzz revisited

One of the cool things about being involved with the development of Rust over the last couple of years has been watching the community grow along with the language. When I came to Mozilla as an intern in March 2011 and started contributing to Rust, the Rust “community” consisted of perhaps twenty people who frequented the #rust IRC channel, most of whom were Mozilla employees. There weren’t any third-party resources for helping people get started with Rust back then.

Two years later, there are 170 users in #rust on a typical Saturday afternoon like this one, and we’re starting to have a healthy ecosystem of volunteer-created Rust Stuff, such as this book by Steve Klabnik.¹ In his book, after getting some basics out of the way, Steve shows how to code up a solution to the FizzBuzz problem in Rust. FizzBuzz is a simple programming problem that is nevertheless infamous for stumping people in job interviews: Write a program that prints the numbers from 1 to 100. But for multiples of three, print “Fizz” instead of the number, and for multiples of five, print “Buzz”. For numbers that are multiples of both three and five, print “FizzBuzz”. People like to use it as a toy problem for getting started with a new programming language, because it covers iteration, conditionals, and printing output.

But FizzBuzz also struck me as the perfect way to introduce some of Rust’s pattern-matching features. Pattern matching is everywhere in Rust code, and Steve does get to it later on in the book, but I couldn’t help myself—this problem was just crying out for it. So, here’s an introduction to pattern matching in Rust, by way of FizzBuzz.

The original code

Here’s the version of FizzBuzz from Steve’s book, minus the tests:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

extern mod std;

fn is_three(num: int) -> bool {
   num % 3 == 0
}

fn is_five(num: int) -> bool {
   num % 5 == 0
}

fn is_fifteen(num: int) -> bool {
   num % 15 == 0
}

fn main() {
  for int::range(1, 101) |num| {
    io::println(
      if is_fifteen(num) { ~"FizzBuzz" }
      else if is_three(num) { ~"Fizz" }
      else if is_five(num) { ~"Buzz" }
      else { int::str(num) }
    );
  }
}

This code works fine, but let’s see if we can rewrite the main function to use pattern matching.

First version: transliterate into match

First, let’s try writing something that looks a lot like the original, but uses Rust’s match construct.

1
2
3
4
5
6
7
8
9
10
11
12

fn main() {
    for int::range(1, 101) |num| {
        io::println(
            match num {
                _ if is_fifteen(num) => ~"FizzBuzz",
                _ if is_three(num) => ~"Fizz",
                _ if is_five(num) => ~"Buzz",
                _ => int::str(num)
            }
        );
    }
}

In Rust, the match language construct takes an expression, in this case num, and a number of arms, each beginning with a pattern. In this example, the first arm (on line 5) begins with _, which is the “wildcard” pattern—that is, it matches everything. But then, the match is narrowed down by is_fifteen(num), the value of which determines whether that arm is actually taken. The if is_fifteen(num) is what’s known as a pattern guard. If is_fifteen(num) evaluates to true, we take that arm.

Looking at the next match arm on line 6, we see that its pattern is also _, the wildcard pattern. In fact, all of the patterns in this example are _, and all of the work of matching is being done by pattern guards.

Second version: match against tuples of bools

The code from our first attempt actually works fine, but it’s a rather weird (and error-prone) way to use pattern matching. Pushing all of the work into the pattern guards makes the code a bit confusing, and it doesn’t really let us take advantage of the convenience and power of pattern matching. So, let’s try something else:

1
2
3
4
5
6
7
8
9
10
11
12

fn main() {
    for int::range(1, 101) |num| {
        io::println(
            match (is_three(num), is_five(num)) {
                (true, true) => ~"FizzBuzz",
                (true, false) => ~"Fizz",
                (false, true) => ~"Buzz",
                _ => int::str(num)
            }
        );
    }
}

Here, we’re matching against a tuple of two values: the value of is_three(num) and the value of is_five(num). If both of them are true, then we print FizzBuzz. Notice that we don’t need the is_fifteen function anymore, because the tuple (true, true) covers exactly that case! Pattern matching has already helped us.

This code works fine as written, but there’s another tweak we can make. Since the only possible match for the wildcard pattern in the final arm is (false, false) (since every other case has already been handled), we might as well change it to that:

1
2
3
4
5
6
7
8
9
10
11
12

fn main() {
    for int::range(1, 101) |num| {
        io::println(
            match (is_three(num), is_five(num)) {
                (true, true) => ~"FizzBuzz",
                (true, false) => ~"Fizz",
                (false, true) => ~"Buzz",
                (false, false) => int::str(num)
            }
        );
    }
}

Doing so leads to an unexpected win: now we can reorder the match arms any way we want. In the version that used if, we would’ve been in trouble if the “FizzBuzz” case hadn’t been first or if the final, catch-all case hadn’t been last, but now it’s fine to order them any which way. We can swap the “FizzBuzz” case and the catch-all cases around, for instance:

1
2
3
4
5
6
7
8
9
10
11
12

fn main() {
    for int::range(1, 101) |num| {
        io::println(
            match (is_three(num), is_five(num)) {
                (false, false) => int::str(num),
                (true, false) => ~"Fizz",
                (false, true) => ~"Buzz",
                (true, true) => ~"FizzBuzz"
            }
        );
    }
}

Moreover, if we forget any of the arms, the compiler tells us that we’ve made a mistake. Commenting out the “Fizz” case, for instance, results in an error, telling us that the match patterns didn’t cover all possible cases.² This is called exhaustiveness checking.

1
2
3
4
5
6
7
8
9

$ rustc fizzbuzz.rs
fizzbuzz.rs:18:12: 23:13 error: non-exhaustive patterns: false not covered
fizzbuzz.rs:18             match (is_three(num), is_five(num)) {
fizzbuzz.rs:19                 (false, false) => int::str(num),
fizzbuzz.rs:20                 // (true, false) => ~"Fizz",
fizzbuzz.rs:21                 (false, true) => ~"Buzz",
fizzbuzz.rs:22                 (true, true) => ~"FizzBuzz"
fizzbuzz.rs:23             }
error: aborting due to previous error

Exhaustiveness checking is conservative, meaning that if the compiler can’t determine whether a match is exhaustive or not, it will complain of non-exhaustiveness even if the match really is exahaustive. To illustrate, let’s try writing this code slightly differently.

Third version: match against tuples of ints

Instead of using the is_three and is_five functions, let’s try matching directly against the values of num % 3 and num % 5.

1
2
3
4
5
6
7
8
9
10
11
12

fn main() {
    for int::range(1, 101) |num| {
        io::println(
            match (num % 3, num % 5) {
                (0, 0) => ~"FizzBuzz",
                (0, n) if n != 0 => ~"Fizz",
                (m, 0) if m != 0 => ~"Buzz",
                (m, n) if m != 0 && n != 0 => int::str(num)
            }
        );
    }
}

Now we’re matching against a tuple of ints instead of a tuple of bools, and we’re using pattern guards to make the arms of the match non-overlapping and therefore order-independent. Unfortunately, this code won’t compile. As it turns out, the match is exhaustive, but the compiler can’t determine that it is. We get the following error:

1
2
3
4
5
6
7
8
9

$ rustc fizzbuzz.rs
fizzbuzz.rs:18:12: 23:13 error: non-exhaustive patterns
fizzbuzz.rs:18             match (num % 3, num % 5) {
fizzbuzz.rs:19                 (0, 0) => ~"FizzBuzz",
fizzbuzz.rs:20                 (0, n) if n != 0 => ~"Fizz",
fizzbuzz.rs:21                 (m, 0) if m != 0 => ~"Buzz",
fizzbuzz.rs:22                 (m, n) if m != 0 && n != 0 => int::str(num)
fizzbuzz.rs:23             }
error: aborting due to previous error

In order to confirm that the match is exhaustive, the compiler would have to be able to prove that, for instance, the cases excluded by the if m != 0 && n != 0 pattern guard on the last arm are covered by the other arms of the match. It can’t do that, so it assumes that the match is non-exhaustive and raises an error.

But all isn’t lost: we can just get rid of the pattern guards. The result is a match that the compiler knows is exhaustive. The only drawback is that now we can no longer reorder the match arms at will. (Also, we would get an unused variable warning if we continued to use m and n after getting rid of the pattern guards that use them, so we’ll just change them to underscores.)

1
2
3
4
5
6
7
8
9
10
11
12

fn main() {
    for int::range(1, 101) |num| {
        io::println(
            match (num % 3, num % 5) {
                (0, 0) => ~"FizzBuzz",  // must come first
                (0, _) => ~"Fizz",
                (_, 0) => ~"Buzz",
                (_, _) => int::str(num) // must come last
            }
        );
    }
}

Code like this turns up all the time in Rust programs. It’s concise, convenient and easy to write. But there’s still that nagging issue of certain clauses having to come first and last, because the match patterns overlap with each other to some extent.

Is there a way to get back the order-independence of the version that used Booleans, but without relying on Booleans?

Why not just use Booleans?

First of all, why might we not want to use Booleans? The answer is that sometimes we want more information than a Boolean value is capable of carrying. Consider again our version of FizzBuzz that matches against a tuple of bools:

1
2
3
4
5
6
7
8
9
10
11
12

fn main() {
    for int::range(1, 101) |num| {
        io::println(
            match (is_three(num), is_five(num)) {
                (false, false) => int::str(num),
                (true, false) => ~"Fizz",
                (false, true) => ~"Buzz",
                (true, true) => ~"FizzBuzz"
            }
        );
    }
}

It works just fine for our purposes so far, of course. But suppose that, in addition to the usual FizzBuzz specification, we also wanted to print “Zot” every time we encountered a number that had a remainder of 2 when divided by 3, and a remainder of 1 when divided by 5. (Such numbers include 11, 26, 41… .)

Admittedly, this is a contrived problem. But if we did want to handle it, we’d have to overhaul our code, because the results of is_three and is_five don’t give us enough information. They tell us whether their arguments have a remainder when divided by three and five, respectively, but they don’t tell us what that remainder is.³

In that sense, the version that matches against tuples of ints instead of bools is much more flexible. We can handle the “Zot” case with a one-line addition to it:

1
2
3
4
5
6
7
8
9
10
11
12
13

fn main() {
    for int::range(1, 101) |num| {
        io::println(
            match (num % 3, num % 5) {
                (2, 1) => ~"Zot",
                (0, 0) => ~"FizzBuzz",  // must come first (or second, if "Zot" is first)
                (0, _) => ~"Fizz",
                (_, 0) => ~"Buzz",
                (_, _) => int::str(num) // must come last
            }
        );
    }
}

The “Zot” case can be inserted almost anywhere—including before the “FizzBuzz” case, which previously had to be first. The catch-all (_, _) pattern still has to come last, though.

Having it both ways

Is there a way to get the order-independence that we get when we match against bools, but also the flexibility we get when we match against ints? Yes, there is!

Since neither int nor bool are quite what we want, we’ll define our own type, which we’ll call Rem for remainder. Rem is the type of values that are the result of the num % 3 and num % 5 operations. We know that such a value will be one of 0, 1, 2, 3, or 4 (or one of just 0, 1, or 2 in the case of num % 3). For regular FizzBuzz, all we care about is whether the value is 0 or not; for the “Zot” situation, on the other hand, we need more information. So, we define the Rem type accordingly:

1
2
3
4
5
6
7
8

enum Rem {
    zero,
    other(NonZeroRem)
}

enum NonZeroRem {
    one, two, three, four
}

The Rem type distinguishes two variants of values: those that are zero, and those that are something else. In the “something else” case, we also carry around the information about what the non-zero value is, just in case it becomes important.

Informally, these types let us treat a value like a bool if we squint at it one way and use the zero/other distinction, but we can also treat it like an int if we feel like doing so (albeit one in a finite range, and a rather narrow one at that, but it’s all we need for this problem). We also could have defined separate types for values that are the result of num % 3 and values that are the result of num % 5, if we had wanted to be especially pedantic.

Given an int in the range 0-4, it’s easy to determine the corresponding value of type Rem. The int_to_rem function takes an int and returns a Rem representation of it.

1
2
3
4
5
6
7
8
9
10

fn int_to_Rem(num: int) -> Rem {
    match num {
        0 => zero,
        1 => other(one),
        2 => other(two),
        3 => other(three),
        4 => other(four),
        _ => fail
    }
}

The last case raises an error because if we ever pass something to int_to_Rem that’s not in the range 0-4, we’ve done something wrong—there’s no Rem representation for such a value.

Final version: match against tuples of Rems

Now, we can write our code this way:

1
2
3
4
5
6
7
8
9
10
11
12

fn main() {
    for int::range(1, 101) |num| {
        io::println(
            match (int_to_Rem(num % 3), int_to_Rem(num % 5)) {
                (zero, zero) => ~"FizzBuzz",
                (zero, other(_)) => ~"Fizz",
                (other(_), zero) => ~"Buzz",
                (other(_), other(_)) => int::str(num)
            }
        );
    }
}

Now we’re matching against a tuple of Rems, but we’ve retained the order-independence that we had when we were matching against a tuple of bools. Because the cases are all non-overlapping, we can put them in any order we want—say, like this:

1
2
3
4
5
6
7
8
9
10
11
12

fn main() {
    for int::range(1, 101) |num| {
        io::println(
            match (int_to_Rem(num % 3), int_to_Rem(num % 5)) {
                (other(_), other(_)) => int::str(num),
                (zero, other(_)) => ~"Fizz",
                (other(_), zero) => ~"Buzz",
                (zero, zero) => ~"FizzBuzz"
            }
        );
    }
}

And because we’re working with Rems instead of bools, we can easily modify the code to handle the “Zot” case:

1
2
3
4
5
6
7
8
9
10
11
12
13

fn main() {
    for int::range(1, 101) |num| {
        io::println(
            match (int_to_Rem(num % 3), int_to_Rem(num % 5)) {
                (other(two), other(one)) => ~"Zot",
                (other(_), other(_)) => int::str(num),
                (zero, other(_)) => ~"Fizz",
                (other(_), zero) => ~"Buzz",
                (zero, zero) => ~"FizzBuzz"
            }
        );
    }
}

To be fair, we had to introduce a little bit of order-dependence here, because the pattern for the “Zot” case overlaps with the (other(_), other(_)) pattern, so the former has to come before the latter. But there are no ordering constraints other than that. Specifically, there’s no particular arm that has to come last, as we had when we were working with ints.

Finally, if we really wanted order-independence at all costs, we could always get it by spelling out cases for each of the NonZeroRem variants. This is possible because there are a finite number of values of NonZeroRem type, whereas it wouldn’t have been possible if we were still working with ints. It’s when working with enum types like Rem and NonZeroRem that Rust’s pattern-matching features are particularly handy, and this post really only scratches the surface of what you can do.

So, go forth and pattern-match, and let me know how it goes!

This post is adapted from a gist I wrote back in December. The code has been tested with Rust 0.5, which is the most recent release as of this writing.

Update (March 3, 2013): I just added two of the versions of FizzBuzz from this post to the Rust section of the Rosetta Code FizzBuzz page. (There were a couple of Rust FizzBuzzes there already, but they didn’t use pattern matching.)