TypeScript Type Level Addition

This blog is adapted from the slide deck for my Columbus Code and Coffee talk. Watch the talk version if you prefer videos!

Ok, now let’s get into it!

No JavaScript Allowed

We’ll work entirely on the type level—there will be no runtime representation

// absolutely not
const add = (x: number, y: number): number => x + y;
// amazing
type Result = Add<1, 2> = ...;
//   ^? Result: 3

Note that the syntax // ^? is a twoslash, which shows what each type resolves to

Why?

We’ll use practical pieces to build something impractical—I’ll show just how impractical at the end!

It’s great to get a better handle on the TypeScript type system or push the boundaries if you’re a big nerd like me

Plus it’s fun—stop judging me 😡

Who’s this talk for?

To fully understand, you’d need to have doven deep into TypeScript metaprogramming, maybe writing a library or doing type challenges for the sake of it. Don’t fret if you’re not a pro!

Agenda

These are the building blocks we’ll need to eventually build up to type level addition

It’s tough to find more information without the correct terminology. If you look up “how to find the last item of a TypeScript array type,” you’ll only find runtime examples like arr.at(-1) and arr[arr.length - 1]. If you write “how to find the last item of a TypeScript tuple type,” you’ll get the type version!

  • generics/generic constraints
  • conditionals
  • mapped types
  • variadic tuple types
  • infer
  • recursion
  • Addition—the main event!

Generics

Generics are type level parameters—we can derive one type from another. In this case, they stop us from needing to create a new type and function for every item that could be held in an array. Instead of StringArray, NumberArray and NumberAndStringArray, we can have an Array<T> where T is any type

JavaScript arrays don’t care about the implementation of their items, so there’s no need to reimplement pop or push for each element type

type MyArray<T> = {
	push: (x: T) => void;
	pop: () => T | undefined;
	map: <U>(fn: (x: T) => U) => MyArray<U>;
};
type SlushyMaker<Flavor> = {
	makeSlushy: (flavor: Flavor) => Slushy<Flavor>;
};

Why do we care about types?

Types are used when we care about some property of the input. In this case, we want to add two numbers as opposed to string concatenating for example

const add = (x: number, y: number): number => x + y;

Generic Constraints

This same concept applies on the type level—for example, we may care that a type has a length property or is indexable by a string

SlushyFlavor is a sum type, meaning it can be one of "Lemonade", "Orange Fanta" or so on.

type SlushyFlavor =
	| 'Lemonade'
	| 'Orange Fanta'
	| 'Mountain Dew'
	| 'Motor Oil'
	| 'Peach';

extends requires that the left type must be assignable to the right. "beans" is not assignable to SlushyFlavor, so the consumer of our API gets feedback through a type error

type SlushyMaker<Flavor extends SlushyFlavor> = {
	makeSlushy: (flavor: Flavor) => Slushy<Flavor>;
};

// Type '"beans"' does not satisfy the constraint 'SlushyFlavor'
type BeansSlushyMaker = SlushyMaker<'beans'>;

Conditionals

There is no if statement on the type level—conditionals are done via ternary expressions. However, instead of operating on a boolean expression, they check if a type is assignable to another—just like generic constraints

type SlushyFlavor =
	| 'Lemonade'
	| 'Orange Fanta'
	| 'Mountain Dew'
	| 'Motor Oil'
	| 'Peach';

type IsDelicious<T extends SlushyFlavor> = T extends 'Peach' ? false : true;

Exercise 1 - And

Pay attention to all these examples—we’ll be using them in our final result!

Code a type And that takes in two booleans and returns true if both are true and false otherwise

If T and U are both the literal true, then true will be returned

export type And<T extends boolean, U extends boolean> = T extends true
	? U extends true
		? true
		: false
	: false;

Remember that extends means T must be assignable to boolean, so boolean, true, false, or never1 will be valid here, though we’ll pass only the literals true and false in our case

Mapped Types

Mapped types allow us to loop through object keys and change their values. Similar to JavaScript, tuples types act as objects with numeric keys, so they can be mapped equivalently

type Cheesify<T> = {
	[Key in keyof T]: 'cheese 🧀🧀🧀';
};

type CheesifiedObject = Cheesify<{
	favoriteFood: 'waffles';
	favoriteChild: 'Charlie';
}>;
//    ^? {favoriteFood: "cheese 🧀🧀🧀"; favoriteChild: "cheese 🧀🧀🧀";}
type CheesifiedTuple = Cheesify<[1, 2]>;
//     ^? ["cheese 🧀🧀🧀", "cheese 🧀🧀🧀"]

