Contents

Developing type-level algorithms in TypeScript

Mieszko Sabo

29 May 2023.11 minutes read

Developing type-level algorithms in TypeScript webp image

Yes, standard programming is pretty cool, but have you ever tried writing types that literally do more complex calculations than most to-do apps? Super-long build times, no side effects, obscure syntax, and confused comments from your colleagues in your PRs - that's the life of a type-level programmer.

Want to write a constant time bubble sort? Type-level interpreter? In this blog post, I'll guide you through the basic techniques that allow you to implement almost any algorithm using only TypeScript types.

Note that this post is quite long and covers many independent features of TypeScript. So instead of reading it all at once, feel free to bookmark this page and come back whenever you like.

What do we need to program?

When I think about the most useful language elements that I use in my daily programming, these come to mind:

  • data structures
  • functions
  • conditionals/code branching
  • loops
  • basic algebra (numbers, addition, multiplication, etc.)

If you think you could program anything with just the above - that's great because I will show you how we can emulate all of the above using just types! Here's the preview:

  • data Structures → object and tuple types
  • functions → generic types
  • conditionals/code branching → conditional types
  • loops → recursive types
  • basic algebra (numbers, addition, multiplication, etc.) → combining the above techniques with sneaky use of tuple lengths

Data structures/object and tuple types

This one is pretty straightforward. Note how similar TS objects are to object types:

const someObj = {
    a: "foo",
    b: { bar: "baz" },
  c: 42,
};

type someType = {
  a: "foo",
  b: { bar: "baz" },
  c: 42,
};

This one is pretty straightforward. Note how similar TS objects are to object types:

The difference here is that the "values" of the fields in someType are actually types that look like TypeScript values. It is because in TypeScript, a constant like 42 is both a value and a type, depending on the context it is in.

This nice feature, called literal types, is what allows us to write anything interesting at the type level. Otherwise, we would be left with types like number or string, which are much less specific and, therefore - much less expressive.

In the following sections, we'll see some useful ways to interact 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

Although in value level TS we can use both the dot syntax, e.g., user.name, and the square brackets syntax, e.g. user["name"], in type level TS it seems that we can only use the brackets syntax. The big twist is that instead of just a field name as a string, we put a type inside the brackets. Whatever keys are matched by that type - their corresponding types are returned:

type NameOrAge = User["age" | "name"];
//   ^ string | number 🤯

type UserKeys = keyof User;
//   ^ "name" | "age" | "isAdmin"

type UserValues = User[UserKeys];
//   ^ string | number | boolean

