Intro to Type Wizardry: Iteration, mapping and recursion with TS unions

TypeScript has an incredibly powerful type system. While most of our daily interactions with TypeScript only scratch the surface of its capabilities, delving into the source code of some of our favorite OS libraries reveals the depth of type magic that's there to improve our developer experience.

Unions are at the heart of TypeScript magic. They serve as the primary mechanism for type-level iteration and are often employed to implement numerous type-level algorithms. This article aims to compile (almost) everything there is to know about unions, enabling you to begin implementing your own magical APIs.

Understanding Unions

A union is a type that describes a value capable of being one of several types. We use vertical bars (|) to separate each type in a union.

We commonly create unions ourselves.

// Example 1: Union describing possible status of a fetch response
type Status = "pending" | "resolved" | "rejected";
type Response = { data: unknown; error: Error; status: Status };

function fetchProducts(): Response {
  /* ... */
}

// Example 2: Union describing props of a component that acts like either a button or anchor
type ButtonOrLinkProps =
  | {
      as?: "button";
      onClick: (e: Event) => void;
    }
  | {
      as: "a";
      href: string;
    };

function ButtonOrLink(props: ButtonOrLinkProps) {
  if (props.as === "a") {
    /* ... */
  }
}

// Example 3: Union Describing configuration options
type Options =
  | true // use capture
  | false // don't use capture
  | { capture: boolean; once: boolean; passive: boolean }; // advanced configuration

function addEventListener(
  target: string,
  callback: () => void,
  options: Options
): void {}

Additionally, unions are a natural outcome of certain TypeScript expressions. For instance, the keyof operator, when applied to an object type, generates a string or numeric literal union of its keys:

type MyObj = {
  foo: string;
  bar: number;
  baz: boolean;
};

type MyKeys = keyof MyObj; // "foo" | "bar" | "baz"

Similarly, extracting values from an array or tuple type through an array member expression ([]) results in a union:

// Getting the union out of array
let myArray = [42, "foo", true];
type MyArrayType = typeof MyArray; // Implicitly has a type of (number | string | boolean)[]
type MyUnionValues = MyArrayType[number]; // number | string | boolean

// Getting the union out of array
let myTuple = [42, "foo", true] as const;
type MyTupleType = typeof MyArray; // readonly [42, "foo", true]
type MyTupleValues = MyTupleType[number]; // 42 | "foo" | true

In the case of myArray, the type is implicitly inferred as the broadest possible array type, namely an array of the union number | string | boolean. Indexing the array type with any number (0, 1, 420) or just number yields the underlying union type.

Initializing an array with the as const type assertion creates a tuple with the narrowest possible type, such as readonly [42, "foo",true]. Tuples, unlike arrays, have a fixed width, allowing specific indexing to retrieve types at designated positions. For example, MyTupleType[0] returns the literal type 42. Indexing the tuple type with the general number type produces a union of types for every possible index.

Iteration with Distributive Conditional Types

Iteration is built into unions thanks to the distributive property of conditional types. If the combination of these terms seems unfamiliar, fear not—it'll all click soon.

Conditional types act as type-level ternary expressions, resolving into one of two branches of a type. They look something like this:

SomeType extends OtherType ? TrueBranch : FalseBranch;

They're most useful when nested within a generic type. Consider the GroupTypes type:

type GroupTypes<T> = T extends number ? { numberType: T } : { unknownType: T };

type NumberType = GroupTypes<11>; // { numberType: 11 }
type UnknownType = GroupTypes<"El">; // { unknownType: "El" }

Here, when GroupTypes encounters a number type, it transforms it into { numberType: T }. Otherwise, it outputs { unknownType: T }

What makes conditional types fascinating is their distributive property. If you provide a union of types for a single type argument, TypeScript will check each member of the union against the condition, and output the union of each check result:

type GroupTypes<T> = T extends number ? { numberType: T } : { unknownType: T };
type RandomUnion = 11 | "El" | number | boolean;

