The goal of the challenge is to implement a generic type Includes<T extends unknown[], U> that returns true if U is included in T.

The challenge: https://github.com/type-challenges/type-challenges/blob/main/questions/00898-easy-includes/README.md

Watch the video

Example "easy" cases

The easier examples to solve this problem for are shown below:

For the given examples, our Includes type should return the type as shown in comment

 Includes<['Kars', 'Esidisi', 'Wamuu', 'Santana'], 'Kars'> // true
  Includes<['Kars', 'Esidisi', 'Wamuu', 'Santana'], 'Dio'> // false
  Includes<[1, 2, 3, 5, 6, 7], 7> // true
  Includes<[1, 2, 3, 5, 6, 7], 4> // false
  Includes<[1, 2, 3], 2> // true
  Includes<[1, 2, 3], 1> // true
  Includes<[false, 2, 3, 5, 6, 7], false> // true
  Includes<[null], undefined> // false
  Includes<[undefined], null> // false

These examples are all fairly simple, they include an array of types as T and one specific type as U. If U is inside T we return true, otherwise we return false.

More complex cases

 Includes<[{}], { a: 'A' }> // false
  Includes<[boolean, 2, 3, 5, 6, 7], false> // false
  Includes<[true, 2, 3, 5, 6, 7], boolean> // false
  Includes<[{ a: 'A' }], { readonly a: 'A' }> // false
  Includes<[{ readonly a: 'A' }], { a: 'A' }> // false
  Includes<[1], 1 | 2> // false
  Includes<[1 | 2], 1> // false

In these more complicated cases, the array T includes complex types such as objects and type classes. For example in the second complex case, false is assignable to boolean but not equal to it, so false is not inside T despite boolean being a member of T.

Approach

Lets forget the complex use example cases for now. If you've been following the challenges, you may have taken the excludes challenge already. This challenge seems very similar although this time we want to return true if U is in T, not the other way round.

We know that working with tuple types when doing type manipulation can be simplified by turning a tuple into a union type like so:

T[number]

And once we've turned our tuple type into a union type we can simply ask if U is assignable to it and write a simple type like so:

type Includes<T extends readonly unknown[], U> = U extends T[number] ? true : false

This converts our type T to a union of all the members of the tuple, then checks to see if U is assignable to to it. In this case, assignable to means "is equal to". If U is, return true, else return false.

This works for the simple cases, but not the more advanced cases. Lets dig into these to find out why

A harder example

For this example,

  Includes<[boolean, 2, 3, 5, 6, 7], false>

Our type is currently returning true, but it should be returning false. Clearly false isn't in our array, but the Includes type thinks it is. What's going on here?

The problem is with our equality check, we're asking our union type if false is assignable to it. Well it is! false is assignable to boolean, as is true. Clearly we need a better way of comparing types.

The Type Challenge Utilities

The type challenges come with a set of utility types that are used to make assertions in the playground. One of these types is called Equal. We won't go into how this type works in this post, but know that you can use it to compare the equality of two types:

  Equal<true, boolean> // returns false
  Equal<false, boolean> // also returns false

Now all we have to do is make use of this type in our Includes type

The solution

To solve this challenge we need to abandon our naive solution and rethink the approach completely. Instead of converting our array into a union type, we're instead going to loop over the elements, and compare the equality of each one to U using our Equal type.

Unfortunately there's no looping construct when doing type manipulation, instead we'll have to rely on recursion. Our approach will be:

1. Grab the first element from the array call it First
2. Grab everything else out of the array and call that Rest
3. Compare First to U using Equal
4. If they're equal, return true
5. If not, call our Includes type again with Rest and the existing U
6. If we reach the end of the array, return false as we haven't found our element

Using Infer to 'destructure' our array

In my opinion, the hardest part of the steps above is working out how we can grab the first element, and the rest of the elements out of the T array.

To do this, we can use the infer keyword. We can use this in a condition type like so:

   T extends [infer First, ...infer Rest] ? true : false

infer First is bound to the first element in the array, ...infer Rest is bound to everything else in the array, or the empty array if there are no other elements. This works very similarly to how it would in JavaScript.

TypeScript will only match infer First if there is at least one element in the array, i.e. there is a type for typescript to infer. This means that the condition will return false when we pass the empty array. If there is only one element in the array ...infer Rest will bind to [], much like the spread operator in JavaScript.

The final solution

Turning the steps into code leaves us with:

  type Includes<T extends readonly unknown[], U> = T extends [infer First, ...infer Rest]
    ? Equal<First, U> extends true
      ? true
      : Includes<Rest, U>
    : false

We need the additional conditional type to compare the equality of First and U to true.

The recursive nature of this means the T will become one element smaller each time we call it, eventually becoming [] (if we don't find U and First). If T does become [] this is our base case of our recursive type, and we return false as we fail the initial conditional check.