Building algorithms at the type level in TypeScript
Thinking of getting into type-level programming? This blog post walks you through the fundamental techniques that let you implement nearly any algorithm with nothing but TypeScript types.
Sure, regular programming is fun, but have you ever written types that quite literally perform heavier computations than the typical to-do app? Painfully long builds, zero side effects, cryptic syntax and puzzled remarks from teammates on your PRs – welcome to the world of a type-level programmer.
Fancy a constant time bubble sort? Or an interpreter built from types? In this blog post, I’ll walk you through the fundamental techniques that let you implement nearly any algorithm with nothing but TypeScript types.
Keep in mind that the post is fairly long and touches on many separate TypeScript features. Rather than reading it in one sitting, you may want to bookmark it and return to it whenever it suits you.
What does programming require?
If I list the language elements I find most useful in everyday programming, I end up with these:
- data structures
- functions
- conditionals/code branching
- loops
- basic algebra (numbers, addition, multiplication, etc.)
If you believe that the list above is enough to program anything – great, because I’m going to show how every one of these can be emulated with types alone! Here’s a sneak peek:
- data Structures → object and tuple types
- functions → generic types
- conditionals/code branching → conditional types
- loops → recursive types
- basic algebra (numbers, addition, multiplication, etc.) → mixing the techniques above with a clever use of tuple lengths
Data structures/object and tuple types
This part is quite simple. Look at how closely TS objects resemble object types:
const someObj = {
a: "foo",
b: { bar: "baz" },
c: 42,
};
type someType = {
a: "foo",
b: { bar: "baz" },
c: 42,
};
Nothing complicated here. Notice how much TS objects look like object types:
The difference is that the field “values” in someType are in fact types that merely resemble TypeScript values. That’s because in TypeScript a constant such as 42 is either a value or a type, depending on where it appears.
This handy feature, known as literal types, is what makes it possible to write anything interesting at the type level at all. Without it, we’d only have types such as number or string, which are far less precise and, as a result, far less expressive.
The next sections present a few useful ways of working with type objects.
Reading properties
type User = { name: string; age: number; isAdmin: boolean };
type Name = User["name"];
// ^ string
// User.name doesn't work
type ValueOf<T> = T[keyof T];
type UserValue = ValueOf<User>;
// ^ string | number | boolean
At the value level, TS lets us use either the dot syntax, e.g. user.name, or the square brackets syntax, e.g. user["name"], but at the type level only the brackets syntax appears to be available. The interesting twist is that the brackets hold a type rather than just a field name as a string. Every key matched by that type contributes its corresponding type to the result:
type NameOrAge = User["age" | "name"];
// ^ string | number 🤯
type UserKeys = keyof User;
// ^ "name" | "age" | "isAdmin"
type UserValues = User[UserKeys];
// ^ string | number | boolean
Observe that this technique of obtaining a union of the types of all object values can be turned into a generic type (so that it works for any object type):
type ValueOf<T> = T[keyof T]; // more about generic types in the next section
type UserValue = ValueOf<User>;
// ^ string | number | boolean
Merging objects
Objects can be merged with the intersect type (&). Let’s look at it more closely to see how it works:
type I = A & B;
The line above can be read as “I is of type A and B simultaneously”. Put differently, a variable of type I can be assigned both to a variable of type A and to a variable of type B.
When A and B are objects, what is the “smallest” type meeting this requirement? An object containing every field of A and of B! As long as no fields clash (e.g. A and B both have a key “foo”, but with different types), this effectively amounts to merging!
type WithName = { name: string };
type WithAge = { age: number };
type WithIsAdmin = { isAdmin: boolean };
type User = WithName & WithAge & WithIsAdmin;
// ^ { name: string; age: number; isAdmin: boolean; }
type Org = WithName & WithAge;
// ^ { name: string; age: number; }
Pick and Omit helper types
These built-in types behave much like their value-level counterparts made popular by libraries such as lodash or ramda. The difference – as you’ve likely guessed – is that their arguments can be any types rather than only strings:
type User = { name: string; age: number; isAdmin: boolean };
type JustNameAndAge = Pick<User, "name" | "age">;
// ^ { name: string; age: number; }
type WithoutName = Omit<User, "name">;
// ^ { age: number; isAdmin: boolean; }
Now on to tuples – here are a few of their interesting traits.
Reading elements
Accessing tuple elements works just like what we did with objects:
type SomeTuple = [string, number, boolean];
type First = SomeTuple[0]; // string
type Second = SomeTuple[1]; // number
type Tail = SomeTuple[1 | 2]; // number | boolean
The only difference is that to obtain a union of all elements, it’s better to index the tuple with number rather than with the keyof SomeTuple. The latter would also give us every property that TypeScript arrays carry, such as length, map, etc., which typically isn’t what we want:
type AllKeys = SomeTuple[number]; // string | number | boolean
Concatenating tuples
As in value-level TS, tuples can be concatenated using the spread operator:
type SomeTuple = [1, 2, 3];
type AnotherTuple = [4, 5, 6];
type Concatenated = [...SomeTuple, ...AnotherTuple];
// ^ [1, 2, 3, 4, 5, 6]
Functions/generic types
Again, I’ll open this section with an artificial example where JS functions and TS generic types look strikingly alike:
// value-level JavaScript
const makeTuple = (a, b) => [a, b];
// type-level TypeScript
type makeTuple<a, b> = [a, b];
The variables in the angle brackets are typically called type parameters, and, as with ordinary functions, they can be used on the right-hand side; each time this type is “called” with specific types, the type parameters get substituted with them and a concrete type is computed.
type double<T> = [T, T];
type doubleString = double<string> // [string, string]
type doubleNubmer = double<number> // [number, number]
Without generics, we’d need a separate double type for every type we wanted to use!
Hold on, though – must generic types always be written to accept every type? Thankfully not: something called types constraints lets us narrow down the set of types that can be passed to our generic:
type MakeTuple<T extends number, U extends string> = [T, U];
type x = MakeTuple<42, "foo">; // OK
type badUsage = makeTuple<"foo", "bar">; // Error!
Generic types come with a few limitations:
- Higher-order generic types aren’t possible, i.e. a generic type can’t accept or return another generic type.
- The entire “body” of a generic type must be one expression rather than a sequence of statements as in value-level TypeScript.
Code branching/conditional types (+ infer)
Conditional types let us emulate if/else branching. For example:
type isString<T> = T extends string ? true : false;
type res1 = isString<"ala">; // true
type res2 = isString<42>; // false
Every conditional type has three parts: a condition, an if case and an else case:
type isString<T> = T extends string ? true : false;
// ^^^^^^^^^^^^^^^^ ^^^^ ^^^^^
// condition if else
Both its look and its behaviour are nearly identical to the JavaScript ternary operator. The key difference is that the first part must be an extends expression rather than a boolean value. Put simply, extends tests whether the first type is a subtype of the second one. In the example above, we test whether the generic type T is a subtype of string. To emulate the ternary operator at the type level, we can put extends true in the condition:
type BadIf<Cond extends boolean, Then, Else> = Cond ? Then : Else; // WON'T WORK
type GoodIf<Cond extends boolean, Then, Else> = Cond extends true ? Then : Else;
type example = GoodIf<true, 42, 0>; // 42
In plain JavaScript, nested ternary operators are considered an anti-pattern since they hurt readability, but in type-level programming there’s no alternative, so we just have to live with them.
type And<A extends boolean, B extends boolean> = A extends true
? B extends true
? true
: false
: false;
Infer keyword
In conditional types, the extends keyword lets us test whether a generic type fits a given shape. With infer, we can grab pieces of that shape into a variable and use them in the `then’ branch.
Let’s walk through an example:
// check if T matches this pattern
// vvvvvvvvvvvvvvvvvvvvvvvvvvvv
type GetNestedProp<T> = T extends { a: { b: { c: infer C } } } ? C : never;
// ^^^^^^^^^^^
// if it does then capture this part as a variable
// ^^^^^
// use it in the then branch
type a = GetNestedProp<{ a: { b: { c: "hello" } } }>;
// ^ "hello"
type b = GetNestedProp<boolean>;
// ^ never, because the boolean doesn't match our pattern
- We define a pattern against which the generic argument is checked.
- We place
inferkeywords in those parts of the pattern that we want to store in variables. - When the type argument fits the pattern, the captured variables become available to us.
Loops/recursive types
The type level has no support for loops, but recursion can be used to implement any logic that needs iteration. A recursive type generally follows this idea:
type SomeRecursiveType<Arg> =
// check if we reached the end of the iteration
CheckBaseCase<Arg> extends true
// if yes, then "return" something
? SomeType<Arg>
// else, use recursive type again, but with a different argument
: SomeRecursiveType<ModifyArg<Arg>>;
Recursive types are often used to search for something in a tuple or a string. As an example, here’s how to pull out the last element of a path-like string.
type ExtractLastItem<Path extends string> =
Path extends `${string}/${infer Rest}`
? ExtractLastItem<Rest>
: Path;
type Item = ExtractLastItem<"foo/bar/baz/hello">;
// ^ "hello"
On every iteration, we attempt to split the path at the first /. If that works, we apply the type recursively to the portion of the path following the first /. The base case is reached once the path contains no /. At that point we’ve found the last element, so we return it and the recursion stops.
Basic algebra
TypeScript doesn’t officially support arithmetic on type-level numbers. Still, this doesn’t prevent programmers from misusing the length property of tuples to emulate at least the algebra of natural numbers. Here’s the trick.
type len = [1, 2, 3, 4]["length"]
// ^ 4 🤯
Exactly! You might expect the length property to be typed simply as number. However, because tuple lengths are known at compile time, TypeScript is able to be more precise.
This is the recipe for adding two numbers, a and b, that exploits this behaviour:
- build a tuple of length
a - build a tuple of length
b - concatenate the two
- read the
lengthproperty of the resulting tuple
In code, it looks like this:
type Add<A extends number, B extends number> = Length<
Concat<CreateArrOfLen<A>, CreateArrOfLen<B>>
>;
We’ve already covered reading properties and concatenating tuples, so all that’s left is building a tuple of a specific length. There’s not much of a choice here – recursion is the way:
type Append<T extends any[], U> = [...T, U];
type CreateArrOfLen<
N extends number,
CurrArr extends any[] = []
> = CurrArr["length"] extends N
? CurrArr
: CreateArrOfLen<N, Append<CurrArr, any>>;
Combining all the pieces gives us this:
type Append<T extends any[], U> = [...T, U];
type CreateArrOfLen<
N extends number,
CurrArr extends any[] = []
> = CurrArr["length"] extends N
? CurrArr
: CreateArrOfLen<N, Append<CurrArr, any>>;
type Concat<A extends any[], B extends any[]> = [...A, ...B];
type Length<T extends any[]> = T["length"] extends number
? T["length"]
: never;
type Add<A extends number, B extends number> = Length<
Concat<CreateArrOfLen<A>, CreateArrOfLen<B>>
>;
Subtracting B from A is somewhat trickier. The approach is to match an array of length A against the shape of an array of size B concatenated with another array U, and then return the length of U.
// A = 5, B = 3
// [any, any, any, any, any]
// ^^^^^^^^^^^^^^|^^^^^^^^^
// B U
// ^^^^^^^^^^^^^^^^^^^^^^^^
// A
type Sub<A extends number, B extends number> = CreateArrOfLen<A> extends [
...CreateArrOfLen<B>,
...infer U,
]
? Length<U>
: 0;
To remain within natural numbers, we return 0 whenever a larger number is subtracted from a smaller one. So what we’ve really implemented is max(0, sub(a,b)).
Exercise for the reader: Have a go at implementing Multiply and Divide types :)
Thank you for reading! If you enjoyed this introduction to type-level programming, let us know, and make sure to subscribe to our blog for more posts like this one 👍🏻