recursive/nested types for arrays

[ORESoftware]

So I had this:

type NestedRequestHandler = RequestHandler | Array<RequestHandler> | Array<Array<RequestHandler>>

for a certain situation it was actually insufficient and the compiler required me to do this:

type NestedRequestHandler = RequestHandler | Array<RequestHandler> | Array<Array<RequestHandler> | RequestHandler>

I can't figure out why the compiler forced me to do that, the above seems like a bug. Since the second operand in the union type seems like it would have covered it. Am I right or wrong?

Anyway, what I am ultimately looking for is a recursive type for arrays, like so:
https://stackoverflow.com/questions/53646270/declare-arbitrarily-nested-array-recursive-type-definition

[Nathan-Fenner]

Consider the following snippet:

type Nest = number | Array<Nest>;

type Okay = number | { nest: Okay };

Today, the type Nest results in an error:

Type alias 'Nest' circularly references itself.

The type Okay, however, doesn't produce any error.

The current rationale is explained in #12525:

The restriction that a type alias can't be referenced by itself at the top level has been the behavior since we implemented type aliases; however, you might recall that a while back, we started allowing type aliases to be referenced from within an object type.

(emphasis mine)

The current restrictions apply to all type aliases (e.g. type Foo<T> = {x: T} also can't break cycles any more than Array<...> can); you can only "break" cycles by putting things inside object types.

I think a reasonable minimal change to support the above use case would be to add two additional cycle-breakers: Array<T> and T[]. Essentially, since these two types are fixed (i.e. not user-supplied) no analysis needs to be done to ensure that they don't produce infinite types any more than {[x: number]: T} would.

The general case of cycle-breaking in type aliases can be addressed later.

[DanielRosenwasser]

Right - type aliases can't be directly recursive because in trying to resolve them, the type-checker would try to eat its own tail and spin off. See more on Wikipedia: https://en.wikipedia.org/w/index.php?title=Recursive_data_type&oldid=812740950#In_type_synonyms

====In type synonyms====
Recursion is not allowed in type synonyms in Miranda, OCaml (unless -rectypes flag is used or it's a record or variant), and Haskell; so for example the following Haskell types are illegal:

type Bad = (Int, Bad)

type Evil = Bool -> Evil

Instead, you must wrap it inside an algebraic data type (even if it only has one constructor):

data Good = Pair Int Good
data Fine = Fun (Bool->Fine)

This is because type synonyms, like typedefs in C, are replaced with their definition at compile time. (Type synonyms are not "real" types; they are just "aliases" for convenience of the programmer.) But if you try to do this with a recursive type, it will loop infinitely because no matter how many times you substitute it, it still refers to itself, e.g. "Bad" will grow indefinitely: (Int, (Int, (Int, ... .

Another way to see it is that a level of indirection (the algebraic data type) is required to allow the isorecursive type system to figure out when to ''roll'' and ''unroll''.

[Nathan-Fenner]

@DanielRosenwasser

We don't need the general case to be handled for this bug to be resolved. Is there any reason that Array<...> can't be given special treatment to resolve this issue (in this particular case)?

[styfle]

Here's a real use case: implementing Array.prototype.flat with any depth.

Right now, lib.esnext.array.d.ts only supports up to depth=7 😮

[ahejlsberg]

Fixed in #33050.