Note how this way of getting a union of all the object values types can be made into a generic type (and thus work with 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

We can merge objects using the intersect type (&). To understand how this works, let's take a closer look:

type I = A & B;

We can think of the above as "I is of type A and B at the same time". In other words, a variable of type I can be assigned to both a variable of type A and a variable of type B.

What is the "smallest" type that satisfies this constraint if A and B are objects? An object that has all the fields of A and B! Provided there are no conflicting fields (e.g., both A and B have a key "foo", but of different types), that's what merging is effective!

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 work in a similar way to their value-level versions popularised by libraries like lodash or ramda. The difference, of course, as you've probably guessed, is that the arguments are arbitrary types and not just 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; }

Moving on to the tuples, here are some of their interesting properties.

Reading elements

Reading elements of a tuple is analogous to what we have done 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 difference is just that to get a union of all elements; the preferred way is to index the tuple with a number instead of the key of SomeTuple. That's because the latter way gives us all the properties that live on TypeScript arrays, like length, map, etc., which is usually not the desired output:

type AllKeys = SomeTuple[number]; // string | number | boolean

Concatenating tuples

Just like in value level TS, you can concatenate tuples with 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

Once again, I'll start this section with a contrived example in which JS functions and TS generic types look extremely similar:

// value-level JavaScript
const makeTuple = (a, b) => [a, b];

// type-level TypeScript
type makeTuple<a, b> = [a, b];

The variables inside the sharp brackets are usually referred to as type parameters, and just like in normal functions, you can use them on the right side, and whenever this type is "called" with some types, the type parameters will be replaced with them and a concrete type will be evaluated.

type double<T> = [T, T];

type doubleString = double<string> // [string, string]

type doubleNubmer = double<number> // [number, number]

If we did not have generics, we would have to write the double type for every type we would use!

But wait, do we always have to write generic types in such a way that they can work with all types? Fortunately not, we can use something called types constraints to limit the set of possible 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!

Some limitations that the generic types have:

  • We can’t make higher-order generic types, i.e., a generic type that takes or returns another generic type.
  • The whole “body” of a generic type has to be a single expression, not a series of statements like in value-level TypeScript.

Code branching/conditional types (+ infer)

We can emulate the if/else branching with conditional types. Here's an example:

type isString<T> = T extends string ? true : false;

type res1 = isString<"ala">; // true

type res2 = isString<42>; // false

A conditional type consists of three parts. A condition, an if case, and an else case:

type isString<T> = T extends string ? true : false;
//                 ^^^^^^^^^^^^^^^^   ^^^^   ^^^^^
//                 condition          if     else

It looks and works almost exactly like the ternary operator in JavaScript. The main difference is that instead of a boolean value in the first part, you have to use an extends expression. In short, extends checks if the first type is a subtype of the second type. The example above checks whether the generic type T is a subtype of string. We can emulate the ternary operator at the type level by using 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

Although nesting ternary operators is an anti-pattern in pure JavaScript because it affects readability, we have no other choice in type-level programming, so we have to go with it.

type And<A extends boolean, B extends boolean> = A extends true
  ? B extends true
    ? true
    : false
  : false;

Infer keyword

The extends keyword in conditional types allows us to check if a generic type matches a shape. The infer allows us to capture parts of that shape in a variable and use it in a `then' branch.

Let's go 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
  1. We create a pattern that we want to check if the generic argument matches.
  2. We use infer keywords in parts of this pattern that we want to capture in variables.
  3. If the type argument matches this pattern, we can use the captured variables.

Loops/recursive types

While loops are not supported at the type level, we can use recursion to implement any logic that requires iteration. The general idea of a recursive type is as follows:

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>>;

A common use case for recursive types is to find something in a tuple or string. For example, let me show you how to extract the last element in 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"

In each iteration, we try to split the path at first /. If we succeed, then we recursively use the type with the part of the path after the first /. We hit our base case when there is no / in the path. This means we have found the last element, so we return it and end the recursion.

Basic algebra

Doing arithmetic on type-level numbers is not officially supported in TypeScript. However, that doesn't stop programmers from abusing the length property of tuples to at least emulate the algebra of natural numbers. Here's how it works.

type len = [1, 2, 3, 4]["length"]
//   ^ 4 🤯

That's right! You would think that number would be a reasonable type for the length property. But since the lengths of tuples are known at compile time, TypeScript can be more specific.

Here's the recipe for adding two numbers, a and b, that take advantage of this behavior:

  • create a tuple of length a
  • create a tuple of length b
  • concatenate them
  • read the length property of the concatenated tuple

And this is how it looks in the code:

type Add<A extends number, B extends number> = Length<
    Concat<CreateArrOfLen<A>, CreateArrOfLen<B>>
  >;

I've already shown how to read properties and concatenate tuples, so the only thing missing is creating a tuple of a given length. We don't have much choice: we have to use recursion:

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>>;

So when you put it all together, you get 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 a bit more tricky. The idea is to match the shape of an array of length A with an array of size B concatenated with some other array U, and 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 stay in natural numbers, we return 0 when we try to subtract a larger number from a smaller one. So the actual operation we have implemented is max(0, sub(a,b)).

Exercise for the reader: Try to implement Multiply and Divide types :)

Thanks for reading! If you liked this introduction to type-level programming, please let us know, and be sure to subscribe to our blog for more articles like this one 👍🏻

Technical review by: Piotr Majcher

Blog Comments powered by Disqus.