Type level Haskell: FizzBuzz

Introduction

We'll start with some arithmetic. We can define Nat to be the type of natural numbers, and implement an addition function. By evaluating this function in GHCi we can compute additions of natural numbers. If we try to add, say, a string and a float, we quite naturally get a type error.

Moving on, we try something else.

What's going on here? It looks like we've computed the sum of two numbers. But we haven't defined any functions, or even values, just types and instances of type classes.

Let's take a closer look. We first define two types, Z and S n with no constructors, so the only value they have is the bottom value undefined. Then we declare a type class Add a b c that implements a single method add :: a- > b -> c. There are two things to note here:

  1. Unlike the type class Eq x, Add a b c has three parameters. This isn't supported in base Haskell, so we have to add a language extension. Now, just as we can think of single-paramater type classes as sets of types, we can think of n-paramater type classes as n-ary relations on types.

  2. We've given Add a b c the functional dependency a b -> c. This means that, given any two types x and y, Haskell will only allow an instance Add x y z for one type z. In other words, the 3-ary relation on types Add is actually a (partial) function Type -> Type -> Type. This means that Haskell is ably to fully infer the type of the first expression. Type checking the second expression doesn't give a type error, since it is possible that there is an instance of Add String Float c defined somewhere in another module, but because it can't see any such instance, it isn't able to fully infer the type.

In this way, we have translated our computation to the type level. Can we do this with more complicated computations?

FizzBuzz

The FizzBuzz test is a much-blogged-about interview question. It goes like this:

Write a program that prints the numbers from 1 to 100. But for multiples of three print “Fizz” instead of the number and for the multiples of five print “Buzz”. For numbers which are multiples of both three and five print “FizzBuzz”.

Here's a Haskell solution:

We get the answer by evaluating fizzbuzz 100

It's not a particularly nice solution, but it lends itself nicely to translation to the type level. Let's jump right in!

It looks like we're going to need:

  • Integers
  • Lists
  • Booleans
  • Strings

Although we can actually get away with only natural numbers, and just three strings... (The latter because type level lists as defined above are heterogeneous, so we can put "numbes" and "strings" in the same list.)

Now the functions we have to translate are fizzes, buzzes, &&, decide, map, list comprehensions, and fizzbuzz. The first few of these are straightforward:

We do decide in two steps:

The case of map :: (a -> b) -> [a] -> [b] seems a little trickier, but thankfully we don't really need map, just map decide, which makes things simpler:

Similarly, we don't need full list comprehensions, just a function first :: Integer -> [Integer] that generates the first n natural numbers (first n = [1..n]). We'll need a helper function that adds elements to the back of a list for this.

Finally we put it all together:

Let's check our work in GHCi. Starting with some small numbers, everything looks good—or at least, correct.

Going up to 100 takes a little longer - about 34 seconds on my machine. Trying n=150 takes even more time (3:26 minutes), and n=200 took around 15 minutes. This suggests that our algorithm has exponential time complexity. Although Haskell's type system is very powerful, we might be better off performing computations in Haskell itself.

Click here to go back.

Copyright © 2020 Daniel Mroz