Issue
I'm playing around in the type system and I'm currently trying to make a reverse level-order traversal at the type level. These are the types I'm working with:
type LEFT = 0;
type VALUE = 1;
type RIGHT = 2;
type List = ReadonlyArray<unknown>;
type Increment<N extends List> = [...N, unknown];
type Decrement<N extends List> = N extends readonly [...infer H, any] ? H : never;
// `Node` already exists as a built-in... so I used Deno...
type Deno = [LEFT: Deno | undefined, VALUE: number, RIGHT: Deno | undefined];
I'm using a tuple instead of an object type to represent nodes since it'll be easier to create and change testing values. I also have some aliases to make it more "readable" when accessing the data (MyDeno[LEFT]
is easier to understand than MyDeno[0]
). Also, I'm using tuples to represent numbers, since they're much easier to work with and don't need a limit to be manually specified.
I can get the height of a tree in JavaScript like this:
function height(node) {
if (!node) return 0;
const lhs = height(node.left);
const rhs = height(node.right);
return Math.max(lhs, rhs) + 1;
}
But my attempt at transferring this to the type system generates an error:
type Max<A extends List, B extends List> = A extends [...B, ...any[]] ? A : B;
type Height<Root extends Deno | undefined> =
Root extends Deno
? Max<Increment<Height<Root[LEFT]>>, Increment<Height<Root[RIGHT]>>>
// ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ Type instantiation is excessively deep and possibly infinite.
: [];
even though it works with sample data:
type Data = [
[
[undefined, 4, undefined],
2,
[undefined, 5, undefined],
],
1,
[undefined, 3, undefined],
];
// Should be 3 since the height of `Data` is 3
type T = Height<Data>["length"];
// ^? 3
I wasn't expecting this to throw "Type instantiation is excessively deep"... Where in my type is the fault, and how could I refactor my Height
type so that it doesn't throw this error? Until I can correct this, I'll stick with using //@ts-ignore
.
Solution
I've noticed that sometimes when recursive conditional types are distributive there is a greater chance of hitting instantiation depth limits than there is when the type is non-distributive.
Thus, one approach I take is to see if I can proceed by turning off distributivity over unions (via the standard one-tuple-wrapper technique X extends Y ? A : B
➝ [X] extends [Y] ? A : B
):
type Height<Root extends Deno | undefined> =
[Root] extends [Deno]
? Max<Increment<Height<Root[LEFT]>>, Increment<Height<Root[RIGHT]>>> // okay
: [];
That works, at least for your example code.
Answered By - jcalz
0 comments:
Post a Comment
Note: Only a member of this blog may post a comment.