Search code examples
arraystypescriptrecursionindexingtyping

Simplify Typescript expression to recursive


How could one simplify this type into a recursive type:

[
keyof T,
keyof T[keyof T],
keyof T[keyof T][keyof T[keyof T]]
]

Solution

  • TypeScript doesn't really support recursive types where the recursion happens at the same object depth, such as in tuples. You'd need circular conditional types, which are currently forbidden (see microsoft/TypeScript#26980). You can trick the compiler into evaluating such types, but these tricks are really not supported (see here and here), so if you use these tricks and the compiler explodes, it's your job to pick up the pieces of broken compiler (that means, don't use it in production code).

    The closest I can imagine getting is something like this:


    First, I want to make some sense of the unspecified T in your type:

    type Manual<T> = [
        keyof T,
        keyof T[keyof T],
        keyof T[keyof T][keyof T[keyof T]]
    ]
    

    Now I will define type functions K and X. K<T> just maps keyof over the properties of T, and X<T> takes a tuple argument T, maps V[keyof V] over each of its properties, and prepends the first element to it:

    type K<T> = { [K in keyof T]: keyof T[K] };
    type X<T extends any[]> =
        ((h: T[0], ...t: { [K in keyof T]: T[K][keyof T[K]] }) => void) extends
        ((...r: infer R) => void) ? R : never;
    

    Then, your type Manual<T> can be expressed like this:

    type PartiallyAutomated<T> = K<X<X<[T]>>>;
    // type PartiallyAutomated<T> = 
    //  [keyof T, keyof T[keyof T], keyof T[keyof T][keyof T[keyof T]]]
    

    So far everything I've done is supported, so you can write K<X<X<[T]>>> or K<X<X<X<[T]>>>>, etc. If you want to tell the compiler "do K<X<X<...[T]...>>> to produce a tuple of length N", that involves cheating with circular conditional types, or unrolling the loop in some way.


    Here's the cheating method, which is NOT SUPPORTED:

    // not supported
    type Evil<N extends number, T, V extends any[] = [T]> =
        { 0: K<V>, 1: Evil<N, T, X<V>> }[N extends V['length'] ? 0 : 1]
    
    type FullyAutomated<T> = Evil<3, T>;
    // type FullyAutomated<T> =
    //  [keyof T, keyof T[keyof T], keyof T[keyof T][keyof T[keyof T]]]
    

    or you can unroll the (illegal) loop into a (legal but redundant) set of nearly-identical types like this:

    // supported but redundant
    type Redundant<N extends number, T, V extends any[] = [T]> = N extends V['length'] ? K<V> : R0<N, T, X<V>>;
    type R0<N extends number, T, V extends any[] = [T]> = N extends V['length'] ? K<V> : R1<N, T, X<V>>;
    type R1<N extends number, T, V extends any[] = [T]> = N extends V['length'] ? K<V> : R2<N, T, X<V>>;
    type R2<N extends number, T, V extends any[] = [T]> = N extends V['length'] ? K<V> : R3<N, T, X<V>>;
    type R3<N extends number, T, V extends any[] = [T]> = N extends V['length'] ? K<V> : R4<N, T, X<V>>;
    type R4<N extends number, T, V extends any[] = [T]> = N extends V['length'] ? K<V> : R5<N, T, X<V>>;
    type R5<N extends number, T, V extends any[] = [T]> = N extends V['length'] ? K<V> : R6<N, T, X<V>>;
    type R6<N extends number, T, V extends any[] = [T]> = N extends V['length'] ? K<V> : RX<N, T, X<V>>;
    type RX<N extends number, T, V extends any[] = [T]> = N extends V['length'] ? K<V> : never; // bail out at depth 7
    
    type AlsoAutomated<T> = Redundant<3, T>;
    // type AlsoAutomated<T> = 
    //  [keyof T, keyof T[keyof T], keyof T[keyof T][keyof T[keyof T]]]
    

    All of PartiallyAutomated, FullyAutomated, and AlsoAutomated evaluate to the same type function as Manual. Is it worth it? I kind of doubt it, since you said "simplify" and all of the solutions seem more complicated than your original definition. Maybe if you wanted a tuple of length 6 instead of 3 like

    [keyof T, keyof T[keyof T], keyof T[keyof T][keyof T[keyof T]], 
     keyof T[keyof T][keyof T[keyof T]][keyof T[keyof T][keyof T[keyof T]]], 
     keyof T[keyof T][keyof T[keyof T]][keyof T[keyof T][keyof T[keyof T]]][
     keyof T[keyof T][keyof T[keyof T]][keyof T[keyof T][keyof T[keyof T]]]], 
     keyof T[keyof T][keyof T[keyof T]][keyof T[keyof T][keyof T[keyof T]]][
     keyof T[keyof T][keyof T[keyof T]][keyof T[keyof T][keyof T[keyof T]]]][
     keyof T[keyof T][keyof T[keyof T]][keyof T[keyof T][keyof T[keyof T]]][
     keyof T[keyof T][keyof T[keyof T]][keyof T[keyof T][keyof T[keyof T]]]]]]
    

    you'd start seeing the benefit of having the compiler generate the type for you, but right now I'd suggest your original tuple is simple enough.


    Okay, hope that helps; good luck!

    Playground link to code