Close Menu

    Recursive Types in TypeScript: A Brief Exploration

    It is said that there are two different worlds in TypeScript that exist side by side: the type world and the value world.

    Consider this line of code:

    <span class="hljs-keyword">const</span> firstName: <span class="hljs-built_in">string</span> = <span class="hljs-string">'Maynard'</span>;

    While firstName and 'Maynard' live in the value world, string belongs to the type world.

    Or, consider the typeof operator that exists in both worlds.

    Here it is in the value world:

    <span class="hljs-built_in">console</span>.log(<span class="hljs-keyword">typeof</span> <span class="hljs-number">42</span>); <span class="hljs-comment">// number</span>

    And, here it is in the type world, used for extracting the type of the function increment, which is then passed to a utility type called ReturnType:

    <span class="hljs-function"><span class="hljs-keyword">function</span> <span class="hljs-title">increment</span>(<span class="hljs-params">n: <span class="hljs-built_in">number</span></span>) </span>{
  <span class="hljs-keyword">return</span> n + <span class="hljs-number">1</span>;
}

<span class="hljs-keyword">type</span> T = ReturnType<<span class="hljs-keyword">typeof</span> increment>; <span class="hljs-comment">// number</span>

    One of the wonders of the type world is the existence of recursive types – types that refer to themselves. They are somewhat similar to recursive functions that you might already be familiar with.

    Here is a recursive function:

    <span class="hljs-function"><span class="hljs-keyword">function</span> <span class="hljs-title">addUpTo</span>(<span class="hljs-params">n: <span class="hljs-built_in">number</span></span>): <span class="hljs-title">number</span> </span>{
  <span class="hljs-keyword">if</span> (n === <span class="hljs-number">0</span>) {
    <span class="hljs-keyword">return</span> n;
  }

  <span class="hljs-keyword">return</span> n + addUpTo(n - <span class="hljs-number">1</span>);
}

    And, here is a recursive type:

    <span class="hljs-keyword">type</span> JSONValue =
  | <span class="hljs-built_in">string</span>
  | <span class="hljs-built_in">number</span>
  | <span class="hljs-built_in">boolean</span>
  | <span class="hljs-literal">null</span>
  | { [key: <span class="hljs-built_in">string</span>]: JSONValue };

    The function addUpTo calls itself, each time with a lesser value of n, gradually reaching the base case. (n is assumed to be a nonnegative number, otherwise, we’ll have the Maximum call stack size exceeded error.)

    The type JSONValue is a union type that has an index signature in one of its possible types ({ [key: string]: JSONValue }), and the value is a reference to itself.

    To see it with an example, let’s say we have an object person that has the properties name, age, and friends:

    <span class="hljs-keyword">const</span> person = {
  name: <span class="hljs-string">'Alice'</span>,
  age: <span class="hljs-number">25</span>,
  friends: {
    <span class="hljs-number">0</span>: {
      name: <span class="hljs-string">'Bob'</span>,
      age: <span class="hljs-number">23</span>,
      friends: {
        <span class="hljs-comment">// ...</span>
      }
    },
    <span class="hljs-number">1</span>: {
      name: <span class="hljs-string">'Carol'</span>,
      age: <span class="hljs-number">28</span>,
      friends: {
        <span class="hljs-comment">// ...</span>
      }
    },
    <span class="hljs-comment">// ...</span>
  }
};

    The value of friends is an object that has numbers as its properties, each having the value that looks just like the person we’ve just defined. So, we can create a Person type for it where the value of friends is an object that also has the value type Person:

    <span class="hljs-keyword">type</span> Person = {
  name: <span class="hljs-built_in">string</span>;
  age: <span class="hljs-built_in">number</span>;
  friends: {
    [key: <span class="hljs-built_in">number</span>]: Person;
  };
};

    Note: In JavaScript, object keys are either strings or symbols. Even if we define key as a number, JavaScript eventually will coerce the object keys to strings.

    In this article, we’ll not only take a look at what recursive types are in TypeScript, but we’ll also see how they can apply to recursive data structures and how they can be useful with two different use cases.

    It can be an excellent tool in your toolkit for very specific circumstances such as when you need to extend a utility type or get the “inner” type of a multidimensional array.

    Let’s begin our exploration.

    Here’s what we’ll cover:

    1. Recursive Types for Trees and Linked Lists

    2. Recursion with Mapped and Conditional Types

    3. Use Cases for Recursive Types

    4. Conclusion (and a Warning!)

    Recursive Types for Trees and Linked Lists

    Recursive types are probably best understood with a data structure like a tree:

    A binary tree where the root node has two children, left and right. The left child has left and right children, each of them also has left and right children of their own. The right child of the root node has a left child that has a left child of its own, and a right child that is a leaf node.

    For example, a node of a binary tree has at most two children, left and right. A child node, if it also has children, is the root of a subtree itself.

    We can create a TreeNode type for a binary tree:

    <span class="hljs-keyword">type</span> TreeNode<T> = {
  value: T;
  left: TreeNode<T> | <span class="hljs-literal">null</span>;
  right: TreeNode<T> | <span class="hljs-literal">null</span>;
};

    It is a generic type, so the value can be any type that we pass to it. The left and right children can be either TreeNode themselves or null.

    Let’s say we have this binary tree:

    A binary tree that has the value 8 as its root node. It has a left child with the value 3 and a right child with the value 10. The left child has a left child node that has the value 1 and a right child node that has the value 6, which has a left child node with the value 4 and a right child node with the value 7. The right child of the root node that has the value 10 has a right child node with value 14, which has a left child node that has the value 13.

    We can represent it just like this, with the type of TreeNode that we’ve just defined:

    <span class="hljs-keyword">const</span> binaryTree: TreeNode<<span class="hljs-built_in">number</span>> = {
  value: <span class="hljs-number">8</span>,
  left: {
    value: <span class="hljs-number">3</span>,
    left: {
      value: <span class="hljs-number">1</span>,
      left: <span class="hljs-literal">null</span>,
      right: <span class="hljs-literal">null</span>
    },
    right: {
      value: <span class="hljs-number">6</span>,
      left: {
        value: <span class="hljs-number">4</span>,
        left: <span class="hljs-literal">null</span>,
        right: <span class="hljs-literal">null</span>
      },
      right: {
        value: <span class="hljs-number">7</span>,
        left: <span class="hljs-literal">null</span>,
        right: <span class="hljs-literal">null</span>
      }
    }
  },
  right: {
    value: <span class="hljs-number">10</span>,
    left: <span class="hljs-literal">null</span>,
    right: {
      value: <span class="hljs-number">14</span>,
      left: {
        value: <span class="hljs-number">13</span>,
        left: <span class="hljs-literal">null</span>,
        right: <span class="hljs-literal">null</span>
      },
      right: <span class="hljs-literal">null</span>
    }
  }
};

    Since this is a generic type, we’re passing to it the type number that’s used as the type of value.

    Similarly, we can create a type for a linked list where each node has a value and a next property that either points to another node or null:

    <span class="hljs-keyword">type</span> LinkedList<T> = {
  value: T;
  next: LinkedList<T> | <span class="hljs-literal">null</span>;
};

    So, if our linked list looks like this:

    A linked list where the head points to the node with the value 1, which points to the node with the value 2, which points to the node with the value 3 that points to null.

    We can represent it like this, with the type LinkedList:

    <span class="hljs-keyword">const</span> linkedList: LinkedList<<span class="hljs-built_in">number</span>> = {
  value: <span class="hljs-number">1</span>,
  next: {
    value: <span class="hljs-number">2</span>,
    next: {
      value: <span class="hljs-number">3</span>,
      next: <span class="hljs-literal">null</span>
    }
  }
};

    Note: We used type aliases in the examples above, but we can also use an interface instead:

    <span class="hljs-keyword">interface</span> TreeNode<T> {
  value: T;
  left: TreeNode<T> | <span class="hljs-literal">null</span>;
  right: TreeNode<T> | <span class="hljs-literal">null</span>;
}

