Typescript: how to achieve a recursion in this type?

UPDATE FOR TS4.1+

Welcome back! TypeScript 4.1 introduced recursive conditional types, which, along with things like variadic tuple types has made it possible to perform a "add one to a non-negative whole number" via recursion. It actually behaves pretty well but I still do not recommend it for production environments for reasons I'll get into shortly.

First of all, I will ~~shamelessly copy~~ borrow a technique from this comment by @lazytype in microsoft/TypeScript#26223 which makes a tuple of any non-negative integer length without smashing into the recursion limit at about depth 23. It does this by breaking the integer into a sum of distinct powers of two (i.e., using its binary representation) and concatenating tuples of these lengths. Variadic tuple types make it easy enough to double the length of a tuple ([...T, ...T]) so this technique supports tuples of lengths well into the thousands and tens of thousands:

type BuildPowersOf2LengthArrays<N extends number, R extends never[][]> =
  R[0][N] extends never ? R : BuildPowersOf2LengthArrays<N, [[...R[0], ...R[0]], ...R]>;

type ConcatLargestUntilDone<N extends number, R extends never[][], B extends never[]> =
  B["length"] extends N ? B : [...R[0], ...B][N] extends never
  ? ConcatLargestUntilDone<N, R extends [R[0], ...infer U] ? U extends never[][] ? U : never : never, B>
  : ConcatLargestUntilDone<N, R extends [R[0], ...infer U] ? U extends never[][] ? U : never : never, [...R[0], ...B]>;

type Replace<R extends any[], T> = { [K in keyof R]: T }

type TupleOf<T, N extends number> = number extends N ? T[] : {
  [K in N]:
  BuildPowersOf2LengthArrays<K, [[never]]> extends infer U ? U extends never[][]
  ? Replace<ConcatLargestUntilDone<K, U, []>, T> : never : never;
}[N]

Then the Increment type you want is just this:

type Increment<N extends number> = [0, ...TupleOf<0, N>]['length'];

