Advanced Type-Level Arithmetic in TypeScript, part 1: the implementation
See how to build `Add` and `Subtract` operations that live purely at the type level and are computed at compile time.
If you have read my earlier articles on TypeScript, you already know that the language comes with a remarkably expressive type system. Used well, it can give anyone working with such carefully typed code a developer experience on a whole new level.
In this two-part blog series, though, we’ll concentrate on something that isn’t especially practical, but is fun and makes an excellent workout for our “typing muscles”. We’ll build Add and Subtract operations that run purely at the type level and are therefore computed at compile time.
type res = Add<16, 4>;
// ^ 20
Best of all, in contrast to the “Basic algebra” approach I presented previously, the types we’re about to write can add and subtract both negative and positive numbers, up to a limit of 9007199254740991 (Number.MAX_SAFE_INTEGER) 🤯.
Add<-123, -52>; // -175
Add<123, -52>; // 71
Add<-123, 52> // -71
Add<123456789, 9988776655>; // 10112233444
Add<9007199254740989, 2>; // 9007199254740991
How I came up with it
My solution was originally inspired by the MinusOne type challenge.
By the way, in case you don’t know Type Challenges, it’s an open-source collection of entertaining type puzzles. Working through them is a great (and tough) path to becoming a TypeScript wizard.
One of the test cases in that problem expected the solution to subtract 1 from 0 and get -1. Seeing this surprised me, because I believed negative numbers couldn’t be handled at the type level, as tuple lengths can’t express them. Out of curiosity, I went through the solutions and found this one.
To cut a long story short, the trick turned out to be strings. That’s logical, since TypeScript’s built-in tools for working with string types are quite sophisticated, and, as I found out, a string type can be parsed into a number type like this:
type ParseInt<T extends string>
= T extends `${infer Digit extends number}`
// ^^^^^^^^^^^^^^
// key element
? Digit
: never;
type example = ParseInt<"42">; // 42 (not "42" 👍🏻)
This has been possible starting with TypeScript 4.8.
Understanding the MinusOne type
In this post, we’ll look at how the MinusOne type works and build a similar PlusOne type. In the following post, we’ll push the idea further and build complete Add and Subtract types on top of it.
At a high level, the MinusOne algorithm goes like this:
- Turn the argument into a string
When it’s positive, we use some string manipulation to build a string representing the number decreased by one
When it’s negative, we strip the minus sign, build a string representing the number increased by one, and add the sign back
- Turn the resulting string back into a number.
Let’s begin with a few utility types:
type ReverseString<S extends string> = S extends `${infer First}${infer Rest}`
? `${ReverseString<Rest>}${First}`
: "";
type RemoveLeadingZeros<S extends string> = S extends "0"
? S
: S extends `0{infer R}`
? RemoveLeadingZeros<R>
: S;
type PutSign<S extends string> = `-${S}`;
These utilities have descriptive names and are fairly simple. Still, if the way they’re implemented is unfamiliar to you, try searching for these techniques:
- “TypeScript infer in Template String Types”
- “TypeScript recursive types”.
Next, let’s examine InternalMinusOne, the central type that actually does the work of subtracting one from a number.
// `S` is a reversed string representing some number, e.g., "0321" instead of 1230
type InternalMinusOne<S extends string> =
S extends `${infer Digit extends number}${infer Rest}`
? Digit extends 0
? `9${InternalMinusOne<Rest>}`
: `${[9, 0, 1, 2, 3, 4, 5, 6, 7, 8][Digit]}${Rest}`
: never;
It works much like the long subtraction you learned in elementary school. We take the last digit (which is the first one here, since the number is reversed) and handle two cases:
- When the digit
disn’t 0, we swap it ford - 1. So 8 turns into 7, 4 turns into 3, and so on. - When the digit is 0, we write 9 and recursively subtract 1 from the remaining part of the number. For 80, for instance, we’d get “08” (keep in mind that the argument is reversed here), which turns into
9${InternalMinusOne<8>}, then “97,” and “79.” once reversed.
A neat trick in this type is the way d is replaced with d - 1: we use the tuple [9, 0, 1, 2, 3, 4, 5, 6, 7, 8] and index into it with Digit. Because the tuple’s elements are shifted, index 3 holds 2, index 8 holds 7, and so forth.
Simple MinusOne
Let’s combine the types above into one that subtracts one from a number and returns a number:
type AlmostFullMinusOne<T extends number> = ParseInt<
RemoveLeadingZeros<ReverseString<InternalMinusOne<ReverseString<`${T}`>>>>
>;
AlmostFullMinusOne<42>; // 41
When reading types like this, start from the innermost part (here, ${T}) and work your way outward. To make it easier to follow, let’s also suppose we’re evaluating MinusOne<100>.
- To begin with,
${T}turns T from a number into a string, so100becomes"100". - Next, we reverse it, so
"100"becomes"001". - After that, we apply
InternalMinusOne. Following the rules described above, the result is"990". - We reverse the string once more, so
"990"becomes"099". - We strip any leading zeros that might have appeared along the way. This is necessary because otherwise our
ParseInttype would return a genericnumber. In our case,"099"becomes"99". - Lastly, we apply
ParseInt, so"99"becomes99.
Full MinusOne
The AlmostFullMinusOne type from the previous section doesn’t cover two important cases:
- when
Tis 0 - when
Tis < 0.
The first is simple: we just hard-code the result: T extends 0 ? -1 : .... If the number is negative (its string form begins with a “-” sign), we take its absolute value, add one to it, and restore the minus sign. Adding one to a number requires an InternalPlusOne, but since it mirrors InternalMinusOne, I won’t go into as much detail:
type InternalPlusOne<S extends string> = S extends "9"
? "01"
: S extends `${infer Digit extends number}${infer Rest}`
? Digit extends 9
? `0${InternalPlusOne<Rest>}`
: `${[1, 2, 3, 4, 5, 6, 7, 8, 9][Digit]}${Rest}`
: never;
With that in place, we can at last implement the complete MinusOne and the corresponding PlusOne:
export type MinusOne<T extends number> = T extends 0
? -1 // T = 0
: `${T}` extends `-${infer Abs}`
? ParseInt<PutSign<ReverseString<InternalPlusOne<ReverseString<Abs>>>>> // T < 0
// T > 0
: ParseInt<
RemoveLeadingZeros<ReverseString<InternalMinusOne<ReverseString<`${T}`>>>>
>;
If you’d like a challenge (the best way to learn something new!), go ahead and try to implement the PlusOne type, which mirrors the MinusOne type.
Otherwise, here’s my solution:
export type PlusOne<T extends number> = T extends -1
? 0
: `${T}` extends `-${infer Abs}`
? ParseInt<
PutSign<
RemoveLeadingZeros<ReverseString<InternalMinusOne<ReverseString<Abs>>>>
>
>
: ParseInt<
RemoveLeadingZeros<ReverseString<InternalPlusOne<ReverseString<`${T}`>>>>
>;
Summary
That was quite a bit of type-level magic, and this is just the beginning!
In the following post, I’ll show how this approach lets us work with numbers in TypeScript and build even more advanced Add and Subtract types.