<span class="hljs-keyword">interface</span> LinkedList<T> {
  value: T;
  next: LinkedList<T> | <span class="hljs-literal">null</span>;
}

    Recursion with Mapped and Conditional Types

    Applying recursive types to values representing recursive data structures is a bit obvious and not too exciting, but we can explore other options where recursion can also be used, such as mapped and conditional types.

    Mapped types are a convenient way to create a new type based on another one. We can, for example, create a new type using the keys of an object, where we map the keys to a different value type.

    Let’s say we have a colors object that has color names and the corresponding hex values. The values are of string type, but let’s say we want to create an object type where the keys are the same, except that the type of the values should be boolean:

    <span class="hljs-keyword">const</span> colors = {
  aquamarine: <span class="hljs-string">'#7fffd4'</span>,
  black: <span class="hljs-string">'#000000'</span>,
  blueviolet: <span class="hljs-string">'#8a2be2'</span>,
  goldenrod: <span class="hljs-string">'#daa520'</span>,
  indigo: <span class="hljs-string">'#4b0082'</span>,
  lavender: <span class="hljs-string">'#e6e6fa'</span>,
  silver: <span class="hljs-string">'#c0c0c0'</span>
};

<span class="hljs-keyword">type</span> ColorsToBoolean<T> = {
  [K <span class="hljs-keyword">in</span> keyof T]: <span class="hljs-built_in">boolean</span>;
};

