Most software developers have encountered the Fizz Buzz interview question at some point in their career, because we can, we'll use the Type System in TypeScript to solve it with zero runtime code.

Watch the video

Coming soon...

It's possible to solve the FizzBuzz interview question using TypeScripts type system alone, without any run time code. I'm going to show you how.

The rules of FizzBuzz are simple:

For each number between 1 and a given number, print:

"Fizz" if the number is divisible by 3
"Buzz" if the number is divisible by 5
"FizzBuzz" if the number is divisible by 3 and 5
Otherwise print the number

In normal sane typescript this would be easy enough, something like:

function fizzbuzz(n: number): void {
  for (let i = 1; i <= n; i++) {
    if (i % 15 === 0) {
      console.log("FizzBuzz");
    } else if (i % 3 === 0) {
      console.log("Fizz");
    } else if (i % 5 === 0) {
      console.log("Buzz");
    } else {
      console.log(i);
    }
  }
}

But this isn't all that interesting, instead I want a Type that can do this. I want this wall of types:

type FizzBuzzRange<
  A extends number, 
  B extends number, 
  Tuple extends unknown[] = []
> = A extends B
  ? Tuple
  : FizzBuzzRange<Add<A, 1>, B, [...Tuple, FizzBuzz<A>]>

type FizzBuzz<N extends number> = And<IsDivisibleBy3<N>, IfDivisibleBy5<N>>
  ? "FizzBuzz"
  : IsDivisibleBy3<N> extends true
      ? "Fizz"
      : IfDivisibleBy5<N> extends true
        ? "Buzz"
        : N

Lets build this piece by piece.

Prerequisite knowledge

You are going to need to know about:

Generics
Conditional types

So this syntax should make sense:

type HelloOrGoodbye<T extends boolean> = 
  T extends true 
    ? "Hello"
    : "Goodbye"

Basically we take a generic type T that's a boolean, if T extends true, which we'll equate to equals true, we return "Hello" otherwise we return false.

Inference within conditional types

type Flatten<T> = T extends Array<infer Item> ? Item : T;

Here we're saying if our generic type T is an array, we want to get back the type of whats inside the array, otherwise give back T itself. The infer keyword is going to be really helpful to us when building types.

Variadic tuple types

Sounds complicated, but isn't really. This can be thought of as similar to the spread operator working on arrays in JavaScript. Think:

type Concat<A extends any[], B extends any[]> = [...A, ...B]

Here we're combining two tuples together by "spreading" both.

A whole bunch of recursion

Since we don't have loops in the type system. we're going to be using a lot of recursion

The start

Lets break the FizzBuzz problem down to it's core, it's basically can you use the modulo operator? If we could build a Modulo operator in typescript, we'd be able to solve the problem

So assuming we can't use %, how would we build mod?

Well one way that makes sense to me, and a way that's going to work well for our use case is:

function isDivisibleBy(a, b) {
  let counter = b;

  while (a >= counter) {
    if (counter === a) {
      return 0;
    }
    counter += b;
  }
  return a - (counter - b);
}

A worked example would make sense:

For mod(9, 3)

We start a counter off at 3, then we loop until that counter is bigger than 10, adding three to the counter each time round the loop. Inside the loop we check if our counter === a, if it does we return 0. The first time through the loop a = 9, counter = 3, so this isn't met, the second time through a = 9, counter = 6, the third time however, a = 9, counter = 9, so we'll return the 0, indicating a 0 remainder

For the example mod(10, 3) We'll keep adding 3 to the counter until it reaches 12, at this point 12 is bigger than 10 so we exit the loop. We then need to work out the remainder. We take 3 off 12 to get back to the iteration before, then we do 10 - 9 to work out the remainder.

We know we don't have loops in the type system, but we do have recursion! So before we try and turn that into a type, lets build it with recursion:

function modulo(a, b, counter = b) {
  if (counter === a) {
    return 0
  }
  if (a < counter) {
    return a - (counter - b);;
  }
  return modulo(a, b, (counter += b));
}

This is the exact same algorithm. Ok great. No lets turn that into a Type!

type Modulo<A extends number, B extends number, Counter extends number = B> = 
  A extends Counter 
    ? 0
    : A < Counter extends true 
      ? A - (Counter - B)
      : Modulo<A, B, Counter + B>

Here we're using extends to mean equals, that's not quite true but it's good enough for us.

