Handle heterogeneous arrays in flat and flatMap

[bterlson]

The typings for both flat and flatMap work ok for homogeneous arrays but do not handle tuple types well. Consider the current typings (with rename):

declare let arr: [[number, boolean], string];
let x0 = arr.flatten(0); // (string | [ number, boolean ])[]
let x1 = arr.flatten(1); // error
let x2 = arr.flatten(2); // error

Using conditional types and infer we can start to see a solution like:

type Flatten0<T> = T extends Array<infer U> ? Array<U> : never;

type Flatten1<T> = T extends Array<infer U>
    ? U extends Array<any> ? Flatten0<U> : never
    : never;
type Flatten2<T> = T extends Array<infer U>
    ? U extends Array<any> ? Flatten1<U> : never
    : never;
        
interface Array<T> {
    flat<T>(this: T, depth: 2): Flatten2<T>;
    flat<T>(this: T, depth: 1): Flatten1<T>;
    flat<T>(this: T, depth: 0): Flatten0<T>;
    flat<T>(this: T, depth: number): Array<T>
}

Which works great for array types and handles some tuple types better, but sacrifices a type error on the depth parameter when the array isn't nested that much, and more importantly, doesn't handle heterogeneous tuple cases, e.g. [ [string, number], boolean] should flatten to [string, number, boolean]. As far as I can tell, this is not possible without variadic kinds. Additionally, this implementation would benefit hugely from a way to reference a type recursively, e.g. https://github.com/Microsoft/TypeScript/issues/6230 (I'm not the only one to notice this issue trying to type this API).

[HerringtonDarkholme]

Would #24897 solve this? Currently it seems very hard to recurse on tuple types though...

[mhegazy]

@HerringtonDarkholme not sure how that would be used.. do you have a proposal in mind?

[HerringtonDarkholme]

The basic idea is to abuse tuple type to perform type level programming. But I'm quite sure it isn't desirable solution, indeed.

First we can transform number literal type to tuple type, which can be used to model the depth parameter. The length property in tuple is the key of transformation.

type Fn<R extends any[]> = (...args: R) => void
type Fn1<H, T extends any[]> = (h: H, ...args: T) => void
type Unshift<H, T extends any[]> = Fn1<H, T> extends Fn<infer R> ? R : []

type NumToTuple<N extends number, L extends any[] = []> = {
  0: L, 1: NumToTuple<N, Unshift<42, L>>
}[N extends L['length'] ? 0 : 1]

Then we can use a tuple to indicate flat depth.

// ToTuple is for type bound check
type ToTuple<T> = T extends any[] ? T : any[]
type Head<L extends any[]> = L extends [infer H, ...any[]] ? H : never
type Tail<L extends any[]> = ((...x: L) => void) extends ((h: any, ...rest: infer T)=>void) ? T : never

type FlatOne<T> = T extends Array<infer U>
  ? U extends any[] ? U : U[]
  : never
type FlatDepth<T, D extends any[]> = ToTuple<{
  0:  T, 1: FlatDepth<FlatOne<T>, Tail<D>>
}[D extends [] ? 0 : 1]>

We also need make a type to concatenate two tuple types, crafted here. #24897 (comment)

And finally we can model flat tuple type:

type FlatTuple<T extends any[], D extends any[], Acc extends any[]= []> = {
  0: Acc,
  1: FlatTuple<Tail<T>, D, Concat<FlatDepth<Head<T>, D>, Acc>>
}[T extends [] ? 0 : 1]

type A = FlatTuple<[[number, string], boolean], NumToTuple<1>>

I didn't managed to pass generic instantiation check, expectedly.

(But I just can't help my self from doing this...

[RyanCavanaugh]

Rolling into #36554