TypeScript recursive union function type

Question

I'm trying to express the infinite family of types:

type Q0 = number;
type Q1 = (x: number) => number;
type Q2 = (x: (x: number) => number) => number;
type Q3 = (x: (x: (x: number) => number) => number) => number;
// ...

as a union type. If I define:

type Q = number | ((x: Q) => number);

and a little helper:

type IsSubtypeOf<S, T> = S extends T ? true : false;

I find that:

type _1 = IsSubtypeOf<number, Q>; // => true
type _2 = IsSubtypeOf<(x: number) => number, Q>; // => false

So (x: number) => number isn't an inhabitant of type Q, defying my expectations.

I expected that Q is equivalent to the union of all of its "ground instances". That is, that Q is the same as:

type Q1
  = number
  | ((x: number) => number)
  | ((x: (x: number) => number) => number)
  | ((x: (x: (x: number) => number) => number) => number)
  // ...

but in that case, (x: number) => number would be a subtype of Q1.

What am I missing here?

Appendix

I tried "unrolling" Q by adding another ground instance, and this does work (not suprisingly):

type Q2 = number | ((x: number) => number) | ((x: Q2) => number);

type _3 = IsSubtypeOf<(x: number) => number, Q2>; // => true

Answer 1

There is no way to write the infinite union type

type Q = number | 
    ((x: number) => number) | 
    ((x: (x: number) => number) => number) | 
    ((x: (x: (x: number) => number) => number) => number) | 
    ⋯;

in TypeScript. At best you can pick some reasonable maximum length of the union and write a recursive conditional type to achieve it:

type QLen<N extends number, A extends any[] = [number]> =
    N extends A["length"] ? A[number] : QLen<N, [(x: A[0]) => number, ...A]>;

type Q = QLen<10>;

---

In particular, the desired infinite union is not equivalent to

type NotQ = number | ((x: NotQ) => number);

One cannot "push" a union into the parameter type for a function and keep things the same. Functions are contravariant in their parameter types. (See Difference between Variance, Covariance, Contravariance, Bivariance and Invariance in TypeScript .) Unions turn into intersections and vice-versa. So NotQ would be expanded to

type NotQ = number | ((x: number | ((x: NotQ) => number)) => number);

which is equivalent to

type NotQ = number | (((x: number) => number) & ((x: NotQ) => number));

And this does not even begin to resemble your desired infinite union.

---

For a more concrete reason why you cannot assign an (x: number) => number to NotQ, you can see what happens if it were allowed:

const f = (x: number) => x.toFixed(2).length;
//    ^? const f: (x: number) => number

const q: NotQ = f; // error, but imagine it weren't

Here we have made the bad assignment. According to the definition of NotQ, if q isn't a number then it must be a ((x: NotQ) => number). And in that case you would be allowed to call q(q):

if (typeof q !== "number") {
    q(q) // no compiler error, but...  at runtime
} 

Of course if you actually run that, you'll get the runtime error that x.toFixed is not a function. Because q is actually f, which assumes that its input is a number, and therefore has a toFixed() method. But you've passed in q, not a number, and thus q(q) explodes. We've lied to the compiler about the type of thing q really is, and we've been penalized for it.

---

Playground link to code