I haven't lost the plot, this type isn't going to work. There are 3 problems with it.

Add, LessThan and Minus. We can't use normal operators in our types. We need to find some way of creating types that work like the operators do.

Lets start with Add, as it's the base of the rest.

Lets assume we want to build a type that when given two numbers returns the result of adding them:

type Add<A extends number, B extends number> = ??

Add<1, 2> // 3
Add<9, 3> // 12

Is the goal, we need to come up with a plan.

Adding is like combining two numbers, we can't add two numbers but we can combine two things, tuples!

Imagine we had this code in TS:

function combine_arrays(a : unknown[], b: unknown[]) : unknown[] {
  return [...a, ...b]
}

A function that takes two arrays and returns a new array with all the elements from both.

Now if we asked for the length of that new array... it would be the length of array a + array b.

So this is how we could tackle Add. We can combine two tuples into one using variadic tuple types just like we can in JavaScript. If we had a Type that could turn a number into a tuple of that length, and a Type that could return the length of a tuple, we could have a way of building Add.

Lets work on the easy part first, a type that can return the Length of a tuple;

type Length<A extends unknown[]> = A extends { length: infer L} ? L : never

We use a conditional type to infer the length of the tuple and return that.

Now we need a way of building a tuple of a given length. We'll start with a number and aim to build a tuple that includes all of the numbers up to that number, for example:

type Range<5> = [0, 1, 2, 3, 4]
type Range<7> = [0, 1, 2, 3, 4, 5, 6]

We've called it Range as that's pretty much what it's doing. How would we build that?

type Range<N extends number> = ???

Lets take the same approach, build a recursive solution in JS and then turn it into a type:

function range(n, tuple=[]) {
  if (tuple.length === n) {
    return tuple;
  }
  return range(n, [...tuple, tuple.length])
}

So we're going to keep growing the tuple by adding a number representing the current length of it and eventually we'll return the tuple when it's the length expected.

In TypeScript that looks like a fairly simple recursive type:

type Range<N extends number, Tuple extends number[] = []> = Length<Tuple> extends N
  ? Tuple
  : Range<N, [...Tuple, Length<Tuple>]>;

So now, building Add is fairly simple, we create a type called Add that takes two numbers,

type Add<A extends number, B extends number> = ???

Then we turn those numbers into tuples with their respective lengths, and we combine them together into one tuple:

type Add<A extends number, B extends number> = [...Range<A>, ...Range<B>];

And finally we return the length using out Length type:

type Add<A extends number, B extends number> = Length<[...Range<A>, ...Range<B>]>;

Ok so looking back at our modulo type, we can now fix it up a little:

type Modulo<A extends number, B extends number, Accumulator extends number = B> = 
  A extends Accumulator 
    ? 0
    : A < Accumulator extends true 
      ? A - (Accumulator - B)
      : Modulo<A, B, Accumulator + B>

The + can be replaced by our new Add type:

type Modulo<A extends number, B extends number, Accumulator extends number = B> = 
  A extends Accumulator
    ? 0
    : A < Accumulator extends true 
      ? A - (Accumulator - B)
      : Modulo<A, B, Add<Accumulator + B>>

Our Modulo type looks better now, but we still have two problems, the < sign and the subtraction. Lets focus on the < less than since this is going to be pretty easy to build.

Ideally we'd like a type that we can use like so:

LessThan<A, B>; // boolean

It should take two numbers and return a boolean if A is less than B. But how should we build less than?

Your first instinct might be subtract a from b, and see if that is less than zero. But if we do that we're not closer to being able to build our type in the type system.

Instead, lets think about what we have built so far with our Range type.

If we turn B into the Range, if A exists inside that tuple then it must be less than B, Example time:

// LessThan<2, 5> // Range<5> = [0, 1, 2 ,3, 4] // 2 extends Range<5> // true

A case where it isn't less than:

// LessThan<5, 5> // Range<5> = [0, 1, 2, 3, 4] // 5 extends Range<5> // false as 5 is not less than 5

Ok, we should be able to build that!

type LessThan<A extends number, B extends number> =
  A extends Range<B> ? true : false

But this isn't quite right, for example:

// LessThan<1, 2>

The condition is saying is 1 assignable to [1, 2], but that doesn't quite work, instead we need to turn the tuple into a union type to ask if a number is inside it.

// 1 is assignable to 1 | 2