type Output = GroupTypes<RandomUnion>;
// { numberType: 11 } | { unknownType: "El" } | { numberType: number } | { unknownType: boolean }

In essence, we've created a union of data and mapped it to a new union of data — I don't know about you but this looks like iteration to me!

However, there's a limitation. If we want to map the union to a single specific shape, and not two distinct shapes, can we omit the conditional? The answer is no:

type MyArg = number | { value: number };
type ToFunctionArgs<T> = (arg: T) => void; // Creates a union of functions that receive T args

type MyFunction = ToFunctionArgs<MyArg>;
// ⚠️ Output: (arg: number | { value: number }) => void;
// ✅ Desired: ((arg: number) => void) | ((arg: { value: number }) => void

Omitting the conditional prevents distributivity. To address this, we turn to the never type. Think of never as Nothing. When found in a union, it is silently removed because, well, why include Nothing with Clearly Something?

type MyUnion = string | never | number | undefined | never;
// When inspected, it becomes: string | number | undefined

Utilizing the never type allows us to confidently create single-branched conditional types:

type MyArg = number | { value: number };
type ToFunctionArgs<T> = T extends T ? (arg: T) => void : never;

type MyFunction = ToFunctionArgs<MyArg>;
// ((arg: number) => void) | ((arg: { value: number }) => void

Notice the condition here. While you may encounter T extends unknown or T extends any instead of T extends T in some codebases, they all serve the same purpose — forcing distributivity.

Unions are automatically flattened. If a union is returned from a branch of a distributed conditional type, the result will be a single flattened union with more items than the initial union:

type MyUnion = "foo" | "bar";
type MyTransform<T> = T extends string ? T | Uppercase<T> : never;

type Out = MyTransform<MyUnion>; // "foo" | "FOO" | "bar" | "BAR"

Here, the native Uppercase utility type is used to return uppercase versions of the union along with the original type T, resulting in a union with double the items.

Thanks to the never type, we can also go the other direction — "filter" the union type to output a union with fewer items than the original. Let's demonstrate this by implementing a generally useful function — a function that filters out falsy values in an array:

type OnlyTruthy<T> = T extends false | 0 | "" | null | undefined ? never : T;

function onlyTruthy<T>(arr: T[]): OnlyTruthy<T>[] {
  return arr.filter((item) => !!item) as any;
}

// usage
let myArr = [42, undefined, "foo", null]; // Inferred as (number | undefined | string | null)[]
onlyTruthy(myArr); // Return Type: (number | string)[]

The onlyTruthy function effectively infers type T from its arguments: arr: T[] informs the compiler that T should be reconstructed from the values in the array arr. As we've learned earlier, the collection of items in an array is represented as a union, which is what the T type argument is inferred as. Finally, by returning OnlyTruthy<T>[], we filter out falsy values one by one, thanks to the distributive property of conditional types.

Note the need to convert the actual filtered value to any before returning it. This signals to TypeScript that we've taken care of the type conversion ourselves. In cases like these, it's common to separate type-level manipulation from runtime logic and connect them at the end.

Advanced Distributive Conditional Type Patterns

Union distribution isn't limited to just one type argument. As long as the type T stands naked in T extends SomeType ? TrueBranch : FalseBranch, it's distributed. A type is considered "naked" when it's not enclosed within another type, like SurroundedType<T> or [T] or T[]. You can chain as many conditionals over naked types as you like.

Distributing over multiple type arguments becomes valuable when you want to pair all the different combinations of union types. Consider representing all the combinations of two dice rolls:

type DiceRoll<T, U> = T extends T ? (U extends U ? [T, U] : never) : never;

type Sides = 1 | 2 | 3;
type Combos = DiceRoll<Sides, Sides>;
// Output:
// [1, 1] | [1, 2] | [1, 3]
// [2, 1] | [2, 2] | [2, 3]
// [3, 1] | [3, 2] | [3, 3]

