==========================
== Zhuo Hong Wei's Blog ==
==========================
Any and everything

Solving Type Challenge

I’ve been trying to solve some type challenges to understand typescript better.

I had a lot of fun with a few easy and medium challenges which involve implementing types.

One of which I really enjoyed implementing is IndexOf<T, U>.

Basically it behaves like a regular indexOf function, except we are dealing with types, not literal values

type A = IndexOf<[1, 2, 3], 2>; // A is 1
type B = IndexOf<[2, 6, 3, 7, 9, 3, 8, 10], 3>; // B is 2
type C = IndexOf<[0, 0, 0], 2>; // C is -1

I started with this:

type IndexOf<T extends any[], U> = T extends [U, ...any]? 
                                     0: (
                                       T extends [...infer X, U, ...infer Y]? 
                                         X['length'] : (
                                           T extends [...infer H, U]? 
                                             H['length'] : -1
                                           )
                                        )

Basically I was thinking along these lines,

  1. Try to detect U at the start of the the array-like structure represented by T
  2. If match, we return 0 else we try to detect U within T instead of at the beginning
  3. Else try to detect U at the end of T

It didn’t work. It took me a long time to realize (2) was impossible because if there are multiple U in T, the type checker won’t be able to infer X or Y.

Next I thought of a recursive solution:

type IndexOf<T extends any[], U> = T extends [U, ...any]? 
                                    0: (
                                      T extends [...infer X, U]? 
                                        X['length'] : (
                                          T extends [any, ...infer M, any]? 
                                            1 + IndexOf<M, U> : -1
                                          )
                                       )

This didn’t even type check, because we are dealing with types and 1 + IndexOf<M, U> is not valid. How can we get position if there’s no way to increment?

What if we start matching recursively from the end of T?

Third attempt:

type ExactlySame<C, P> = C extends P? (P extends C? true : false) : false

type IndexOf<T extends any[], U> =T extends [...any, infer G]? (
                                      ExactlySame<G, U> extends true? 
                                      (T extends [...infer H, any]?
                                        (IndexOf<H, U> extends -1? H['length']: IndexOf<H, U>): never
                                      ):  
                                      (T extends [...infer H, any]? IndexOf<H, U> : -1)) : -1

This worked! Whenever we matched U at the end of T, the index of U is the length of the number of elements before U. However we cannot immediately return that length, because U may occur earlier in T. So we recurse with the part before U, H. If the chain of recursive calls leads to -1, we then accept the index of the later match.