Compile-time functional programming in TypeScript

Started with Competitive Programming and after a journey through Information Security, Robotics, Game Development and Machine Learning ended up in Frontend Development. What's next?

You probably know that TypeScript is a language. But did you know that TypeScript is a language? Meaning, not the JavaScript that it transpiles to, but its actual type system? Check this out: 

This is TypeScript calculating Fibonacci numbers at compile-time. No JavaScript, no running the code, just the type system alone. 

So, how does it work? 

Real world usages

Before we deep dive into theory and experiments, it is worth mentioning that these concepts are actually useful in real applications. Sure, you’ll never need to calculate Fibonacci numbers with your types, but understanding the principles behind it can help you solve some practical problems. 

For example, at Mews we once needed to get an intersection of multiple interfaces dynamically – and we were able to easily achieve it using the methods described in the following sections: 

type Intersection<A extends Array<unknown>> = 
    A extends [infer First] 
        ? First 
    : A extends [infer First, ...infer Rest] 
        ? First & Intersection<Rest> 
    : never; 
type X = Intersection<[A, B, C]>;  // A & B & C 

We also had a problem with automatically generating and typing the methods for working with dates. And, once again, using the conditional types and a bit of Template Literal Types and Key Remapping we were able to solve it. 

// Plural<'day'>  -> 'days' 
// Plural<'days'> -> 'days' 
type Plural<S extends string> = 
    S extends `${infer _}s` 
        ? S 
        : `${S}s`;  
type Accessors<Entity, Parts> = { 
    [P in Parts as `get${Capitalize<Plural<string & P>>}`]: (entity: Entity) => number; 
} 
type X = Accessors<DateEntity, 'years' | 'month' | 'week' | 'days'>; 
// { 
//     getYears: (entity: DateEntity) => number; 
//     getMonths: (entity: DateEntity) => number; 
//     getWeeks: (entity: DateEntity) => number; 
//     getDays: (entity: DateEntity) => number; 
// } 

The types above might look a bit confusing, but don’t worry – now that we know the practical benefits of compile-time functional programming, we can start from the beginning and see how far we can take it. 

The basics 

TypeScript 2.8 introduced Conditional Types. The concept is simple – when defining a generic type, you can conditionally change the result based on the received argument. For example:  

type IsString<T> = T extends string ? true : false; 
type X = IsString<'123'>;  // true 
type Y = IsString<123>;    // false 

Being able to “execute” different things based on the input is one of the most important features of a language. But what really pushes it over the edge for TypeScript is Type Inference. It allows us to do a conditional check on a type, and then later use the information we got from it. For example, the following type returns the first element of the array type it receives:  

type Head<T> = T extends [infer H, ...infer Rest] ? H : never;  
type X = Head<[1, 2, 3]>;  // 1 

It checks whether the type extends [H, ...Rest], and if it does, it allows us to use the inferred types of H and Rest. The rest of the type is trivial – we just return H, the first element of the array.

This might look simple at first, but it’s incredibly powerful. Basically, it provides a way for us to do pattern matching on types, just like we would do in a functional language. 

Let’s get functional 

Using the concept of pattern matching we can start solving some of the classic functional programming problems. We already know how to get the first element of an array, but we can do better. For example, we can reverse a list: 

type Reverse<A> = A extends [infer First, ...infer Rest] 
    ? [...Reverse<Rest>, First] 
    : A;
type X = Reverse<[1, 2, 3, 4, 5]>;  // [5, 4, 3, 2, 1] 

We can check if a list is a palindrome: 

type IsPalindrome<A> = 
    A extends [infer First, ...infer Rest, infer Last] 
        ? First extends Last 
            ? IsPalindrome<Rest> 
            : false 
        : true; 
type X = IsPalindrome<[1, 2, 3, 2, 1]>;  // true 
type Y = IsPalindrome<[1, 2, 3, 1]>;     // false 

Or we can flatten a list: 

type Flatten<A> = 
    A extends [infer First, ...infer Rest] 
        ? First extends Array<unknown> 
            ? [...First, ...Flatten<Rest>] 
            : [First, ...Flatten<Rest>] 
        : A; 
type X = Flatten<[1, [2, 3], [4, 5, 6]]>;  // [1, 2, 3, 4, 5, 6] 

And in a normal app, usually you wouldn’t need to go any further than this. But we’re already here, so let’s dive a bit deeper. 

Working with numbers 

Unfortunately, the type system in TypeScript doesn’t support basic math. It wouldn’t even allow you to add numbers: 

type Three = 1 + 2;  // Syntax error

But there is a way around it – arrays! TypeScript does allow you to manipulate them in many ways, including some fancy inferences like in the example above. And, most importantly, it allows you to get the length of an array, practically giving you the option to manipulate numbers – we can turn numbers into arrays, manipulate them in any way we want, and then turn them back into numbers. 

Let’s create a few types that will help us do this: 

type ToNumber<A extends Array<unknown>> = A['length']; 
type ToArray<N extends number> = _ToArray<N, []>; 
type _ToArray<N extends number, A extends Array<unknown>> = 
    ToNumber<A> extends N 
        ? A 
        : _ToArray<N, [...A, undefined]>; 
type X = ToNumber<[undefined, undefined, undefined]>;  // 3 
type Y = ToArray<3>;  // [undefined, undefined, undefined] 

As a side note, here you can see me creating two versions of the second helper – ToArray and _ToArray. This is a common trick we will be using when a type has a default value for one of the arguments. We could try setting the default value in the generic definition itself, but, unfortunately, TypeScript doesn’t allow you to both extend an argument and specify its default value, so it wouldn’t always work. 

TypeScript, D&D, game development…

Just to name a few perks of working with Alex. ✌

