Search code examples
typescripttypescript-genericstype-level-computation

Recursive Types alias in typescript - typing flatten function

So I've been trying, for fun and for educative purpose, to write a type-level Flatten function. Here is what I've got so far :


type List<Head, Tail extends Array<Head>> =
  ((h: Head, ...args: Tail) => any) extends ((...args: infer Arr) => any) ? Arr : never

type Head<Arr extends Array<any>> =
  ((...args: Arr) => any) extends ((h: infer Head, ...t: Array<any>) => any) ? Head : never

type Tail<Arr extends Array<any>> =
  ((...args: Arr) => any) extends ((h: any, ...t: infer Tail) => any) ? Tail : never

type HasTail<Arr extends Array<any>> =
  ((...args: Arr) => any) extends ((h: any, ...t: infer Tail) => any)
    ? Tail extends []
      ? false
      : true
    : false

type Flatten<Arr extends Array<Array<any>>> =
Arr extends []
  ? []
  : HasTail<Arr> extends true
    ? List<Head<Head<Arr>>, Flatten<Tail<Arr>>>
    : Head<Arr>

It's not perfect as it does not check enough details on the input Arr but it's a good start I think. My problem is that I receive a Type alias 'Flatten' circularly references itself. error.

I thought it was fixed by this PR: https://github.com/microsoft/TypeScript/pull/33050 Maybe I do not understand the error in the right way? Can someone explain my mistake please?

Solution

  • So, If anyone ever find stuck like this, I would recommend reading the PR's discussions I mentioned in the question.

    The answer is that even if the recursion in types is allowed it's only in a subset of cases. Namely when using a "true" type in recursion. For example:

    interface Recurse<T> {}

type Do<I> = "string" | Recurse<Do<I>>

    That's just a simple example but it shows the idea. The call to Do<I> is ok if it's passed to Recurse only because Recuse is an interface. It would have work with Array, Tuple or structural types too.

    For example on how to do this right, look at this libary. https://github.com/pirix-gh/ts-toolbelt