Variadic Tuple Types

Variadic tuples are very similar to the spread operator in JavaScript (...). For example, we can take two tuples and concatenate them like so

type Concat<T extends unknown[], U extends unknown[]> = [...T, ...U];
type Delicious = Concat<['garlic'], ['bread', 'is', 'scrumptious']>;
//   ^? ["garlic", "bread", "is", "scrumptious"]

The generic constraint is required to let TypeScript know we can spread this type

Infer

In conditional types, we can extract types with infer. infer is only usable in a conditional—the false branch returning never is unreachable since T is constrained to arrays

type Element<T extends unknown[]> = T extends Array<infer Item> ? Item : never;

type Num = Element<number[]>;
//   ^? number

infer has a lot of use cases beyond this, and we’ll explore a few more in this article!

Last

Combining variadic tuple types and infer, we can grab the last item in a tuple

The default of 0 will come in handy later!

export type Last<T extends unknown[], Default = 0> = T extends [
	...infer _,
	infer L,
]
	? L
	: Default;
type LastExample = Last<[1, 2, 3, 4]>;
//   ^? 4
type LastExampleEmpty = Last<[], 42>;
//   ^? 42

infer can also get the last character in a string as well, albeit with different syntax

Exercise 2 - Pop

Make a type taking in a tuple and returning a copy without the last element

This is almost exactly the same as our Last example, but we keep the starting elements

export type Pop<T extends unknown[]> = T extends [...infer Head, infer _]
	? Head
	: [];
type PopExample = Pop<[1, 2, 3, 4]>;
//   ^? [1, 2, 3]
type PopExampleEmpty = Pop<[]>;
//   ^? []

Adding time!

Make a type that takes in two numbers and returns their sum

Adding Small Numbers

This could be done with an addition table. Table[1][1] would give us 2

type Table = [
  [0, 1, ...],
  [1, 2, ...],
  ...
]

For our implementation, we’ll instead use the length property on tuples

We can make two tuples and combine them together and get the new length at the end!

Tuple of length N

We must use recursion to loop N times since there is no native looping construct like a for or while loop in the type system.

If the length of the resultant tuple is N, then stop recursing. If not, add an arbitrary value to the tuple, in this case never.

type TupleLengthN<
	N extends number,
	T extends never[] = [],
> = N extends T['length'] ? T : TupleLengthN<N, [...T, never]>;
Add digits

Now that we can create tuples of arbitrary length, we can concatenate them and grab the new length

export type AddDigits<M extends number, N extends number> = [
	...TupleLengthN<M>,
	...TupleLengthN<N>,
]['length'] &
	number;

There is a limitation of 999 items per tuple with this method before hitting the recursion limit, so we’ll need to find another approach. We likely could manually make a huge addition table, but that’s no fun!

Manual Adding

Since we can’t add numbers larger than 999, we need to take matters into our own hands and go back to grade school. I’m sorry to say, but in addition to programming fundamentals, we need to know how to do basic arithmetic as well

We need to add left to right. If the sum of a column is greater than 10, we carry the 10s place and leave the 1s place behind

15+6??\begin{array}{cc} & 1 & 5 \\ + & & 6 \\ \hline & ? & ? \end{array}

To add 15 and 6. First, we add 5 and 6

This adds to 11, so we take the 1 from the tens place and carry it over. The 1 from the ones place goes into the resultant ones column

115+61\begin{array}{cc} & 1 & \\ & 1 & 5 \\ + & & 6 \\ \hline & & 1 \end{array}

Finally, we add the carried one and the one from the tens place of 15 to get 2, and put that in the 10s place, giving us 21

115+621\begin{array}{cc} & 1 & \\ & 1 & 5 \\ + & & 6 \\ \hline & 2 & 1 \end{array}

Pseudocode

To avoid getting bogged down in implementation, let’s do some pseudocode with some more familiar syntax

func add(num1, num2) {
	result = []
	carry = 0
	while carryOrDigitsToAdd {
		sum = lastDigit(num1) + lastDigit(num2) + carry

		digit = sum % 10
		carry = sum / 10

		result.push(digit)
	}
	return toNumber(result)
}

Split into digits

I recommend looking at these implementations one by one—they can be a bit much to look at. You have everything you need to understand them, but the syntax can be overwhelming

Convert a number into its individual digits

We’ll see implementation details for MapNums and Split soon—don’t worry about them for now

export type Digits<T extends NumLike> = MapNums<Split<`${T}`>>;
type DigitsExample = Digits<289>;
//   ^? [2, 8, 9]
Split a string into an array of its characters