It is also worth mentioning that these helpers, as well as all the types in the rest of this section, don’t support negative numbers. It is possible to do it, but that’s a layer of complexity we can skip for now. 

Now, with these helpers we can start doing some basic math – for example, adding numbers: 

type _Add<A extends Array<unknown>, B extends Array<unknown>> = [...A, ...B]; 
type Add<A extends number, B extends number> = 
    ToNumber< 
        _Add< 
            ToArray<A>, 
            ToArray<B> 
        > 
    >; 
type X = Add<3, 9>;    // 12 
type Y = Add<13, 21>;  // 34 

Subtracting numbers: 

type _Subtract<A extends Array<unknown>, B extends Array<unknown>> = 
    A extends [...infer A1, undefined] 
        ? B extends [...infer B1, undefined] 
            ? _Subtract<A1, B1> 
        : A 
    : A; 
type Subtract<A extends number, B extends number> = 
    ToNumber< 
        _Subtract< 
            ToArray<A>, 
            ToArray<B> 
        > 
    >; 
type X = Subtract<13, 5>;  // 8 
type Y = Subtract<7, 7>;   // 0 

Or comparing them: 

type _Greater<A extends Array<unknown>, B extends Array<unknown>> = 
    A extends [...infer A1, undefined] 
        ? B extends [...infer B1, undefined] 
            ? _Greater<A1, B1> 
            : true 
        : false; 
type Greater<A extends number, B extends number> = 
    _Greater< 
        ToArray<A>, 
        ToArray<B> 
    >; 
type X = Greater<13, 5>;  // true 
type Y = Greater<5, 13>;  // false 

Once again, you can see me using two versions of each type – one of them works on arrays, and the other works on numbers. 

With these helpers we can solve a whole different level of problems. 

You’ll probably never need this 

Having the option of working with numbers, we can take a look at a few more classic functional programming exercises.  

We can find the maximum number in an array: 

type _Max<A extends Array<number>, R extends number> = 
    A extends [infer First, ...infer Rest] 
        ? First extends number  // Unfortunately, TS doesn't infer the actual type automatically. 
            ? Rest extends Array<number> 
                ? Greater<First, R> extends true 
                    ? _Max<Rest, First> 
                    : _Max<Rest, R> 
                : R 
            : R 
        : R; 
type Max<A extends Array<number>> = _Max<A, 0>; 
type X = Max<[1, 2, 1, 3, 2, 1]>;  // 3 
type Y = Max<[1, 2, 3, 4, 5]>;     // 5 

We can even sort an array using merge sort: 

// Merge<[1, 2, 5, 7], [3, 4, 6]> -> [1, 2, 3, 4, 5, 6, 7] 
type Merge<A extends Array<number>, B extends Array<number>> = 
    A extends [infer FirstA, ...infer RestA] 
        ? B extends [infer FirstB, ...infer RestB] 
            ? FirstA extends number ? RestA extends Array<number> ? FirstB extends number ? RestB extends Array<number> 
                ? Greater<FirstA, FirstB> extends false 
                    ? [FirstA, ...Merge<RestA, B>] 
                    : [FirstB, ...Merge<A, RestB>] 
                : [] : [] : [] : [] 
            : A 
        : B; 
// Split<[1, 2, 3, 4, 5, 6, 7]> -> [[1, 2, 3, 4], [5, 6, 7]] 
type Split<A extends Array<number>> = _Split<A, [], []>; 
type _Split<A extends Array<number>, L extends Array<number>, R extends Array<number>> = 
    A extends [infer First, ...infer Rest, infer Last] 
        ? First extends number ? Rest extends Array<number> ? Last extends number 
            ? _Split<Rest, [...L, First], [Last, ...R]> 
            : [[], []] : [[], []] : [[], []] 
    : A extends [infer First] 
        ? [[...L, First], R] 
    : [L, R]; 
type MergeSort<A extends Array<number>> = 
    Split<A> extends [infer L, infer R] 
        ? L extends Array<number> ? R extends Array<number> 
            ? R['length'] extends 0 
                ? L 
                : Merge<MergeSort<L>, MergeSort<R>> 
            : never : never 
        : never; 
type X = MergeSort<[2, 1, 3, 5, 4, 6, 7]>;  // [1, 2, 3, 4, 5, 6, 7] 
type Y = MergeSort<[2, 1, 3]>;              // [1, 2, 3] 
type Z = MergeSort<[1]>;                    // [1] 

Finally, as promised at the start of this article, we can calculate the Fibonacci numbers: 

type Fib<N extends number> = 
    Greater<N, 1> extends true 
        ? Add< 
            Fib<Subtract<N, 1>>, 
            Fib<Subtract<N, 2>> 
        > 
        : 1; 
type F0 = Fib<0>;  // 1 
type F1 = Fib<1>;  // 1 
type F2 = Fib<2>;  // 2 
type F3 = Fib<3>;  // 3 
type F4 = Fib<4>;  // 5 
type F5 = Fib<5>;  // 8 

Now, as you might have noticed, all of the types above do a bunch of conversions from arrays to numbers and back, so there’s definitely some space for optimizations. But still, how cool is that? 

Realistically, though, you’ll never need to do any of this in a real application. It does, however, show off the amazing capabilities of TypeScript, and the cool things you can do with it. 

To sum up 

TypeScript’s type system is incredibly powerful. Its conditional type inference system allows you to do pretty much anything at compile-time, and it’s actually useful in real-world applications. Sure, you’ll never need to sort an array using types, but just in case you do – TypeScript’s got you covered. 

Featured image by Ludde Lorentz on Unsplash

Started with Competitive Programming and after a journey through Information Security, Robotics, Game Development and Machine Learning ended up in Frontend Development. What's next?
Share:

More About &