Typescript: how to achieve a recursion in this typ

Question

My original problem is this.

I made the following type but it does not work due to the circular references error and I don't know how to solve it:

type Increment<T extends number, Tuple extends any[] = [any]> = 
T extends 0 ? 1 :
T extends 1 ? 2 :
T extends TupleUnshift<any, Tuple> ? 
TupleUnshift<any, TupleUnshift<any, Tuple>>['length'] :
Increment<T, TupleUnshift<any, TupleUnshift<any, Tuple>>>

In the end it should work like:

type five = 5
type six = Increment<five> // 6

P.S. TupleUnshift is from here.

Answer 1

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>; // {}                                                                     

                                                        
            

查看更多

0人赞 添加讨论(0) 举报