<span class="hljs-keyword">type</span> Result = ColorsToBoolean<<span class="hljs-keyword">typeof</span> colors>;

    The Result type then will look like this:

    A screenshot of the code block that's defined above when it's hovered over the type `Result`. Keys are the same as the ones in the `colors` object, and all the values are `boolean`.

    In order to create a recursive mapped type, however, we need a reference to the same type that we’re creating, like this:

    <span class="hljs-keyword">type</span> Recursive<T> = {
  [K <span class="hljs-keyword">in</span> keyof T]: Recursive<T[K]>;
};

    Before going further, let’s also take a look at the conditional types, which look very similar to the conditional expressions that use the ternary operator:

    AType <span class="hljs-keyword">extends</span> AnotherType ? ResultTypeIfTrue : ResultTypeIfFalse;

    It has this familiar form:

    condition ? resultIfTrue : resultIfFalse

    Now, we can combine both mapped and conditional types to create a recursive mapped conditional type:

    <span class="hljs-keyword">type</span> Recursive<T> = {
  [K <span class="hljs-keyword">in</span> keyof T]: T[K] <span class="hljs-keyword">extends</span> <span class="hljs-built_in">number</span> ? T[K] : Recursive<T[K]>;
};

    We map the keys of the given object type to the same value type if it’s a number, otherwise, continue with the recursion.

    Use Cases for Recursive Types

    Use Case 1: DeepPartial

    One use case of recursive types is extending the capabilities of the utility type Partial.

    Let’s say we have a type for an article, using an interface this time:

    <span class="hljs-keyword">interface</span> IArticle {
  title: <span class="hljs-built_in">string</span>;
  description: <span class="hljs-built_in">string</span>;
  url: <span class="hljs-built_in">string</span>;
  author: {
    name: <span class="hljs-built_in">string</span>;
    age: <span class="hljs-built_in">number</span>;
  };
}

    Partial makes all the properties of an object type that it’s given optional.

    But, if we try to do this:

    <span class="hljs-keyword">const</span> article: Partial<IArticle> = {
  title: <span class="hljs-string">'Navigating the Mysteries'</span>,
  description:
    <span class="hljs-string">'As we walk our questions into a troubled future, storyteller and mythologist Martin Shaw invites us to subvert today’s voices of certainty and do the hard work of opening to mystery.'</span>,
  url: <span class="hljs-string">'https://emergencemagazine.org/essay/navigating-the-mysteries'</span>,
  author: {
    name: <span class="hljs-string">'Martin Shaw'</span>
  }
};

    We’ll have an error: Property 'age' is missing in type '{ name: string; }' but required in type '{ name: string; age: number; }'. All the properties are optional as expected, except for age which is a property of the property author. So, Partial is not going to work for objects with more than one level of depth.

    In our example, we don’t want to pass in an age property for the author, so we need to find a way to make it work.

    In fact, the recursive mapped conditional type that we’ve just defined above is a perfect use case for this. We can use recursion so that all the properties are optional, no matter their depth:

    <span class="hljs-keyword">type</span> DeepPartial<T> = {
  [K <span class="hljs-keyword">in</span> keyof T]?: T[K] <span class="hljs-keyword">extends</span> <span class="hljs-built_in">object</span> ? DeepPartial<T[K]> : T[K];
};

    Now, if we try our example with DeepPartial, there are no errors, and the problem is resolved:

    <span class="hljs-keyword">const</span> article: DeepPartial<IArticle> = {
  title: <span class="hljs-string">'Navigating the Mysteries'</span>,
  description:
    <span class="hljs-string">'As we walk our questions into a troubled future, storyteller and mythologist Martin Shaw invites us to subvert today’s voices of certainty and do the hard work of opening to mystery.'</span>,
  author: {
    name: <span class="hljs-string">'Martin Shaw'</span>
  }
};

    Use Case 2: UnwrapArray

    Another use case we can take a look at is when we need to have the “inner“ type of a multidimensional array.

    Consider this one:

    <span class="hljs-keyword">type</span> UnwrapArray<A> = A <span class="hljs-keyword">extends</span> <span class="hljs-built_in">Array</span><infer T> ? UnwrapArray<T> : A;

    We define an UnwrapArray generic type. If the type we pass to it is yet another array (A extends Array), then it’s passed to UnwrapArray again until we reach a type that doesn’t extend Array.

    Note that we use the infer keyword to extract the type. infer is only used with conditional types when extends is used, so it’s perfect for our purpose here.

    Now, we can get the inner type:

    <span class="hljs-keyword">type</span> Result = UnwrapArray<<span class="hljs-built_in">string</span>[][][]>; <span class="hljs-comment">// string</span>

    Using the keyword Array will have the same result:

    <span class="hljs-keyword">type</span> Result = UnwrapArray<<span class="hljs-built_in">Array</span><<span class="hljs-built_in">Array</span><<span class="hljs-built_in">Array</span><<span class="hljs-built_in">string</span>>>>>; <span class="hljs-comment">// string</span>

    Conclusion (and a Warning!)

    The universe of recursive types in TypeScript is fascinating and very powerful. But, of course, with great power comes great responsibility. TypeScript’s own documentation warns us:

    Keep in mind that while these recursive types are powerful, they should be used responsibly and sparingly. (Source)

    It’s not only that recursive types can result in longer time for type-checking, but with enough complexity, it can also result in a compile-time error. In fact, the documentation also tells us not to use them at all if possible.

    So, was all this learning for nothing?

    The answer depends on what you make of it. Recursion is a powerful concept that definitely has use cases in TypeScript as we’ve seen in this article, and if used responsibly, it can be an excellent tool.

    Source: freeCodeCamp Programming Tutorials: Python, JavaScript, Git & More 

    Related Posts

    Leave A Reply

    For security, use of Google's reCAPTCHA service is required which is subject to the Google Privacy Policy and Terms of Use.