Correct type for nested array in a recursive function in typescript

Question

I am trying to implement a function flattenDeep which is quite similar to lodash's _.flattenDeep(array) in typescript, however i meet some problems with type definitions, here is my code:

export interface DeepArray<T> extends Array<T | DeepArray<T>> {}

export const flattenDeep = <T>(array: DeepArray<T>): T[] => {
  return [].concat(...array.map(arr => {
    if (Array.isArray(arr)) {
      return flattenDeep(arr)
    } else {
      return arr
    }
  }))
}

flattenDeep([1, [2, [3, [4]], 5]]) // should return [1, 2, 3, 4, 5]

So far it looks fine, when i test it, the functionality itself is alright, however the flattenDeep() function is inferring the wrong return type:

const arr = [1, [2, [3, [4]], 5]]
const flattenedArr = flattenDeep(arr)

// inferred type is:
// const flattenedArr: (number | (number | (number | number[])[])[])[]
// but it should expected to be number[] or Array<number>? since the final result is a one dimensional array

So how do i resolve this problem for providing correct types?

jcalz · Accepted Answer · 2020-03-10 10:20:06Z

The problem is that since DeepArray<T> is recursively typed and structurally identical to (T | DeepArray<T>)[], there isn't a unique T corresponding to DeepArray<T>. For example, the type DeepArray<number> is compatible with (number | DeepArray<number>)[] and therefore with (number | (number | DeepArray<number>)[])[], etc.

So when the compiler is trying to interpret a type like (number | number[])[] as DeepArray<T> for some T, it isn't guaranteed to infer number. It is perfectly free to pick number | number[], or number | (number | number[])[], or all sorts of things as long as whatever it chooses for T allows (number | number[])[] to be compatible with DeepArray<T>. So you can't count on inference to "flatten" T even though the implementation of flattenDeep() does flatten the value:

declare const flattenDeepOrig: <T>(array: DeepArray<T>) => T[]
const oops = flattenDeepOrig([1, [2, [3, [4]], 5]]) 
// const oops: (number | (number | (number | number[])[])[])[]

You could, of course, manually specify the desired value of T and the compiler would be able to check that it works, and generate an error if not:

const okayAnnotated = flattenDeepOrig<number>([1, [2, [3, [4]], 5]]) // number[]

But presumably you want the compiler to figure it out for you. To do so it's much better to have a type like <T>(array: T[])=>FlattenArray<T>[] for some appropriate FlattenArray<T> definition that explicitly collapses deeply nested array types to a flat type. That's because given a value [1, [2, [3, [4]], 5]] as T[], the only reasonable inference candidate for T is something like number | (number | (number | number[])[])[], at which point you want FlattenArray<T> to flatten it explicitly to number. So we just need to define FlattenArray<>.

Unfortunately, the straightforward definition of FlattenArray<T> would be circular in a way that the compiler does not support:

type FlattenArrayOops<T> = T extends Array<any> ? FlattenArrayOops<T[number]> : T; // error!
//   ~~~~~~~~~~~~~~~~  <-- Type alias 'FlattenArrayOops' circularly references itself.

There is an open suggestion, microsoft/TypeScript#26980, to allow such circular types, but for now there's no officially supported way to get this behavior.

In cases like this what I usually do is approximate a circular type by manually "unrolling" the definition into a version that works up to some fixed depth, like this:

type FlattenArray<T> = T extends Array<any> ? FA0<T[number]> : T;
type FA0<T> = T extends Array<any> ? FA1<T[number]> : T;
type FA1<T> = T extends Array<any> ? FA2<T[number]> : T;
type FA2<T> = T extends Array<any> ? FA3<T[number]> : T;
type FA3<T> = T extends Array<any> ? FA4<T[number]> : T;
type FA4<T> = T extends Array<any> ? FA5<T[number]> : T;
type FA5<T> = T extends Array<any> ? FA6<T[number]> : T;
type FA6<T> = T extends Array<any> ? FA7<T[number]> : T;
type FA7<T> = T extends Array<any> ? FA8<T[number]> : T;
type FA8<T> = T extends Array<any> ? FAX<T[number]> : T;
type FAX<T> = T; // bail out

Here you can see that FlattenArray<T> is not defined in terms of itself, but in terms of a similar type FA0<T>, which is defined in terms of a similar type FA1<T>, etc., until it reaches depth FAX<T> and just bails out. As long as your use cases tend not to be incredibly deeply nested, it should work for you:

declare const flattenDeep: <T>(array: T[]) => FlattenArray<T>[];
const okay = flattenDeep([1, [2, [3, [4]], 5]]) // number[]

Okay, hope that helps; good luck!

Playground link to code

Collectives™ on Stack Overflow

Correct type for nested array in a recursive function in typescript

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related