Here, we've utilized nested conditional types to distribute over both T and U. False branches simply resolve into never because we're only interested in the "reachable" branch that outputs [T, U]. While the die in this example has three sides, represented by the union of Sides, you can add as many sides as you like, or even use two differently sided dice: DiceRoll<1 | 2, 1 | 2 | 3 | 4>.

When iterating with distributive conditional types on an object, accessing nested properties with a member expression (SomeType[Index]) is usually straightforward. But sometimes, you may want to iterate over other types and access a subtype that isn't accessible conventionally. These scenarios include accessing function parameters or return types, or extracting substrings from string literals. For such cases, TypeScript introduced the infer keyword.

infer is exclusively allowed in the extends clause of a conditional type. Its purpose is to infer and introduce a new subtype from an existing type. You can reference the inferred value using the name you assigned it within the body of the conditional type. For example, here's how you'd infer the first argument of a function using the infer keyword:

type FunctionUnion =
  | ((id: number) => void)
  | ((name: string, ignoredArg: boolean) => void);

type FirstArg<T> = T extends (arg: infer FirstArg, ...rest: any[]) => void
  ? FirstArg
  : never;

type Out = FirstArg<FunctionUnion>; // number | string

In this case, infer FirstArg is strategically placed where the first argument would be. Without infer FirstArg, the condition would be checking T extends (arg: any, ...rest: any[]) => void, which both function types of FunctionUnion satisfy. Since the condition is satisfied by both functions, TypeScript moves on to the true branch, which outputs the type we inferred at the position of the first argument.

If you want to further narrow the inferred type, you can write another extends clause next to the infer keyword. For example, here's how the conditional would look if we were only interested in first arguments that extend number:

type FunctionUnion =
  | ((id: number) => void)
  | ((name: string, ignoredArg: boolean) => void);

type FirstArg<T> = T extends (
  arg: infer FirstArg extends number,
  ...rest: any[]
) => void
  ? FirstArg
  : never;

type Out = FirstArg<FunctionUnion>; // number

With this adjusted syntax, the conditional check becomes T extends (arg: number, ...rest: any[]) => void, satisfied only by the first function type in the union. Hence, the inferred type is simply number from the first function type.

Another scenario where the infer keyword frequently appears is with string literal types. TypeScript's string literal types are robust and versatile, so we can't get into everything here. Thankfully, the syntax is very intuitive if you are familiar with JavaScript's template literals. Let's implement a utility type that converts string literal types into number literals:

type MyUnion = "42.69" | "123" | "foo";
type ToNumber<T extends string> = T extends `${infer Num extends number}`
  ? Num
  : never;

type Out = ToNumber<MyUnion>; // 42.69 | 123

This type iterates over string literals and checks if a string consists entirely of a substring that can be converted into a number. If so, it returns the inferred number type.

Mapping with in and keyof

Another form of iteration in TypeScript involves using the in operator. This operator works on a union and aims to map over an object's keys to construct a an object type. The right-hand side of in must be a union of string literals, number literals, or symbols, as these are the only allowed object keys in JavaScript.

const myUniqueSymbol = Symbol("some symbol");
type MyUnion = 42 | "foo" | typeof myUniqueSymbol;

type MyObject = {
  [K in MyUnion]: boolean;
};

// When inspected, MyObject becomes:
// {
//   42: boolean;
//   foo: boolean;
//   [myUniqueSymbol]: boolean;
// }

The in operator is particularly useful when you want to transform an object type into another object type with different properties. for this purpose, it's often combined with the keyof operator, which outputs a union of object keys:

type MyObject = {
  foo: string;
  bar: number;
};

type ToFunctionProperties<T> = {
  [K in keyof T]: (arg: T[K]) => void;
};

type Out = ToFunctionProperties<MyObject>;
// {
//   foo: (arg: string) => void;
//   bar: (arg: number) => void;
// }