We can do that with the [number] syntax, so Range<A>[number] would create a union 0 | 1 | 2 | 3

We have to write this in two steps to stop TypeScript getting confused:

type LessThan<
  A extends number,
  B extends number,
  BRange extends number[] = Range<B>
> = A extends BRange[number] ? true : false

Ok so now back to Modulo, lets replace our < with our new LessThan type:

type Modulo<A extends number, B extends number, Counter extends number = B> = 
  A extends Counter 
    ? 0
    : LessThan<A, Counter> extends true 
      ? A - (Counter - B)
      : Modulo<A, B, Add<Counter + B>>

So now there's just one issue left, subtract. Now here me out, we don't actually need subtract to get FizzBuzz working. We don't need to know the modulo to get FizzBuzz working, we only need to know if A is divisible by B or not. We don't need the remainder.

If we change our expectations to only get back true or false from this type, we're actually there. If we change the name to IsDivisible, and change our returns, we're there:

type IsDivisible<A extends number, B extends number, Accumulator extends number = B> = 
  A extends Accumulator
    ? true
    : LessThan<A, Accumulator> extends true 
      ? false
      : IsDivisible<A, B, Add<Accumulator + B>>

Lets try it out:

We can now build two new types for IsDivisibleBy3 and IsDivisibleBy5:

type IsDivisibleBy3<A extends number> = IsDivisible<A, 3>
type IsDivisibleBy5<A extends number> = IsDivisible<A, 5>

An aside, this is kinda like partial application, if that's your thing.

We can now go back to the initial problem, FizzBuzz. We had this type:

type FizzBuzz<N extends number> = IsDivisibleBy3<N> extends true ???

And we now have that type!

Lets return Fizz if its divisible by 3, otherwise return the number passed in:

type FizzBuzz<N extends number> = IsDivisibleBy3<N> extends true
  ? "Fizz"
  : N

Now we can add the IfDivisibleBy5 in as a nested conditional type:

type FizzBuzz<N extends number> = IsDivisibleBy3<N> extends true
  ? "Fizz"
  : IfDivisibleBy5<N> extends true
    ? "Buzz"
    : N

Now, the final piece of the puzzle. How do we do &&

IsDivisibleB  y3<N> && IfDivisibleBy5<N>

Well, we build a type of course:

We can build a type called And that takes two generics, and returns true if both of them evaluate to true, and false otherwise:

type And<A extends boolean, B extends boolean> = A extends true
  ? B extends true 
    ? true 
    : false
  : false

So if A and B are true, we return true, if A is true but B is false we return false, and if A is false, we return false

We can use that type like:

type FizzBuzz<N extends number> = And<IsDivisibleBy3<N>, IfDivisibleBy5<N>>
  ? "FizzBuzz"
  : IsDivisibleBy3<N> extends true
      ? "Fizz"
      : IfDivisibleBy5<N> extends true
        ? "Buzz"
        : N

And that should be a working type, it takes a number and returns either FizzBuzz, Fizz, Buzz or the number passed in.

Now, the final final puzzle piece, we want to build a type that can generate a tuple of FizzBuzzes over a range. For example:

FizzBuzzRange<1, 10>

Should generate the tuple:

// [1, 2, "Fizz", 4, "Buzz", "Fizz", 7, 8, "Fizz"]

This should be quite simple using everything we have learnt so far:

We know we're going to use recursion to build up the tuple, so we know we'll take a third param in our type that eventually will get returned:

type FizzBuzzRange<
  A extends number, 
  B extends number, 
  Tuple extends unknown[] = []
> = ???

Now if we add one to A each time through our "loop" and return when A is equal to B, we'd have the base case of our recursion:

type FizzBuzzRange<
  A extends number, 
  B extends number, 
  Tuple extends unknown[] = []
> = A extends B
  ? Tuple
  : ???

If A doesn't equal B, then we need to recursivly call our type again, adding the result of calling FizzBuzz to our tuple, and also incrementing A by one:

type FizzBuzzRange<
  A extends number, 
  B extends number, 
  Tuple extends unknown[] = []
> = A extends B
  ? Tuple
  : FizzBuzzRange<Add<A, 1>, B, [...Tuple, FizzBuzz<A>]>

And that's it, FizzBuzz built completely in the type system, zero run time typescript. Beautiful, but please never do this.

Nick Angeli

Fizz Buzz using the TypeScript Type System

Watch the video

Prerequisite knowledge

The start