TypeScript can't do it

May 18, 2024

Sheep

This article takes a stab at getting TypeScript to perform some simple calculations in the type system alone. Before you ask - is it useful at all? Well, it depends on your use case (please, read along), but boy, is it fun! Buckle up.

ℹ️ While there are other implementations out there that I personally find way more elegant, here we're deliberately going to approach the problem from a slightly different angle, prioritising readability, plus, who knows, maybe even achieving some utility.

Before we begin, there are some constraints that we must accept. Some of them come from our implementation of choice, while others originate from the TypeScript compiler itself. These include:

We'll only support non-negative natural numbers (often referred to as whole numbers).
The code will heavily rely on recursion, which means the TypeScript recursion limit applies, and we'll hit it at some point.

Now to...

The underlying mechanics

As stated in the title, TypeScript is incapable of performing arithmetic operations within the type system. In general, when it comes to combining types, it is quite limited. We have a few operators at our disposal, such as union and intersection, the ability to spread tuples, template literal types, extending interfaces, and that's basically it. Nowhere near what we need.

One way of solving this riddle is by using an intermediate data structure - what TypeScript can't do with a number, it can do with a different type; it only requires being able to convert back and forth between the two. As it turns out, a tuple makes a great candidate for such a helper type. What makes it so appealing is the subtlety in handling the length property. Consider the following snippet:

type MyArray = 'foo'[];
type MyArrayLength = MyArray['length']; // `number`
 
type MyTuple = ['foo'];
type MyTupleLength = MyTuple['length']; // `1`
 
type Test<A, B> = B extends A ? true : false;
type TupleToArray = Test<MyArray, MyTuple> // `true`
type ArrayToTuple = Test<MyTuple, MyArray> // `false`

type MyArray does not encode length information in its definition, thus the length property is inferred as a number. In contrast, type MyTuple narrows it down to a single member - ['foo'], thereby removing ambiguity from the length property and allowing for accurate inference. Despite this, tuples remain arrays, which will later be useful for constraining generic parameters.

Armed with all knowledge, let's build ourselves...

A framework

As mentioned earlier, all we need is to convert the number type to something we can work with, and then convert it back. We've also already established that a tuple will suffice. Since we're not particularly interested in the contents of the tuple (only the length property is useful), we're free to throw anything in there.

Behold type XDNumber:

type XDNumber = 'XD'[];
 
type ToXD<T extends number, R extends XDNumber = []> =
  T extends R['length']
    ? R
    : ToXD<T, [...R, 'XD']>;
 
type FromXD<T extends XDNumber> = T['length'];
 
type Zero = ToXD<0>; // `[]`
type One = ToXD<1>;  // `["XD"]`
type Two = ToXD<2>;  // `["XD", "XD"]`
 
type ActualZero = FromXD<Zero>; // `0`
type ActualOne = FromXD<One>;   // `1`
type ActualTwo = FromXD<Two>;   // `2`

Okay, what's actually going on here:

number ➡️ type XDNumber: given a number, we create a tuple with matching length by recursively inserting 'XD'
type XDNumber ➡️ number: to convert back, we simply grab the length

Having built the tools, let's finally do some math.

Addition / Subtraction

The algorithm for addition is pretty straightforward:

given 2 numbers, convert them to type XDNumber
spread the results over a new tuple
grab the length of the resulting tuple

type Add<A extends number, B extends number> = [...ToXD<A>, ...ToXD<B>]['length'] & number;
 
type Test1 = Add<0, 0>; // `0`
type Test2 = Add<0, 1>; // `1`
type Test3 = Add<3, 2>; // `5`

Subtraction involves basically reverting the process:

convert the first operand to type XDNumber; let's call it a
convert the second operand to type XDNumber; let's call it b
pattern-match on a:
- if it's comprised of b and another type XDNumber (let's call it c), return type FromXD of c
- otherwise, return never