The ToFunctionProperties utility type here maps over object types, preserving the keys, and transforms the properties into function types that receive the original properties as arguments. Note the use of K in (arg: T[K]) => void. The K type variable holds the current key name during each iteration of [K in keyof T], allowing us to access current properties on object T and remap them to function arguments.

We can also apply transformations to property names with the as operator. Let's modify the ToFunctionProperties type to uppercase the keys:

type MyObject = {
  foo: string;
  bar: number;
};

type ToFunctionProperties<T> = {
  [K in Extract<keyof T, string> as Uppercase<K>]: (arg: T[K]) => void;
};

type Out = ToFunctionProperties<MyObject>;
// {
//   FOO: (arg: string) => void;
//   BAR: (arg: number) => void;
// }

Here, the native Extract type is used to filter out non-string property names of T. We need it, because Uppercase expects a string as an argument. Even though we're transforming the properties, K in the right-hand side still references the original property names, as demonstrated by T[K] correctly accessing the original properties.

Conditional types can also be used inside mapped keys. For instance, let's implement another utility type:

type PickEvents<T> = {
  [K in keyof T as K extends `on${string}` ? K : never]: T[K];
};

type Out = PickEvents<HTMLInputElement>;
// {
//   onChange: (e: Event) => void;
//   onFocus: (e: Event) => void;
//   ...
// }

The PickEvents utility type selects keys that start with "on" and end with an arbitrary string, as specified by the K extends on${string} condition. Providing any HTMLElement type to PickElement as an argument will give us the specified events on the element.

Mapped types reserve the original data type of the mapped argument when specific conditions are met:

1. The keyof operator must be used within the type.
2. as or any other form of key filtering must not be used.

When a tuple is provided as an argument to our original ToFunctionProperties type, it outputs the transformed result as a tuple:

type ToFunctionProperties<T> = {
  [K in keyof T]: (arg: T[K]) => void;
};

type Out = ToFunctionProperties<["a", "b"]>;
// [(arg: "a") => void, (arg: "b") => void]

However, as soon as as is introduced, the tuple is treated like an object, yielding less desirable results:

type ToFunctionProperties<T> = {
  [K in keyof T as K]: (arg: T[K]) => void;
};

type Out = ToFunctionProperties<["a", "b"]>;
// {
//   [x: number]: (arg: "a" | "b") => void;
//   0: (arg: "a") => void;
//   1: (arg: "b") => void;
//   length: (arg: 2) => void;
//   toString: (arg: () => string) => void;
//   ...
// }

Reverse mapped types

Reverse mapping in TypeScript involves describing a "vague" shape of a type using the in and keyof operators instead of strict types, allowing the compiler to reconstruct the narrower type upon usage. This technique is particularly useful for inference and type validation.

Let's illustrate this concept with a configure function that returns the same configuration object it receives but performs type inference and validation using reverse mapped types.

function configure<T>(config: { [K in keyof T]: number }) {
  return config;
}

configure({ a: 1, b: 2 }); // All good.
configure({ a: 1, b: true }); // Error: type `boolean` is not assignable to type `number`.

Here, the function configure describes the shape of the argument using mapped type syntax, reconstructing T. If the argument doesn't match the shape described by the mapped type, an error is thrown.

Although this might seem like overcomplication, reverse mapped types provide precise control over inference. For instance, consider a theoretical render function in React that accepts element names and their props as an object:

render({
    button: {
        onClick: (e) => {}
        value: "Click Me"
    },
    a: {
        href: "/blog"
    }
})

Our goal is to provide inference and error reporting at each keystroke, including when specifying elements, props of the element, and arguments of events like onClick and onChange.

Let's implement this function step by step:

// This interface is available in React environments.
type Elements = React.JSX.IntrinsicElements; // { a: AnchorProps, button: ButtonProps, div: ... }