which creates a tuple of length N filled with zeros (doesn't matter what you use there), prepends a single 0 to it, and gets its length.

Let's see it in action:

type Seven = Increment<6>; // 7
type Sixteen = Increment<15>; // 16
type OneHundredOne = Increment<100>; // 101
type OneThousand = Increment<999>;  // 1000
type SixOrElevent = Increment<5 | 10>; // 6 | 11
type Numbah = Increment<number>; // number

Nice! That looks like what we want, I think. Now for the not-nice part and the reason I don't recommend it:

// Don't do this
type Kablooey = Increment<3.14> // Loading... 💥🔥💻🔥💥

That will cause the compiler to have a heart attack; the recursive tuple-builder never reaches its goal because no matter how big of a tuple it makes, there's never an element at index 3.14.

Can that be fixed? Sure. We can add an extra guard into the TupleOf type to bail out if there's a decimal point in the string representation of the number (shout-out to template literal types!):

type TupleOf<T, N extends number> = number extends N ? T[] :
  `${N}` extends `${infer X}.${infer Y}` ? T[] : {
    [K in N]:
    BuildPowersOf2LengthArrays<K, [[never]]> extends infer U ? U extends never[][]
    ? Replace<ConcatLargestUntilDone<K, U, []>, T> : never : never;
  }[N]

Now 3.14 results in number, which is not 4.14, but is at least reasonable and not compiler-explodey:

type AlsoNumber = Increment<3.14> // number

So there you go; it works and performs well.

I still can't bring myself to tell anyone "please use this in your production environment", though. It's just too potentially fragile. How sure are you, looking at the byzantine type munging above, that there isn't some simple edge case that will crash your compiler? Do you want to be responsible for patching such things just to get the compiler to add one to a number?

Instead I'd still recommend a simple lookup until and unless TypeScript implements arithmetic on numeric literals as requested in microsoft/TypeScript#15645 and/or microsoft/TypeScript#26382.

Playground link to code

PREVIOUS ANSWER FOR EARLIER TS VERSIONS:

I think in the other question and in comments I said that you can try to do this recursively but that the compiler, even if you can make it happy with the definition, will give up at some relatively shallow depth. Let's look at it here:

interface Reduction<Base, In> {
  0: Base
  1: In
}
type Reduce<T, R extends Reduction<any, any>, Base =[]> =
  R[[T] extends [Base] ? 0 : 1]

type Cons<H, T extends any[]> = ((h: H, ...t: T) => void) extends
  ((...c: infer C) => void) ? C : never;

interface TupleOfIncrementedLength<N extends number, Tuple extends any[]=[]>
  extends Reduction<Tuple, Reduce<Tuple['length'],
    TupleOfIncrementedLength<N, Cons<any, Tuple>>, N
  >> { }

type Increment<N extends number> = TupleOfIncrementedLength<N>[1] extends
  { length: infer M } ? M : never;

EDIT: You asked for an explanation, so here it is:

First, the definition of Cons<H, T> uses tuples in rest/spread positions and conditional types to take a head type H and a tuple tail type T and return a new tuple in which the head has been prepended to the tail. (The name "cons" comes from list manipulation in Lisp and later in Haskell.) So Cons<"a", ["b","c"]> evaluates to ["a","b","c"].

As background, TypeScript generally tries to stop you from doing circular types. You can sneak around the back door by using some conditional types to defer some execution, like this:

type RecursiveThing<T> = 
  { 0: BaseCase, 1: RecursiveThing<...T...> }[Test<...T...> extends BaseCaseTest ? 0 : 1]

This should either evaluate to BaseCase or RecursiveThing<...T...>, but the conditional type inside the index access gets deferred, and so the compiler doesn't realize that it will end up being a circular reference. Unfortunately this has the very bad side effect of causing the compiler to bottom out on infinite types and often getting bogged down when you start using these things in practice. For example, you can define TupleOfIncrementedLength<> like this:

type TupleOfIncrementedLength<N extends number, Tuple extends any[]=[]> = {
  0: Cons<any, Tuple>,
  1: TupleOfIncrementedLength<N, Cons<any, Tuple>>
}[Tuple['length'] extends N ? 0 : 1]

and it works, even for N up to 40 or 50 or so. But if you stick this in a library and start using it you might find that your compile time becomes very high and even causes compiler crashes. It's not consistent, so I can't easily generate an example here, but it's bitten me enough for me to avoid it. It's possible this problem will eventually be fixed. But for now, I'd follow the advice of @ahejlsberg (lead architect for TypeScript):

It's clever, but it definitely pushes things well beyond their intended use. While it may work for small examples, it will scale horribly. Resolving those deeply recursive types consumes a lot of time and resources and might in the future run afoul of the recursion governors we have in the checker.

Don't do it!

Enter @strax, who discovered that since interface declarations are not evaluated eagerly the way that type declarations are (since types are just aliases, the compiler tries to evaluate them away), if you can extend an interface in the right way, in conjunction with the conditional type trick above, the compiler should not get bogged down. My experiments confirm this, but I'm still not convinced... there could be a counterexample that only shows up when you try to compose these things.

Anyway, the above TupleOfIncrementedLength type with Reduction and Reduce works much the same way as the "naïve" version from before, except that it is an interface. I really can't pick it apart without writing ten pages and I don't feel like doing it, sorry. The actual output is a Reduction whose 1 property has the tuple we care about.

After that, Increment is defined in terms of TupleOfIncrementedLength by getting the 1 property and extracting its length (I don't use plain indexed access because the compiler can't deduce that TupleOfIncrementedLength<N>[1] is an array type. Luckily conditional type inference saves us).

~~I don't know that it's too useful for me to walk through exactly how this works.~~ Suffice it to say that it keeps increasing the length of a tuple until its length is one greater than the N parameter, and then returns the length of that tuple. And it does work, for small N:

type Seven = Increment<6>; // 7
type Sixteen = Increment<15>; // 16

But, on my compiler at least (version 3.3.0-dev.20190117), this happens:

type TwentyThree = Increment<22>; // 23
type TwentyWhaaaa = Increment<23>; // {} 😞
type Whaaaaaaaaaa = Increment<100>; // {} 🙁

Also, you get some weirdness with unions and number:

type WhatDoYouThink = Increment<5 | 10>; // 6 😕
type AndThis = Increment<number>; // 1 😕

You can probably fix both of these behaviors with conditional types, but this feels like you're bailing out a sinking ship.

If the above super-complicated and fragile method gives out entirely at 23, you might as well use a hardcoded list of outputs as I showed in the answer to the other question. For anyone playing along at home who wants to see answers in one place, it is:

type Increment<N extends number> = [
  1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,
  21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,
  38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54, // as far as you need
  ...number[] // bail out with number
][N]

That is comparatively simpler, and works for higher numbers:

type Seven = Increment<6>; // 7
type Sixteen = Increment<15>; // 16
type TwentyThree = Increment<22>; // 23
type TwentyFour = Increment<23>; // 24
type FiftyFour = Increment<53>; // 54

is generally more graceful when it fails, and fails at a known place:

type NotFiftyFiveButNumber = Increment<54>; // number
type NotOneHundredOneButNumber = Increment<100>; // number

and naturally does better things in the "weird" cases above

type WhatDoYouThink = Increment<5 | 10>; // 6 | 11 👍
type AndThis = Increment<number>; // number 👍

So, all in all, recursive types are more trouble than they're worth here, in my opinion.

Okay, hope that helps again. Good luck!

UPDATE FOR TS4.1+

PREVIOUS ANSWER FOR EARLIER TS VERSIONS:

Recommended topics

Hot tags