This is very similar to splitting up our tuples, but with some new syntax to handle strings!

export type Split<S extends string> = S extends `${infer Head}${infer Rest}`
	? [Head, ...Split<Rest>]
	: [];
type SplitExample = Split<'123'>;
// ^? ["1", "2", "3"]
Map an array of strings to their numeric equivalents 
export type MapNums<T extends string[]> = {
	[K in keyof T]: ToNumber<T[K]>;
};
type MapNumsExample = MapNums<['1', '2', '3']>;
//   ^? [1, 2, 3]

Carries

There’s no remainder or division operator in the Type Level!

We can assume numbers are never greater than two digits for these implementations

Get first digit of a number 
export type GetCarry<T extends number> =
	`${T}` extends `${infer C}${infer _}${infer _}` ? ToNumber<C> : 0;
type GetCarryExample1 = GetCarry<12>;
//    ^? 1
Get last digit of a number This could be implemented similarly to GetCarry, but this is pretty elegant, so why not! 
export type GetDigit<T extends number> = ToNumber<Last<Split<`${T}`>>>;
type GetDigitExample1 = GetDigit<12>;
//   ^? 2

Looping

Remember, there’s no for loop in the type level, we must use recursion

The base case is when there are no more numbers to add

And<
  And<IsZero<Num1["length"]>, IsZero<Num2["length"]>>,
  IsZero<Carry>
> extends true

This following is the most complex the code will get—take some time to understand what it’s doing

Recursive Adder Implementation

Sum is set as a default to mimic a variable in JavaScript—it could be directly in the code, but it looks nicer this way

If there’s no more numbers to add, end. If there are, add the ones place to the resultant tuple and continue on with the carry and pop from the 2 num arrays

type Adder<
	Num1 extends number[],
	Num2 extends number[],
	Carry extends 0 | 1 = 0,
	Sum extends number = AddDigits<Carry, AddDigits<Last<Num1>, Last<Num2>>>,
> =
	And<
		And<IsZero<Num1['length']>, IsZero<Num2['length']>>,
		IsZero<Carry>
	> extends true
		? []
		: [...Adder<Pop<Num1>, Pop<Num2>, GetCarry<Sum>>, GetDigit<Sum>];
type AdderExample = Adder<[9, 2, 3, 4], [5, 4, 3, 2]>;
//   ^? [1, 4, 6, 6, 6]

Got it? I understand if not, this is a lot to get through 😅

Joining the result

This calls Adder and converts the array of digits into a single number!

Since we’re stringifying, we can take in a string | number | BigInt with no issue. Let’s call that a NumLike

export type Add<M extends NumLike, N extends NumLike> =
	Adder<Digits<M>, Digits<N>> extends infer R extends number[]
		? ToNumber<Join<R>>
		: never;

You may see a wacky extends infer R extends number[] in there, this is done to get around the recursion/type instantiation depth limit

With this, you can add numbers up until 64 bit floating point numbers can accurately describe them! Maybe if we used BigInts we could go even further!

Let’s take a look at the code!

Take a look through the GitHub Repo if you’re so inclined!

Play around with the code in a TypeScript Playground

But could you actually use this in a codebase?

Yes, but should you? It only works well if you know the literal type

You can either know the type at compile time

const add = <T extends number, U extends number>(x: T, y: U) =>
	(x + y) as Add<T, U>;

add(5, 10);
// ^? const add: <5, 10>(x: 5, y: 10) => 15

Or you can do some ridiculous assertions. If you were so inclined, you could assert on every number, albeit with a huge file size and runtime impact. I see the value in unsigned integers, but this level of precision is probably not worth it

let num: number = 10;
//   ^? let num: number
if (num === 10) {
	num;
	// ^? 10
}

I started down this rabbithole after being challenged to do a CodeWars on the same topic. I said it couldn’t be that hard. It ended up taking me 4 hours 😅

CodeWars uses an older version of TypeScript with a lower recursion limit, so I had to do more shenanigans to get it working

For reference, I’ve read the TypeScript Handbook and have been doing similar code challenges including from the TypeScript Type Challenges2 repo, advent of TypeScript, and so on for a few years now

My first blog from 2 years and 4 months ago—Implement Pick in TypeScript—was on the same topic!

Thanks for coming along this journey with me, and hopefully I’ll see you soon!

Footnotes

  1. never is a part of every union. For example, string is technically string | never ↩

  2. Add is an example in the extreme challenge! ↩