type Subtract<A extends number, B extends number> =
  ToXD<A> extends [...ToXD<B>, ...infer R extends XDNumber]
    ? FromXD<R>
    : never;
 
type Test1 = Subtract<0, 0>; // `0`
type Test2 = Subtract<4, 3>; // `1`
type Test3 = Subtract<2, 3>; // `never`

Multiplication / Division

This is where things get a little more complex. Luckily, we can mitigate that complexity by building upon things we've created previously.

Let's start with multiplication, which, by the way, is nothing more than recursive addition:

start with 2 operands (a and b) and an extra variable for storing the result (r), which defaults to 0
if b equals 0 (the base case), return r
otherwise, return the result of multiplication, but this time subtract 1 from b (we already know how to do subtraction), and add a to r (we already know how to do addition)

type Multiply<A extends number, B extends number, R extends number = 0> =
  B extends 0
    ? R
    : Multiply<A, Subtract<B, 1>, Add<R, A>>
 
type Test1 = Multiply<2, 0>; // `0`
type Test2 = Multiply<1, 5>; // `5`
type Test3 = Multiply<3, 7>; // `21`

Similarly, division can be described as recursive subtraction:

start with 2 operands (a and b) and an extra variable for storing the result (r), which defaults to 0
if b equals 0, return never (can't divide by 0)
if subtracting b from a produces a result (let's call it tmp) greater than 0, return the result of division, but this time replace a with tmp, and add 1 to r
otherwise, return r

type Divide<A extends number, B extends number, R extends number = 0> =
  B extends 0
    ? never
    : ToXD<A> extends [...ToXD<B>, ...infer Tmp extends XDNumber]
    ? Divide<FromXD<Tmp>, B, Add<R, 1>>
    : R
 
type Test1 = Divide<3, 0>; // `never`
type Test2 = Divide<2, 2>; // `1`
type Test3 = Divide<9, 4>; // `2`

Power / Root*

It won't come as a surprise if I say that, once again, we're going to build on the tools we've created earlier.

Exponentiation, you guessed it, is simply recursive multiplication:

start with 2 operands (a and b)
if b equals 0, return 1
if b equals 1, return a
otherwise, return a multiplied by a to the power of b minus 1

type Pow<A extends number, B extends number> = B extends 0
  ? 1
  : B extends 1
    ? A
    : Multiply<A, Pow<A, Subtract<B, 1>>>;
 
type Test1 = Pow<2, 0>; // `1`
type Test2 = Pow<3, 1>; // `3`
type Test3 = Pow<4, 3>; // `64`

We're going to do a little bit of cheating now (hence the asterisk in the heading). We're going to "compute" the square root using a brute force approach:

start with a single operand (a) and an extra variable for storing the result (r), which defaults to 0
if r to the power of 2 equals a, return r
otherwise, return type Sqrt of a, this time adding 1 to r

type Sqrt<A extends number, R extends number = 0> = Pow<R, 2> extends A
  ? R
  : Sqrt<A, Add<R, 1>>;
 
type Test1 = Sqrt<0>; // `0`
type Test2 = Sqrt<1>; // `1`
type Test3 = Sqrt<9>; // `3`

Trying it all out

Okay, we have the blocks: let's build something with them. The hello world of type-level programming seems to be computing the nth element of the Fibonacci sequence - fine by me.

type Fibonacci<T extends number> =
  T extends 0 | 1
    ? T
    : Add<Fibonacci<Subtract<T, 2>>, Fibonacci<Subtract<T, 1>>>;
 
type Test1 = Fibonacci<1>; // `1`
type Test2 = Fibonacci<3>; // `2`
type Test3 = Fibonacci<8>; // `21`

Let's try something more contemporary. How about we compute the energy of a body with a mass of 2kg in a very slow universe, where the speed of light equals 3 (instead of approximately 3 × 10^8)?

type C = 3;
 
type E<M extends number> = Multiply<M, Pow<C, 2>>;
 
type Energy = E<2>; // `18`

We can go on and on computing different things, but is that really useful? Is there something one could actually use type XDNumber for? It turns out there actually might be.

Comparing numbers

First things first - we need something to represent order. The TypeScript type system lacks not only comparison operators but also the concept of truthiness and falsiness. Let's borrow from Haskell - more specifically, the data Ordering type.

Courtesy of type XDNumber, the comparison algorithm is pretty straightforward:

convert both operands (let's call them a and b) to type XDNumber
if a and b are identical tuples, return 'EQ'
if a is longer than b, return 'GT'
otherwise, return 'LT'

type Compare<A extends number, B extends number> = ToXD<A> extends ToXD<B>
  ? 'EQ'
  : ToXD<A> extends [...ToXD<B>, ...any]
    ? 'GT'
    : 'LT';
 
type Test1 = Compare<1, 1>; // `"EQ"`
type Test2 = Compare<7, 2>; // `"GT"`
type Test3 = Compare<4, 9>; // `"LT"`

Being able to compare numbers within the type system enables some interesting capabilities, such as...

Type-safe arithmetic functions

Consider the following business requirement:

A function that takes a single number and returns the number squared if it is less than or equal to five, or increased by ten otherwise.

Here's what your initial implementation would most likely look like:

const foo = (arg: number) => arg <= 5 ? arg ** 2 : arg + 10;
 
const test1 = foo(3); // `number`
const test2 = foo(6); // `number`

While this works, there might be situations where you're not happy with the way TypeScript generalizes the result type; everything ends up being just a number. How about a version that narrows the result type more accurately?

declare const foo: <T extends number>(arg: T) => Compare<T, 5> extends 'LT' | 'EQ' ? Pow<T, 2> : Add<T, 10>;
 
const test1 = foo(3); // `9`
const test2 = foo(6); // `16`

And Voila!

Now that we've made TypeScript properly infer things, we might as well be interested in...

Improving control flow analysis

ℹ️ At the time of writing, TypeScript is at version 5.4.5. The described behaviour may or may not change in future releases.

Out of the box, TypeScript does a pretty good job narrowing down types based on equality:

declare const foo: number;
 
if (foo === 3) {
  // @ts-expect-error 💥
  if (foo === 42) {
    alert('yay');  
  }
}

However, things get worse when it comes to comparing numbers:

declare const foo: number;
 
if (foo < 3) {
  if (foo === 42) { // All good 🤷‍♂️
    alert('yay');  
  }
}

How do we fix this? Unfortunately, we're not allowed to overload operators, but we can use type guards to our advantage. Before we do, however, there's one issue that we need to address. The code we're about to write is heavily dependent on recursion, and when it comes to recursion in TypeScript, there are limits. We can bypass these limits by narrowing down the set of values we'll be dealing with. Instead of the broad number type, let's focus on 0 | 1 | ... | 99.

type NumRange<T extends number, R extends number[] = []> = T extends R['length']
  ? R[number]
  : NumRange<T, [...R, R['length']]>;
 
type SafeNumber = NumRange<100>; // 0 | 1 | ... | 99

We can now implement a type guard that will filter out these pointless checks:

type LT<A extends number, B extends number> = {
  [N in A]: Compare<N, B> extends 'LT' ? N : never;
}[A];
 
declare const lt: <A extends number, B extends number>(a: A, b: B) => a is LT<A, B>;
 
declare const foo: SafeNumber;
 
if (lt(foo, 3)) {
  // @ts-expect-error 💥
  if (foo === 42) {
    alert('yay');  
  }
}

Okay, so what?

There's a thin line between actually creating something useful and over-complicating things for the sake of it. Whether it's the former or the latter depends on several factors:

the broader context
the requirements
the time constraint (or lack thereof)
the team

Realistically, 99% of the time you don't need this, but once you actually do, boy, does it shine.

Photo by Elimende Inagella on Unsplash.