// Moved outside of `render` declaration for readability
type Config<T> = {
  [K1 in T]: {};
};

function render<T extends keyof Elements>(config: Config<T>) {}

render({
  button: {}, // Autocomplete for elements!!!
  a: {},
  someUnknownElement: {}, // Error: Object literal may only specify known properties
});

Here, we added constraint of extends keyof Elements to the type variable T. This is done to allow inference and autocomplete for element names. If you are wondering why we declared T to have constraint of extends keyof Elements instead of extends Elements, it's because it allows us to only specify just the subset of elements that we are interested in instead of every element in Elements type.

Let's see what happens when we use the T extends Elements constraint:

type Config<T> = {
  [K1 in keyof T]: {};
};

function render<T extends Elements>(config: Config<T>) {}

render({
  // Autocomplete still works but...
  button: {},
  // Type '{ button: {} }' is missing the following properties: a, abbr, address, area, and 172 more.(2345)
});

When using reverse mapped types, T is reconstructed based on our usage. In the first case, T is reconstructed as a union of specified properties ("button" | "a"). In the second case, it becomes an object type with our specified properties ({ button: {}, a: {} }).

While our reconstructed union extends the type constraint:

("button" | "a") extends ("button" | "a" | ... 175 other union values) ? true : false // true

The reconstructed object does not:

{ button: {}, a: {} } extends { button: {}, a: {}, ... 175 other object properties } ? true : false // false

Let's add prop inference:

type Config<T> = {
  [K1 in T]: {
    [K2 in keyof Elements[K1]]: {};
  };
};

function render<T extends keyof Elements>(config: Config<T>) {}

render({
  button: {
    // Autocomplete for props!
    value: {},
    onClick: {},
  },
  a: {
    value: {}, // Error: Object literal may only specify known properties
  },
});

Here, we use K1 from the previous "loop" to query the Elements, which gives us the current element's props, and once again iterate over its keys which this time gives us prop names of each element.

Finally, let's infer the values:

type Config<T> = {
  [K1 in T]: {
    [K2 in keyof Elements[K1]]: Elements[K1][K2];
  };
};

function render<T extends keyof Elements>(config: Config<T>) {}

render({
  button: {
    // Autocomplete for props!
    value: "Click Me",
    onClick: (event) => {
      // Event type is inferred automatically
    },
  },
  a: {
    href: "/blog",
    value: "Wrong Prop", // Error: Object literal may only specify known properties
  },
});

In this example, T was inferred as "button" | "a". You can use the T type variable further to validate another type argument, specify a return value, or apply additional transformations to T.

Recursion

Recursion, while not specific to unions, shares an important characteristic with union distribution: conditional types. As with any form of recursion, we must provide a base case to type-level recursion. In TypeScript, the only way to do this is with conditional types. Since conditional types automatically iterate over unions, mixing recursion with conditional types can either break our logic or, if used carefully, provide some really amazing results.

To demonstrate recursion, let's attempt to implement a type that prevents duplication in an array, given that we know every possible array item beforehand. One way we can do this is by creating a union type that includes every possible array combination for the given items. We can then use this type annotate the array value we are validating:

type UniqueArray<T> = ToBeImplemented;

type UniqueNumbers = UniqueArray<1 | 2 | 3>;
// | [1] | [2] | [3]
// | [1, 2] | [1, 3] | [1, 2, 3] | [1, 3, 2]
// | [2, 1] | [2, 3] | [2, 1, 3] | [2, 3, 1]
// | [3, 1] | [3, 2] | [3, 1, 2] | [3, 2, 1]

let x: UniqueNumbers = [1, 2]; // All good
let y: UniqueNumbers = [1, 1, 2]; // Error: Value is not assignable to type UniqueArray<1 | 2 | 3>

The UniqueArray type is a kind of utility type that can only be implemented through recursion. But before we do that, let's implement a similar logic with arrays in plain JavaScript to better understand what we are trying to do:

function uniquePairs(items) {
  // Base case
  if (items.length === 1) {
    return [items];
  }

  let pairs = [];

  for (let i = 0; i < items.length; i++) {
    // Remove current item from the list.
    // If items are [1, 2, 3], then 'excluded' becomes [2, 3], then [1, 3], then [1, 2]
    let excluded = items.filter((item) => item !== items[i]);

    // Recursively call the function with excluded items
    let smallerPairs = uniquePairs(excluded);

    pairs.push(
      // Keep one-item pairs so that bigger unique pairs can be constructed when we go up the call stack
      [items[i]],
      // Add the current item to each smaller pair to create unique combinations
      ...smallerPairs.map((pair) => [items[i], ...pair])
    );
  }

  return pairs;
}

uniquePairs([1, 2, 3]);
// [[1],[1,2],[1,2,3],[1,3],[1,3,2],[2],[2,1],[2,1,3],[2,3],[2,3,1],[3],[3,1],[3,1,2],[3,2],[3,2,1]]

While there's room for improvement in terms of performance, the focus here is on understanding the algorithm. This JavaScript implementation closely resembles the type-level algorithm we're aiming for. Take some time to play around with this function to grasp its workings, as we won't be able to inspect or debug the TypeScript solution directly.

Given the context we've covered in this article, you might already have ideas on how to translate this code into a type-level algorithm. Here's a summary of the steps:

• Iterate over the union with conditional types, which will also serve as our base case.
• Exclude each union member using the Exclude utility type.
• Create unions of unique tuples through recursion.

If you're up for the challenge, give it a go. I'll meet you there

.

.

.

.

.

.

.

.

.

type UniqueArray<T> =
  // Force distributivity & provide a base case (when every element is excluded T becomes never)
  T extends never
    ? [] // base case
    :
        | [T] // Keep one-item pairs so that bigger unique pairs can be constructed when we go up the call stack
        | [T, ...UniqueArray<Exclude<T, T>>]; // Add current item to each smaller pair to create unique combinations

At its core this is the exact same algorithm as our JavaScript function, but before you try to use it you should know there's a bug. It comes from Exclude<T, T>. Since we are distributing over T, on each iteration T references a single specific member of the union. This means Exclude<T, T> is resolved to never each time!

What we want is to keep track of unions as a whole as well as to iterate over each member with distribution, so we can do Exclude<WholeUnion, T>

We learned earlier that we can prevent distribution if we surround the distributed property with any type. Easiest way to do this and still maintain the logic of conditional is to surround both types with an array notation ([]).

type UniqueArray<T> =
  // No longer distributed!
  [T] extends [never] ? [] : [T] | [T, ...UniqueArray<Exclude<T, T>>];

Our bug is still not fixed though, because now that T is no longer distributed, we are always doing Exclude<WholeUnion, WholeUnion>

So, how can we make a type variable both distributed and not? Easy, we can introduce another type argument that has the same value as T and we just don't distribute over it:

type UniqueArray<T, U = T> = T extends never
  ? []
  : [T] | [T, ...UniqueArray<Exclude<U, T>>];

type UniqueNumbers = UniqueArray<1 | 2 | 3>;

let x: UniqueNumbers = [1, 2]; // All good
let y: UniqueNumbers = [1, 1, 2]; // Error: Value is not assignable to type UniqueArray<1 | 2 | 3>

And now our UniqueArray behaves as expected! Isn't it beautiful?

You Are a TypeScript Wizard Now

Now you know pretty much everything there is to know about unions and type-level iteration, which officially qualifies you as a TypeScript wizard!

For your next steps I suggest checking out some TypeScript utility libraries like millsp/ts-toolbelt. You should also consider hanging out in TypeScript communities, offering help to devs in need, as I think the best way to learn about TypeScript is to get your hands dirty and try it yourself.

If you enjoyed this article, please show support by leaving a 💖and let's talk in the comments!