Navigating Arrays and Recursive Types in TypeScript

Photo by Elijah Boisvert on Unsplash

Navigating Arrays and Recursive Types in TypeScript

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

4 min read

Table of contents

December is flying by, and with every challenge, I'm gaining more confidence in my TypeScript skills. Today's task, I must admit, is the toughest one yet (at least for me). It brought back memories of the challenging toy problems I used to tackle back when I was learning JavaScript.

But don't be intimidated, you will have me as the guinea pig to try to solve this and guide you (if I can!). Let's roll up our sleeves and get into it.

Day twelve - Dec 12th

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

Challenge: Find Santa

The challenge

Strange as it may sound.. Santa went to college with someone that works at a big silicon valley networking company. They've been buddies for years. So much so that in 2023 Santa pushed the workshop's board until they approved budget to get WiFi on the entire campus. That way Santa can browse TikTok as he walks from building to building across the campus.

But after all that doomscrolling, Santa realized he has lost himself in a Christmas tree forest! A search team of elves has been deployed to find him, but he needs to give them more information about where he is among the trees.

FindSanta is a type that takes a tuple as its only argument and returns the index where Santa is located. Let's help Santa get back to the thing he's best at: inspiring leadership.

note: never is returned if Santa cannot be found among the trees

The code to complete

type FindSanta = unknown;

The tests

type Forest0 = ['🎅🏼', '🎄', '🎄', '🎄'];
type test_0_actual = FindSanta<Forest0>;
type test_0_expected = 0;
type test_0 = Expect<Equal<test_0_expected, test_0_actual>>;

type Forest2 = ['🎄', '🎄', '🎅🏼', '🎄'];
type test_2_actual = FindSanta<Forest2>;
type test_2_expected = 2;
type test_2 = Expect<Equal<test_2_expected, test_2_actual>>;

type Forest4 = ['🎄', '🎄', '🎄', '🎄'];
type test_4_actual = FindSanta<Forest4>;
type test_4_expected = never;
type test_4 = Expect<Equal<test_4_expected, test_4_actual>>;

The solution

type FindSanta<T extends readonly any[], I extends any[] = []> = 
  T['length'] extends 0 ? never : T[0] extends '🎅🏼' ? I['length']
    : FindSanta<T extends [any, ...infer R] ? R : [], [...I, any]>;

🤯😳What the...! I know I know, A LOT is going on. But bear with me, this will be a good learning opportunity, let's break down the solution:

Starting with the parameters:

  • T extends readonly any[]: This parameter represents the input array, nothing fancy going on.

  • I extends any[] = []: This is an additional parameter that we are defining to represent an array that accumulates the indices of the elements in our input array (T). If you don't pass the second param it defaults to an empty array [].

As you might have noticed already we are calling FindSanta inside of FindSanta... yup recursion strikes back!

That means that we will have a base case:

T['length'] extends 0 ? never

This is saying that if the length of the input array T is 0, return never.

Then we are checking for Santa 🎅🏼:

T[0] extends '🎅🏼' ? I['length']

If the first element of the input array is Santa🎅🏼, return the length of the accumulated indices I. This means Santa has been found, and the length of I represents the index.

Then things get a little bit more interesting in our recursive case:

FindSanta<T extends [any, ...infer R] ? R : [], [...I, any]>;

We are calling our FindSanta type with two array parameters:

  • T extends [any, ...infer R] ? R : []: This checks if there is at least one element (any) in the array (T). Then it takes out the first element (any) and only use the rest of the elements R. Otherwise, if the array is empty, just return an empty array []. (Phew, typing this made me sweat! 😰)

  • [...I, any]: This appends an element to the array I (it accumulates the indices). The any element doesn't matter, it's just a placeholder to keep track of the indices.

  • The recursion continues until either Santa🎅🏼 is found (base case) or the array has been fully traversed.

This was a lot to take, so take your time to let it sink. Here's hoping tomorrow's challenge gives us a breather, but you know what they say – no pain, no gain! 💪🏻
See you in the next TypeScript challenge!

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

TypeScriptRecursionTypesWeb DevelopmentFrontend Development