我正在尝试类型系统,目前正在尝试在类型级别进行反向级别顺序遍历。这些是我正在使用的类型:
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];
我使用元组而不是对象类型来表示节点,因为创建和更改测试值会更容易。我还有一些别名,以使其在访问数据时更加“可读”(MyDeno[LEFT]
比MyDeno[0]
)。另外,我使用元组长度来表示数字,因为它们是much更容易使用,并且不需要手动指定限制。
无论如何,我可以用 JavaScript 获取树的高度,如下所示:
function height(node) {
if (!node) return 0;
const lhs = height(node.left);
const rhs = height(node.right);
return Math.max(lhs, rhs) + 1;
}
但是我尝试将其传输到类型系统会产生错误:
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.
: [];
即使它适用于示例数据:
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
我没想到这会抛出“类型实例化过深”......我的类型中的错误在哪里,我该如何重构我的Height
输入这样就不会抛出此错误?在我能纠正这个问题之前,我会坚持使用//@ts-ignore
.
操场 https://tsplay.dev/mAreQW
已完成实施 https://github.com/kelsny/ja-reverse-level-order-traversal/blob/main/translated.ts and 操场 https://tsplay.dev/WzP32N