An Over-Engineered FizzBuzz Type in TypeScript

I’m sure we’re all familiar with the famous fizz buzz problem, it goes something like this:

Counting from 1 to 100, print either
1. fizz,
2. buzz,
3. fizzbuzz,
4. or the number itself
depending on the current iteration

Today we’ll build this in TypeScript, and no, I don’t mean a JavaScript function annotated with types.
I mean this:

A type that can be used to check the output of a fizzbuzz call.

No… this is not really useful but this exercise will hopefully help us learn a bit more about how to think in TypeScript.

Regular FizzBuzz:

The original fizzbuzz code looks something like:

We’ll want to recreate a lot of these pieces in TypeScript.

🥣 Basic Ingredients:

• TypeScript 4.1
• Numbers
• Arithmetic
• Loops
• String Concatenation

It’s technically somewhat possible to have done fizzbuzz as early as TypeScript 3.0, but 4.1 made things a lot easier (and more elegant).

🔢 Numbers

TypeScript has always supported number literal types like so:

Whereby a 5 is an extension (more specific type) of the number type:

But did you know that tuples have had a typed length property since version 2.7?

This property is particularly useful because we’re going to encode numbers into tuple types and pave the way to performing arithmetic.

—

🧮 Arithmetic

TypeScript 4.0 added a feature called variadic tuples — var, meaning variable, and aradic, referring to arity, the number of arguments a function takes. Basically, we’re able to manipulate variable/generic length tuples.

More specifically, the spread operator (...) was added to allow us to manipulate tuple types. We are able to build types that combine and split other tuple types like so:

And most importantly, we can see that the length property of these types are being calculated, so voila — arithmetic.

Note: when we perform subtraction, you’ll see that we will (predictably) run into issues if the elements aren’t all the same type. For example, if I try to subtract [true, false] from [any, string, boolean]:

We get never because it’s impossible. To avoid this, we’ll just always type our tuple elements as any.

🥂 Great!
We can manipulate numbers, but an interface that takes in tuples isn’t particularly user friendly right? What we really want to be able to do is something like Subtract<5,4>. To do that, we need to be able to dynamically build tuples sized to a given number literal type like 5, and for that we actually need… recursion.

(Further reading on tuple arithmetic in TypeScript.)

—

🔁 Loops (Recursive)

TypeScript 4.1 added support for something that was already commonly being used through various hacks— recursive conditional types. We can now define conditional types that reference themselves, allowing us to define loops that end because we can define the end condition.

So if I wanted to build a tuple factory I can recursively increase it’s size by 1 until it’s the right size:

But one problem we’ll have is TypeScript’s recursion depth limit. It’s hardcoded to be about 45 (though this limit has been increased to about 1000 in TypeScript 4.5.4), so we can’t build anything bigger than 45 elements:

We can get around this issue through some hacks.

1: Wrapping recursive calls in an object

First, we can create infinitely deep types if we wrap results in objects:

Here we are able to avoid the error because the calculation is being deferred. The depth is actually 46 but TypeScript doesn’t evaluate all the way down, at least not until we use the type for something, that’s why for now the summary is showing any.

TypeScript is allowing this functionality so there’s no risk of crashing things when the developer defines an infinitely recursively deep object type like a JSON object that can be infinitely deep.

This hack gives us practically limitless depth, but we’ll get stuck with a deep object that isn’t evaluated and so we won’t get our result. We’ll need to unwrap. Unwrapping, however, would take the same number of steps and… we’re trying to cut down on that, so we’ll need to be a bit clever here.

2: Halving/Logarithmic Reduction

We can define a helper that uses wrapping to have a limitless depth, but cuts the overall depth in half by consolidating sets of 2 wrappings into 1:

Using this should cut the depth of 8 to 4 in this case:

With this, we’ll only need to run _Unwrap 3 times (8 → 4 → 2 → 1), this is sort of like the divide and conquer we do in binary search, we’re cutting the number of wrappings to it’s log₂.

This should technically allow us to reach a depth of something like 2⁴⁵ but it’s a bit more complicated than that and instead we’re stuck with a limit of about 3000, but that’s enough for our exercise.

(There are ways to boost this limit to 150,000+, by using doubling to keep the depth of recursion below 50, unfortunately the TypeScript team clamped down a hardcoded limit of about 10,000 in version 4.2)

—

📝 String Concatenation

The final ingredient we’ll need is a way to combine strings together. This was also introduced in TypeScript 4.1. It’s pretty straightforward, we can now do this:

We’ll use this to build our output.

🔪 Preparation

With our ingredients we can now set up some basic helpers to define our ultimate type.

❓ Conditional Types

Since we’re relying on a TypeScript hack to defer evaluation, everything has to defer-safe. So rather than setting hard type parameter rules like this:

We’re going to rely on conditional types:

Remember how the summary of the 46 deep object wasn’t actually being evaluated? With deferrals, TypeScript will try to avoid evaluation as much as possible and will use unknown as a placeholder instead. With hard parameter rules, unknown would instantly fail constraints like <Size extends number> because unknown doesn’t extend number. Conditionals don’t have this problem because they handle both cases of passing and failing the constraint.

—

📏 Length

This will let us get the length of any tuple:

—

🎁 Unwrap

This will let us unwrap the result of any deep recursive loops:

Note: Defining a complementary Wrap<Inside> = {result: Inside} would make sense but it seems to run into a bunch of issues.

—

🏭 Tuple Factory

This will basically be similar to what we had before:

We’ll want to create a friendlier interface that takes in a number as a parameter. However, we’ll also need to add a few additional conditionals because of an issue that gets fixed in 4.2.
Take a look at this:

Basically, when we use a conditional to check the Number parameter, it doesn’t get applied downstream, so TypeScript can’t figure out that Tupleize<Number> results in any[].
But if you use a parameter constraint it works:

But we don’t want parameter constraints instead what we’ll do is guarantee that the output will be any[]:

First, we assign the result to a variable Tuple using infers, then we check that Tuple extends any[] before outputting it.

—

➕ Add

We can use the tuple factory to help us here:

—

➖ Subtract

Same here:

—

➗ Modulo

A modulo is the remainder after performing division and division is just repeated subtraction. So we’ll attempt to Subtract until it comes back as never which tells us that we’ve subtracted too far. Since we couldn’t subtract further it means we already had the remainder on hand, so we’ll just return that. We’ll also need to use halving to prevent issues with recursion limits:

Let’s Bake this 🥐

Finally! We can build our type.
First, let’s define a basic for loop, but using recursion. Normally we would achieve this with something like:

where running forLoop(5) would get us a result of 1 2 3 4 5.

The type will be basically the same:

But we don’t want to print out the number for every number, we want to print “fizz”, “buzz”, “fizzbuzz”, or the number. Let’s build some helpers here.

• FizzText will handle printing out “fizz”
• BuzzText will handle printing out “buzz”
• Coalesce will choose a given default if a given value is empty string ("")
• FizzBuzzText will combine everything together

Putting it all together:

🎉 It works!

🔗 Here’s a link to the playground

But it’s extremely slow and starts croaking when we try something like 500. Let’s fix that.

📈 Optimization

We wrote the code in a way that matches the way we wrote it in regular JavaScript, but some of the operations are really suboptimal.

Repeat Tupleization
To actually advance the index, in every iteration we call Add<Index, 1> which will build a tuple of size Index. Building tuples takes a long time and we do this for every iteration (this is a time complexity of O(N²)).

We do even worse when we use FizzBuzzText which uses Modulo which repeatedly uses Subtract which itself builds tuples (this means Modulo by itself has a time complexity of O(N²) and using Modulo on every iteration ends with a complexity of O(N³)).

The problem stems from converting in and out of tuples. We can avoid this by only converting numbers into tuples once and using tuple specific operators.

Let’s first rework all helpers to function on tuples:

That covers all the arithmetic, next the text helpers:

Lastly, our function only needs to be tweaked slightly to use a tuple as a counter:

⏱ Results (in seconds):

╔══════╦══════════╦════════════╗
║ size ║ original ║   faster   ║
╠══════╬══════════╬════════════╣
║ 500  ║ 29       ║ 3          ║
║ 1000 ║ error    ║ 9          ║
║ 2000 ║ error    ║ 33         ║
║ 3000 ║ error    ║ 56(error)  ║
╚══════╩══════════╩════════════╝

🚅 Fast!

🔗Link to Playground

But can we do better?

Linear Time

Though this is faster (at a time complexity of O(N²)), we can go faster. We’re still using Modulo which uses repeated subtraction to get us a result, but we can actually avoid using Modulo with a bit of ingenuity.

What we’ll do is basically count up to 3 and 5 using tuples, and reset back to one on every cycle. These mini cycle trackers will take the place of using Modulo. We’ll need to modify our text helpers first, assuming we’ll never exceed 3 or 5:

With these helpers, we just need to track 3s and 5s:

Now it should run at about the same speed as it takes to build a single tuple with the size of the loop.

⏱ Results (in seconds):

╔══════╦══════════╦════════════╦═══════════╗
║ size ║ original ║   faster   ║  fastest  ║
╠══════╬══════════╬════════════╬═══════════╣
║ 500  ║ 29       ║ 3          ║ 1         ║
║ 1000 ║ error    ║ 9          ║ 3         ║
║ 2000 ║ error    ║ 33         ║ 14        ║
║ 3000 ║ error    ║ 56(error)  ║ 41        ║
╚══════╩══════════╩════════════╩═══════════╝

🚄 Faster!

🔗 Playground Link