Recursively validating a list of elements with TypeScript

Photo by Linus Mimietz on Unsplash

Recursively validating a list of elements with TypeScript

Fernando De La Madrid's photo
Fernando De La Madrid
·

5 min read

Table of contents

The title for this post is very telling, so I'm going to keep the intro short for this one so we can jump right into today's challenge and learn about how can we validate a list of items recursively using TypeScript. Let's get to it!

Day eighteen - Dec 18

I strongly encourage you to try the first challenge on your own before reading the solution here.

Challenge: Santa's Remaining Deliveries

The challenge

Santa needs your help to count the number of presents he has to deliver! He's got all kinds of presents, from video game consoles (🎮), stuffed animals (🧸), toy cars (🏎️), books (📚), and more!

We need a general-purpose type that can take a tuple of items as its first argument and an item to search for as the second argument. It should return a count of the item specified.

For example:

Count<['👟', '👟', '💻', '🎸', '👟', '🧸'], '👟'>;

should return 3 because there are three 👟.

The code to complete

type Count = unknown;

The tests

import { Expect, Equal } from 'type-testing';

type ToySack = [
    '🎸', '🎧', '👟', '👟', '💻', '🪀', '🧩', '🎮',
    '🎨', '🕹️', '📱', '🧩', '🧸', '🎧', '👟', '🚲',
    '📚', '⌚', '🎨', '👟', '🎸', '🧸', '👟', '🎸',
    '📱', '🎧', '🎮', '🎒', '📱', '🧩', '🧩', '🚲',
    '🕹️', '🧵', '📱', '🕹️', '🕰️', '🧢', '🕹️', '👟',
    '🧸', '📚', '🧁', '🧩', '🎸', '🎮', '🧁', '📚',
    '💻', '⌚', '🛹', '🧁', '🧣', '🪁', '🎸', '🧸',
    '🧸', '🧸', '🧩', '🪁', '🏎️', '🏎️', '🧁', '📚',
    '🧸', '🕶️', '💻', '⌚', '⌚', '🕶️', '🎧', '🎧',
    '🎧', '💻', '👟', '🎸', '💻', '🪐', '📚', '🎨',
    '📱', '🎧', '📱', '🎸', '🏎️', '👟', '🚲', '📱',
    '🚲', '🎸'
];

type test_0_actual = Count<ToySack, '👟'>;
type test_0_expected = 8;
type test_0 = Expect<Equal<test_0_expected, test_0_actual>>;

type test_1_actual = Count<ToySack, '🧦'>;
type test_1_expected = 0;
type test_1 = Expect<Equal<test_1_expected, test_1_actual>>;

type test_2_actual = Count<ToySack, '🧩'>;
type test_2_expected = 6;
type test_2 = Expect<Equal<test_2_expected, test_2_actual>>;

The solution

type Count<T extends any[], Item, Acc extends number[] = []> = T extends []
  ? Acc['length']
  : T extends [infer Head, ...infer Tail]
    ? Count<Tail, Item, Head extends Item ? [...Acc, 1] : Acc>
    : never;

You might be familiar by now that it is quite common for problems that require counting occurrences or running a validation through multiple scenarios to go hand in hand with you guessed it, a solution that involves recursion.

This is not the exception that is why we are calling the Count type again within itself, but we'll get to that. Let's start by breaking down the solution from the params:

type Count<T extends any[], Item, Acc extends number[] = []>

The Count type takes three type parameters, T which is a list of any items to search through. The item to count occurrences of within the tuple. And the accumulator - Acc that keeps track of occurrences that were initially set to an empty array [].

Then we have the base case:

T extends [] ? Acc['length']

This is a conditional statement that is saying that if the array (list of items) T is empty [], return the length of the accumulator, which represents the count of occurrences of the item you want to search for.

Now we enter the recursive case:

: T extends [infer Head, ...infer Tail]
  ? Count<Tail, Item, Head extends Item ? [...Acc, 1] : Acc>
  : never;

There are a couple of different things going on in this conditional type, let's break them down.

The first thing is that we check if the array T has at least one element, if so we split it into its head (Head) and tail (Tail) (first and rest of elements).
We use the infer keyword to capture and assign the element(s) type, this is like saying: "Infer the type of the first element in the tuple and call it Head."

Next, we know that there is at least one element, so we recursively call Count on the remaining elements (Tail).
On the same call, for the accumulator parameter, we check if the Head is the same as the specified Item. If true, append 1 to the accumulator ([...Acc, 1]), otherwise, use the existing accumulator (Acc).

Otherwise if T is not empty and not of the expected form ([infer Head, ...infer Tail]), we just return never.

Solving it with an example

Now that we have learned how the solution for the type Count works, let's illustrate it step by step with an example:

type LetterCount = Count<['a', 'b', 'a', 'c', 'a'], 'a'>;

  1. Initial Call:

    • T: ['a', 'b', 'a', 'c', 'a']

    • Item: 'a'

    • Acc: [] (initially)

  2. First Recursive Call:

    • T: ['b', 'a', 'c', 'a']

    • Item: 'a'

    • Acc: [1] (since the first element is 'a')

  3. Second Recursive Call:

    • T: ['a', 'c', 'a']

    • Item: 'a'

    • Acc: [1]

  4. Third Recursive Call:

    • T: ['c', 'a']

    • Item: 'a'

    • Acc: [1, 1] (since the third element is also 'a')

  5. Fourth Recursive Call:

    • T: ['a']

    • Item: 'a'

    • Acc: [1, 1]

  6. Fifth Recursive Call:

    • T: []

    • Item: 'a'

    • Acc: [1, 1, 1] (since the fifth element is also 'a')

  7. Base Case:

    • T: [] (empty)

    • Return Acc['length'], which is 3.

So, the result of LetterCount would be 3, indicating that the item 'a' appears 3 times in the array.

Phew! This was a long one, thanks for sticking until the end, I hope you loved boosting your TypeScript skills by learning about how to recursively validate a list of items.

If you like this content consider checking out what I post on Twitter/X 🐦

TypeScriptRecursionTypesWeb DevelopmentFrontend Development