Yurii Honcharenko

Recursive conditional types in TypeScript and tuples

While writing my previous blog post, I started to think about other strongly typed languages and whether it would be possible to create a type that describes an array of fixed size.

In TypeScript, the array type is either Array<T> or T[]. So obviously, the type itself doesn't encode the size, and it makes sense, since arrays in JavaScript are dynamic, and don't have a fixed length.

However, TypeScript has tuples. A tuple is represented with an array in JavaScript, but TypeScript compiler will enforce the correct number of tuple members and their types. This means that tuple size is actually part of its signature. So the type of a tuple of three numbers is [number, number, number]. Since a tuple is just an array, in theory, we could use this type annotation to type check the array size. But in practice, it's not really convenient, for example, if our array has to contain 30 numbers, its type signature would be:

type MyArray = [number, number, /* ...and so on, 28 more times. */ ];

However, we could use recursive conditional types to automatically generate the needed type. The PR that added this feature to TypeScript even has an example that does precisely that. I took the example type (called TupleOf there), changed the naming and simplified the code a bit:

// "public" type
type FixedSizeArray<T, N extends number> = N extends N
    ? FixedSizeArrayBuilder<T, N, []>
    : never;

// "private" type
type FixedSizeArrayBuilder<T, N extends number, R extends T[]> = R['length'] extends N
    ? R
    : FixedSizeArrayBuilder<T, N, [T, ...R]>;

// usage:
const myArray: FixedSizeArray<number, 3> = [1, 2, 3];

T is the type of items in our array (tuple), and N is its length.

Let's try to figure out what this type signature actually means.

First of all, why there are two types? You can think of FixedSizeArrayBuilder as a "private" type. This "private" type allows us to hide the third type variable R which is used for recursion and should not be exposed.

Also, splitting the type definition into two smaller types makes them easier to read and understand. It would be possible to write this type using one type definition, but nested ternaries would make it impossible to read.

Besides improving readability, it allows us to use union types for N type parameter. That is what N extends N is for.

export type FixedSizeArray<T, N extends number> = N extends N
                                              // ^^^ this

We might want to make sure our array has exactly 2 or 4 elements. However, if we use the type parameter N as it is, the final type will be incorrect:

type FixedSizeArray<T, N extends number> = FixedSizeArrayBuilder<T, N, []>
const wheelInfo: FixedSizeArray<number, 2 | 4>;
// type expanded to: [number, number];

The correct type should've been [number, number] | [number, number, number, number], but it looks like only the first value of the 2 | 4 union was used. To make sure our type definition is applied for every member of the union of type variable N, we need to turn into a "distributive type" (TS Docs: Distributive Conditional Types When conditional is used with a generic type, that generic type becomes "distributive", and that's what N extends N is for. The condition itself doesn't matter, as long as it evaluates to true, the type will be "expanded".

In addition to type variables T and N we've seen before, FixedSizeArrayBuilder has an additional parameter, R. You can think of it as an "accumulator" variable that's usually used when iterating using a recursion. Let's look at the first branch of the ternary:

R['length'] extends N
  ? R
  // rest of the type

This is the base case of recursion. The recursion stops when length property of array R extends N. It's a TypeScript way of saying R.length == N.

Second branch of the ternary is the actual recursive type definition. On every iteration of the recursion, a single type T will be added to "accumulator" type R:

FixedSizeArrayBuilder<T, N, [T, ...R]>;

Here's how a similar recursion would look in TypeScript:

function repeat<T>(valueToRepeat: T, times: number, acc: T[] = []): T[] {
    return acc.length === times
        ? acc
        : repeat(valueToRepeat, times, [valueToRepeat, ...acc]);
}
repeat('A', 5) // => ["A", "A", "A", "A", "A"]

I think it's pretty cool that the "regular" TypeScript code maps to this recursive type definition almost one to one.

As you can see, it's possible to describe almost any type, using recursive conditional types. However, there's a limitation on the recursion depth. TypeScript won't let you to declare a type that has a very deep recursion depth:

let tooLarge: FixedSizeArray<number, 999>;
// Error!
// Type instantiation is excessively deep and possibly infinite.

Nevertheless, it's a useful type, especially if you're using noUncheckedIndexedAccess compiler flag.

const sampleData: User[] = [
  { name: 'Bob' },
  { name: 'John' },
];

const firstUser = sampleData[0];
console.log(firstUser.name); // => Error: 'firstUser' is possibly 'undefined'.

You can fix this error with a tuple:

const sampleData: [User, User] = [
  { name: 'Bob' },
  { name: 'John' },
];

Or with the FixedSizeArray type that will make the tuple for you:

const sampleData: FixedSizeArray<User, 2> = [
  { name: 'Bob' },
  { name: 'John' },
];

const firstUser = sampleData[0];
console.log(firstUser.name); // => No error here anymore!

Pretty convenient!