An exercise in missing the point: FizzBuzz as a Typescript type
Early in my career, a new puzzle entered the software engineering zeitgeist: FizzBuzz.
First popularized by Imran Ghory’s (now defunct) blog, this was initially proposed as an interview question that could be used to screen out completely unqualified software engineering candidates :
After a fair bit of trial and error I’ve come to discover that people who struggle to code don’t just struggle on big problems, or even smallish problems (i.e. write a[n] implementation of a linked list). They struggle with tiny problems1.
So I set out to develop questions that can identify this kind of developer and came up with a class of questions I call “FizzBuzz Questions” named after a game children often play (or are made to play) in schools in the UK.
While Imran’s point was that a solid engineer should be able to effortlessly write a straightforward solution to this problem, many of his readers took the idea in an entirely different direction, filling message boards with increasingly obscure, clever, and absurd solutions, simply for the joy of it. I recall being particularly amused by one that used C++ template metaprogramming to get the compiler itself to print the solution in its diagnostic messages…
…And perhaps you can see where this is going.
A while ago, having seen all of the control flow structures that have been added to Typescript’s type system, I began to wonder if it would be possible to induce the Typescript compiler to compute the result of FizzBuzz as a type.
The rules, revisited
As typically stated, the rules of FizzBuzz are
Count from 1 to 100 (inclusive), and for each value…
if the number is divisible by 3, print ‘fizz’
if the number is divisible by 5, print ‘buzz’
if the number is divisible by both 3 and 5, print ‘fizzbuzz’
otherwise, print the number itself
TypeScript doesn’t have the ability to perform side effects—like printing—at compile time, so we’ll need to modify the rules a little bit in order to have an achievable goal. Here’s what I landed at as my target:
Create a Typescript type alias that evaluates to a tuple with 100 elements. Each element should either be a numeric literal or one of the literal strings
'fizz','buzz', and'fizzbuzz', as they would be computed in the FizzBuzz problem.For a bit of flair, construct this in a way that makes it easy to generate “FizzBuzz” sequences of arbitrary length.
First problem: basic arithmetic
While Typescript has some sophisticated options for manipulating string literals, they never baked arithmetic into the type system because really, who would even want that?
…me, apparently.
While for a while, this seemed like it would be an absolute non-starter, I eventually noticed a loophole:
If you ask the type system for the length of a tuple, you get back a numeric literal!
type zeroLength = []['length'];type oneLength = [never]['length'];type twoLength = [never, never]['length'];
| The type alias… | is evaluated as… |
|---|---|
| zeroLength | 0 |
| oneLength | 1 |
| twoLength | 2 |
This opens all sorts of doors: we can now represent any2 non-negative
integer with a tuple of the same length. Since it doesn’t really matter what we
put in the tuple, as long as it has the desired length. Since we don’t want to
actually use these at runtime, I’m going to stick with putting never in them,
which helps to emphasize their lack of utility for any real purpose.
This also gives us a really straightforward way to add two numbers together: just concatenate them!
type add<left extends never[], right extends never[]> = [...left, ...right];
type twoPlusThree = add<[never, never], [never, never, never]>;type twoPlusThreeLength = twoPlusThree['length'];
| The type alias… | is evaluated as… |
|---|---|
| twoPlusThree | [never, never, never, never, never] |
| twoPlusThreeLength | 5 |
But even this simple example shows us that it’s going to be a huge pain if we have to manually encode each number as a tuple. To help with that let’s build a couple of utility types:
type increment<value extends never[]> = add<value, [never]>;
type numberToTuple< value extends number, accumulator extends never[] = [],> = value extends accumulator['length'] ? accumulator : numberToTuple<value, increment<accumulator>>;
type two = numberToTuple<2>;type five = numberToTuple<5>;
| The type alias… | is evaluated as… |
|---|---|
| two | [never, never] |
| five | [never, never, never, never, never] |
Here, we make use of Typescript’s support for conditional types to build a recursive type. Asking Typescript to build up tuples one by one certainly doesn’t seem like a great idea for compiler performance in a production environment, but given that we’re already deliberately pushing the boundaries of what’s even possible in the type system, this’ll do!3
If this is an unfamiliar language construct, you may be surprised by the
presence of the extends keyword as part of the condition. This usage bears a
little bit more explanation, as it’s going to pop up repeatedly as we build up
the tools needed to solve this problem.
To understand what’s going on here, it might be better to start with the other
usages of extends that we’ve seen in this example, which are the
generic constraints
applied to our types. Even if you’re unfamiliar with this feature, the context
alone may be enough to build the intuition that this bit of code would be
prohibited:
type constraintDemo<value extends number> = [];type invalid = constraintDemo<'abc'>;
ts(2344): Type 'string' does not satisfy the constraint 'number'.And sure enough, it is!
Although we have an entire keyword for constraints, if you squint at this example, you can probably see the similarities with a much more familiar looking bit of code:
function methodWithParameter(value: number) {}
methodWithParameter('abc');
ts(2345): Argument of type 'string' is not assignable to parameter of type 'number'.While constraints have some extra tricks up their sleeves, they’re very similar in principle to parameter type annotations, and if you start with this as your mental model, it’ll take you pretty far.
So what about the extends inside the conditional type?
The logic for how the compiler interprets these is similar, but in this case, a
failure to apply the constraint doesn’t cause a compiler error! Instead, we
choose a branch of the condition based on whether or not the constraint
application succeeds. Moreover, within each of the branches, the expression on
the left hand of the extends will be narrowed in the same way that the
compiler does when you perform a conditional type check of a variable inside of
a method.
In the case of our numberToTuple example, we’re using extends to determine
whether the length of our tuple has reached a particular length. It can be
difficult to develop an intuitive sense for what’s going on when the literal
types are being obscured by type parameters, so here are a few examples of the
sorts of comparisons we’re doing:
type fiveExtendsThree = 5 extends 3 ? 'yes' : 'no';
type fiveExtendsFive = 5 extends 5 ? 'yes' : 'no';
type fiveExtendsNumber = 5 extends number ? 'yes' : 'no';
type numberExtendsFive = number extends 5 ? 'yes' : 'no';
type tupleHasLengthTwo = 2 extends [never, never]['length'] ? 'yes' : 'no';
| The type alias… | is evaluated as… |
|---|---|
| fiveExtendsThree | "no" |
| fiveExtendsFive | "yes" |
| fiveExtendsNumber | "yes" |
| numberExtendsFive | "no" |
| tupleHasLengthTwo | "yes" |
Another interesting thing that we can explore here are some of the deliberate limitations that the Typescript language designers have baked into the language. The introduction of recursively computed types in the type system also brought with it the possibility of infinite loops, and since nobody likes a compiler that hangs indefinitely or crashes as a result of stack overflow, the compiler will cut you off at a certain point. As of Typescript 5.6.3, we can’t use this technique to build a tuple containing more than 999 elements:
type nineHundredNinetyNineWorks = numberToTuple<999>;type oneThousandFails = numberToTuple<1000>;
ts(2589): Type instantiation is excessively deep and possibly infinite.But again, since our goal is to compute the first 100 elements of FizzBuzz, this won’t be a problem for us!
Comparisons
Since we’re going to need to build our own implementations of the rest of the arithmetic operations, we’d be well served by first building a way to compare two values. Again, we’re probably going to need to reach for conditional types, so let’s see if a straightforward usage will tell us anything:
type bigExtendsSmall = numberToTuple<5> extends numberToTuple<3> ? 'yes' : 'no';
type smallExtendsBig = numberToTuple<3> extends numberToTuple<5> ? 'yes' : 'no';
type bigExtendsBig = numberToTuple<5> extends numberToTuple<5> ? 'yes' : 'no';
| The type alias… | is evaluated as… |
|---|---|
| bigExtendsSmall | "no" |
| smallExtendsBig | "no" |
| bigExtendsBig | "yes" |
We can see that equality works here, but there’s nothing that distinguishes the other two results from one another. This actually follows the same behavior that we’d get using typed method parameters: if we say that a method takes a tuple with three elements, it must always get exactly three elements!
function methodAcceptingTuple(tuple: [string, string, string]) {}
const largerTuple: [string, string, string, string] = ['a', 'b', 'c', 'd'];
methodAcceptingTuple(largerTuple);
ts(2345): Argument of type '[string, string, string, string]' is not assignable to parameter of type '[string, string, string]'.
Source has 4 element(s) but target allows only 3.However, if we pull out the spread operator, we can see some more interesting results:
type bigIncludesSmall = numberToTuple<5> extends [...numberToTuple<3>, ...never[]] ? 'yes' : 'no';
type smallIncludesBig = numberToTuple<3> extends [...numberToTuple<5>, ...never[]] ? 'yes' : 'no';
type bigIncludesBig = numberToTuple<5> extends [...numberToTuple<5>, ...never[]] ? 'yes' : 'no';
| The type alias… | is evaluated as… |
|---|---|
| bigIncludesSmall | "yes" |
| smallIncludesBig | "no" |
| bigIncludesBig | "yes" |
In this case, we’re asking if the array on the left contains at least a certain number of elements, and now we get some more useful results. If we apply the comparison in both directions and wrap it in a helper type, we get a comparison operator:
type compare<left extends never[], right extends never[]> = left extends [...right, ...never[]] ? right extends [...left, ...never[]] ? 'equalTo' : 'greaterThan' : 'lessThan';
type bigCompareSmall = compare<numberToTuple<5>, numberToTuple<3>>;type smallCompareBig = compare<numberToTuple<3>, numberToTuple<5>>;type bigCompareBig = compare<numberToTuple<5>, numberToTuple<5>>;
| The type alias… | is evaluated as… |
|---|---|
| bigCompareSmall | "greaterThan" |
| smallCompareBig | "lessThan" |
| bigCompareBig | "equalTo" |
Now we’re cooking!
Subtraction
The way that we built comparisons leads neatly into handling subtraction,
although doing so will require us to make use of a new keyword: infer.
Within a condition, infer allows us to perform a sort of pattern matching: on
the right hand side of the extends, use use infer and a new identifier as a
placeholder somewhere within the expression. In the “success” branch of the
condition, the identifier will be mapped to whatever type would be necessary to
make the condition successful.
A few concrete examples will probably make this much clearer:
type arrayElement<t> = t extends Array<infer element> ? element : never;
type normalArrayElement = arrayElement<number[]>;type tupleArrayElement = arrayElement<[string, number]>;type notArrayElement = arrayElement<{ foo: string }>;
| The type alias… | is evaluated as… |
|---|---|
| normalArrayElement | number |
| tupleArrayElement | string | number |
| notArrayElement | never |
In this case, it’s clear that the helper type arrayElement<t> is expecting an
array type—and we could have even put a contraint on the type parameter if we
wanted the notArrayElement declaration to result in an error—but conditional
types are required to include a failure branch, and using never is a common
convention in the Typescript community to signal that there’s no meaningful
result when the condition fails.
If we combine infer with the spread operator, we can use it to split tuples
and collect either prefixes or suffixes!
type tuplePrefix = [string, number, boolean] extends [...infer rest, boolean] ? rest : never;
type tupleSuffix = [string, number, boolean] extends [string, ...infer rest] ? rest : never;
| The type alias… | is evaluated as… |
|---|---|
| tuplePrefix | [string, number] |
| tupleSuffix | [number, boolean] |
And this leads directly into a way to perform subtraction: the result of subtraction is whatever’s left in the suffix after matching a particular prefix:
type subtract<left extends never[], right extends never[]> = left extends [...right, ...infer rest] ? rest : never;
type fiveMinusThree = subtract<numberToTuple<5>, numberToTuple<3>>;
type fiveMinusTwo = subtract<numberToTuple<5>, numberToTuple<2>>;
type threeMinusFive = subtract<numberToTuple<3>, numberToTuple<5>>;
| The type alias… | is evaluated as… |
|---|---|
| fiveMinusThree | [never, never] |
| fiveMinusTwo | [never, never, never] |
| threeMinusFive | never |
Due to our limitation of only being able to handle non-negative integers, we don’t have a meaningful result when the right hand side is greater than the left hand side, but we won’t need that in order to solve FizzBuzz, so it’s time to move on!
Modulo
To know whether a dividend is “evenly divisible” by divisor, we need modulo, and now that we have comparison and subtraction, we can implement this operation in terms of those:
if the dividend is less than the divisor, the modulo is the dividend itself
otherwise, perform the modulo operation with the dividend minus the divisor
This implementation isn’t going to win any beauty contests, but it gets the job done:
type modulo<dividend extends never[], divisor extends never[]> = compare<dividend, divisor> extends 'lessThan' ? dividend : modulo<subtract<dividend, divisor>, divisor>;
type sixModFour = modulo<numberToTuple<6>, numberToTuple<4>>;type twentyThreeModFive = modulo<numberToTuple<23>, numberToTuple<5>>;
| The type alias… | is evaluated as… |
|---|---|
| sixModFour | [never, never] |
| twentyThreeModFive | [never, never, never] |
Putting it together
So far, we’ve figured out how to
Turn a non-negative integer into a form that can be manipulated in the the type system
Turn that form back into a number
Add two numbers
Increment a number
Compare two numbers
Subtract one number from another
Perform modulo
This should be enough arithmetic to solve FizzBuzz, so let’s start digging into the details.
Computing a single element of FizzBuzz
For a single element, we need to perform the modulo operator for both 3 and 5, then emit results handling the cases in which both, either, or neither evenly divide the current element.
Here’s one way to do that:
type fizzBuzzElement<value extends never[]> = [ modulo<value, numberToTuple<3>>, modulo<value, numberToTuple<5>>, ] extends [infer modThree, infer modFive] ? [modThree, modFive] extends [[], []] ? 'fizzbuzz' : modThree extends [] ? 'fizz' : modFive extends [] ? 'buzz' : value['length'] : never;
type singleResultSeven = fizzBuzzElement<numberToTuple<7>>;type singleResultTen = fizzBuzzElement<numberToTuple<10>>;type singleResultFifteen = fizzBuzzElement<numberToTuple<15>>;type singleResultTwentySeven = fizzBuzzElement<numberToTuple<27>>;
| The type alias… | is evaluated as… |
|---|---|
| singleResultSeven | 7 |
| singleResultTen | "buzz" |
| singleResultFifteen | "fizzbuzz" |
| singleResultTwentySeven | "fizz" |
Although there are no new language elements in this snippet, I do put them together in some new ways:
The outer condition in this type is one that always succeeds: I build a tuple of
two elements and then infer each of them. This technique works similarly to
assigning const values inside of a method: we perform a computation and then
assign a name to it so that we can use it by name in the remainder of the body,
rather than needing to repeatedly run—and write out—the code for the
computation.
The rest of this uses language features that we’ve already discussed—although the nested conditions can get a bit dense—so I won’t belabor this part any further.
Building a sequence
There’s not much left to do at this point!
We need to build up a sequence of elements one by one, which we already saw how
to do when we created numberToTuple. However, in this case, rather than
putting never inside the sequence, we have to compute a value based on the
“current index” of the iteration.
Here’s a solution that uses accumulators for both the sequence and the “current index” concept:
type fizzBuzzSequence< length extends number, currentIndex extends never[] = [], result extends unknown[] = [],> = result['length'] extends length ? result : fizzBuzzSequence< length, increment<currentIndex>, [...result, fizzBuzzElement<increment<currentIndex>>] >;
type fizzBuzzFifteen = fizzBuzzSequence<15>;
| The type alias… | is evaluated as… |
|---|---|
| fizzBuzzFifteen | [1, 2, "fizz", 4, "buzz", "fizz", 7, 8, "fizz", "buzz", 11, "fizz", 13, 14, "fizzbuzz"] |
All that’s left to do at this point is to generate it with a hundred elements!
type fizzBuzz = fizzBuzzSequence<100>;
| The type alias… | is evaluated as… |
|---|---|
| fizzBuzz | [1, 2, "fizz", 4, "buzz", "fizz", 7, 8, "fizz", "buzz", 11, "fizz", 13, 14, "fizzbuzz", 16, 17, "fizz", 19, "buzz", "fizz", 22, 23, "fizz", "buzz", 26, "fizz", 28, 29, "fizzbuzz", 31, 32, "fizz", 34, "buzz", "fizz", 37, 38, "fizz", "buzz", 41, "fizz", 43, 44, "fizzbuzz", 46, 47, "fizz", 49, "buzz", "fizz", 52, 53, "fizz", "buzz", 56, "fizz", 58, 59, "fizzbuzz", 61, 62, "fizz", 64, "buzz", "fizz", 67, 68, "fizz", "buzz", 71, "fizz", 73, 74, "fizzbuzz", 76, 77, "fizz", 79, "buzz", "fizz", 82, 83, "fizz", "buzz", 86, "fizz", 88, 89, "fizzbuzz", 91, 92, "fizz", 94, "buzz", "fizz", 97, 98, "fizz", "buzz"] |
And we’re done! 🎉
Appendix: What if 999 isn’t enough?
Although we didn’t need to go beyond 999 for this exercise, the question of whether it would be possible to build even longer sequences has certainly occurred to me. In fact, when I first started thinking about this problem, the naïve solution of building up a single element at a time stopped working well before 100 because the execution depth limit was considerably stingier.
One of the ideas that I had was to try doubling the length of the tuple on each iteration, which would cut the time complexity for conversion down to logarithmic.
But this leads to a dilemma: how do we know when to stop? Our previous
implementation of compare assumes that you’ve already converted both numbers
to tuples, which would place us in a Catch-22 if we tried to use it here.
Then I remembered keyof.
When applied to any other type keyof produces a union of all of the values
that can be used to index into that type. Here’s a quick example:
type basicKeyOfDemo = keyof { foo: number; bar: string };
| The type alias… | is evaluated as… |
|---|---|
| basicKeyOfDemo | "foo" | "bar" |
Although it’s usually used for object types, there’s nothing that prevents it from being used for other types, like arrays! However, this gives us back all of the keys that can be used on arrays, including all of the available methods.
To clear out some of the noise, let’s make a little helper:
type numericKeys<tuple extends unknown[]> = Exclude<keyof tuple, keyof []>;
type smallArrayNumericKeys = numericKeys<[string, number, boolean]>;
| The type alias… | is evaluated as… |
|---|---|
| smallArrayNumericKeys | "0" | "1" | "2" |
Here, we exclude from the union all of the keys that are available on an empty array, which leaves us only with the numbers themselves. Interestingly, Typescript stringifies these, but if we already have a number, it’s trivial to stringify it for the sake of equality comparison:
type stringifyNumber<value extends number> = `${value}`;
type zeroString = stringifyNumber<0>;type oneString = stringifyNumber<1>;type twoString = stringifyNumber<2>;
| The type alias… | is evaluated as… |
|---|---|
| zeroString | "0" |
| oneString | "1" |
| twoString | "2" |
This gives us the tools that we need to build a comparison between a number
value and a tuple: if the tuple’s numeric keys include the value, then the value
is strictly less than the tuple.
type isLessThan<left extends number, right extends never[]> = stringifyNumber<left> extends numericKeys<right> ? true : false;
type threeLessThanFive = isLessThan<3, numberToTuple<5>>;type fiveLessThanThree = isLessThan<5, numberToTuple<3>>;type threeLessThanThree = isLessThan<3, numberToTuple<3>>;
| The type alias… | is evaluated as… |
|---|---|
| threeLessThanFive | true |
| fiveLessThanThree | false |
| threeLessThanThree | false |
We could potentially use this to build a tuple representing the first power of two that is greater than or equal to a target value:
type powerOfTwoAtLeastAsGreatAs< value extends number, accumulator extends never[] = [never]> = isLessThan<value, increment<accumulator>> extends false ? powerOfTwoAtLeastAsGreatAs<value, add<accumulator, accumulator>> : accumulator;
type atLeastAsBigAsZero = powerOfTwoAtLeastAsGreatAs<0>['length'];type atLeastAsBigAsTwentyFour = powerOfTwoAtLeastAsGreatAs<24>['length'];type atLeastAsBigAsThirtyTwo = powerOfTwoAtLeastAsGreatAs<32>['length'];
| The type alias… | is evaluated as… |
|---|---|
| atLeastAsBigAsZero | 1 |
| atLeastAsBigAsTwentyFour | 32 |
| atLeastAsBigAsThirtyTwo | 32 |
Since we only have a less than operator, we increment our accumulator for the comparison in order to get the result of “greater than or equal to”.
Now that we have the ability to build up a power of two large enough to “fit” a particular value, we’re closing in on a strategy that might be familiar to folks who have had to do bit manipulation:
Build a list of all the powers of two up to the one that can “fit” the target value.
Initialize an accumulator tuple representing 0.
Loop through the powers of two in descending order, and add each value to the accumulator if the result would be less than the target value.
In this algorithm, we treat each of the powers of two as a single bit, and we flip all of the bits necessary to equal our target value.
First, we need the sequence generator:
type powerOfTwoSequenceLargeEnoughToFit< value extends number, powersOfTwo extends unknown[] = [[never]],> = powersOfTwo extends [...unknown[], infer lastPowerOfTwo] ? lastPowerOfTwo extends never[] ? isLessThan<value, increment<lastPowerOfTwo>> extends false ? powerOfTwoSequenceLargeEnoughToFit< value, [...powersOfTwo, add<lastPowerOfTwo, lastPowerOfTwo>] > : powersOfTwo : never : never;
type sequenceForFour = powerOfTwoSequenceLargeEnoughToFit<4>;
| The type alias… | is evaluated as… |
|---|---|
| sequenceForFour | [[never], [never, never], [never, never, never, never]] |
Then, we need the ability to loop through one of these sequences to build up our target value.
type buildValueFromPowersOfTwo< value extends number, powersOfTwo extends unknown, accumulator extends never[] = [],> = powersOfTwo extends [...infer earlierPowersOfTwo, infer lastPowerOfTwo] ? lastPowerOfTwo extends never[] ? isLessThan<value, add<accumulator, lastPowerOfTwo>> extends false ? buildValueFromPowersOfTwo< value, earlierPowersOfTwo, add<accumulator, lastPowerOfTwo> > : buildValueFromPowersOfTwo<value, earlierPowersOfTwo, accumulator> : never : accumulator;
type seven = buildValueFromPowersOfTwo< 7, [[never], [never, never], [never, never, never, never]]>;type sevenLength = seven['length'];
| The type alias… | is evaluated as… |
|---|---|
| seven | [never, never, never, never, never, never, never] |
| sevenLength | 7 |
Finally, we can put the pieces together:
type numberToLargeTuple<value extends number> = buildValueFromPowersOfTwo< value, powerOfTwoSequenceLargeEnoughToFit<value> >;
type nine = numberToLargeTuple<9>;type nineLength = nine['length'];
| The type alias… | is evaluated as… |
|---|---|
| nine | [never, never, never, never, never, never, never, never, never] |
| nineLength | 9 |
So this appears to work, but the big test is whether we can build sequences larger than 999:
type oneThousand = numberToLargeTuple<1000>['length'];
| The type alias… | is evaluated as… |
|---|---|
| oneThousand | 1000 |
However, we eventually reach an altogether different limit, which is the maximum size of a tuple in Typescript. As of Typescript 5.6.3, this is our limit with this approach:
type length8191Works = numberToLargeTuple<8191>['length'];type length8192Fails = numberToLargeTuple<8192>['length'];
ts(2799): Type produces a tuple type that is too large to represent.Interestingly, though, we can build numbers larger than 8,191: the error reported here is caused when the underlying helpers try to build a tuple of length 16,384. As of Typescript 5.6.3, we can build tuples with over 9,000 elements:
type addLargeTuples = add< numberToLargeTuple<8191>, numberToLargeTuple<1808>>['length'];
| The type alias… | is evaluated as… |
|---|---|
| addLargeTuples | 9999 |
But it breaks when we try to go to 10,000:
type pastTheLimit = add< numberToLargeTuple<8191>, numberToLargeTuple<1809>>['length'];
ts(2799): Type produces a tuple type that is too large to represent.And that’s about as far as I’ve taken this excursion. I’ve had some ideas about
how this approach could be extended to support negative numbers and values
larger than 8,191, but I have no idea how to get those representations back to
a number, so I haven’t yet pursued anything like that.