Implementing Advanced Type-Level Arithmetic in TypeScript part 1

If you have been following my previous articles on TypeScript (Developing type-level algorithms in TypeScript, 4 TypeScript tips you might not know), you should already be aware that this language offers an extremely expressive type system. It can provide a next-level developer experience for anyone using such neatly typed code when taken advantage of. Examples of how to write such code can be found here.

In this two-part blog series, however, we will focus on something that's not particularly useful but fun and serves as a great exercise for our "typing muscles". We'll implement Add and Subtract operations that work entirely on the type-level and therefore evaluate at compile time.

type res = Add<16, 4>;
//   ^ 20

The best thing is that unlike the method I showed here ("Basic algebra" section), the types we'll write can perform addition and subtraction on both negative and positive numbers, with the upper 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

The initial inspiration for my solution came from the MinusOne type challenge.

BTW, If you haven't heard of Type Challenges, it's an open-source list of fun type problems. Solving them is a great (and hard) way of becoming a TypeScript wizard.

One of the problems' test cases required that the solution should be able to subtract 1 from 0, obtaining -1. When I saw that, I raised my eyebrows as I didn't think negative numbers were possible to handle on the type level since they can't be represented with tuple lengths. Curious, I looked into the solutions and discovered this one.

Long story short, the secret ingredient turned out to be strings. This makes sense as the built-in mechanisms to handle string types in TypeScript are pretty advanced and, as I learned, we can parse a string type to a number type with the following:

type ParseInt<T extends string> 
  = T extends `${infer Digit extends number}`
  //                         ^^^^^^^^^^^^^^
  //                         key element                       
  ? Digit
  : never;

type example = ParseInt<"42">; // 42 (not "42" 👍🏻)

The above is possible since TypeScript 4.8.

Understanding the MinusOne type

In today's post, we'll explore how the MinusOne type works and implement a similar PlusOne type. In the next post, we'll see how we can take this idea further and build full Add and Subtract types on top of it.

The high-level algorithm of MinusOne is the following:

1. We convert the argument to a string

If it's positive, with some string manipulation, we create a string that represents a decremented number

If it's negative, we remove the minus sign, create a string that represents an incremented number, and put the sign back

2. Convert the new string back to a number.

Let's start with some 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 utility functions are well-named and pretty straightforward. However, if their implementation seems new to you, you can Google the following techniques:

• "TypeScript infer in Template String Types"
• "TypeScript recursive types".

Now, we'll look into InternalMinusOne, the core type that performs the actual logic 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 similarly to how you would do long subtraction in elementary school. We take the last digit (here, it's the first one because the number is reversed) and consider two cases:

• If the digit d is not 0, then we replace it with d - 1. For example, 8 becomes 7, 4 becomes 3, etc.
• If the digit is 0, then we put 9 and recursively subtract 1 from the rest of the number. For example, for 80, we'd have "08" (remember, the argument here should be reversed), which we'd change to 9${InternalMinusOne<8>}, which would become "97," and after reversing "79."

A cool trick in this type is how we replace d with d - 1 using a tuple [9, 0, 1, 2, 3, 4, 5, 6, 7, 8] and indexing it with Digit. Since the elements in the tuple are shifted, the element at index 3 has 2, index 8 has 7 in it, and so on.

Simple MinusOne

Let's compose the above types to create a type that will subtract one from a number and give us a number back:

type AlmostFullMinusOne<T extends number> = ParseInt<
      RemoveLeadingZeros<ReverseString<InternalMinusOne<ReverseString<`${T}`>>>>
    >;

AlmostFullMinusOne<42>; // 41

When reading such types, remember to read outwards from the most nested part (in this case, from ${T}). To make it easier to follow, let's also assume that we are evaluating MinusOne<100>.

• First, we convert T from a number to a string via ${T}. So 100 becomes "100".
• Then we reverse it. So "100" becomes "001".
• Then we apply InternalMinusOne. So following the rules we described above, we get "990".
• We reverse the string again. So "990" becomes "099".
• We remove any leading zeros that may have been generated in the process. We have to do this because otherwise, our ParseInt type would yield a generic number. In our example, "099" becomes "99".
• Finally, we apply ParseInt. So "99" becomes 99.

Full MinusOne

AlmostFullMinusOne, which we implemented in the previous section, doesn't handle two important cases:

• when T is 0
• when T is < 0.

The first one is easy; we'll just hard-code the answer: T extends 0 ? -1 : .... Now, if the number is negative (its string representation starts with a "-" sign), then we'll grab the absolute value, add one to it, and put the minus sign back. To add one to a number, we'll need a InternalPlusOne, but this one is analogous to InternalMinusOne, so I won't describe it in 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;

Having this, we can finally implement the full MinusOne and analogous 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}`>>>>
    >;

Now, if you want to challenge yourself (the best way to learn new things!), I invite you to try implementing the PlusOne type, which is analogous to the MinusOne type.

If not, then I'll attach my solution below:

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

Wow, that was some nice type-level magic, and we're only getting started!

In the next post, I'll explain how we can use this approach to deal with numbers in TypeScript and implement even more advanced Add and Subtract types. If you don't want to miss it, make sure to stay subscribed to our social media accounts 🙏🏻
X: @softwaremill
LinkedIn: SoftwareMill

Reviewed by: Tomasz Krawczyk