typescript - 二叉树类型实例化的高度过高

Question

我正在研究类型系统，目前正尝试在类型级别进行反向级别顺序遍历。这些是我正在使用的类型:

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] 更容易理解)。此外，我使用元组长度来表示数字，因为它们更更容易使用并且不需要手动指定限制。

无论如何，我可以像这样在 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。

Playground

---

Completed implementation和 playground

Answer 1

我注意到有时 recursive conditional types是distributive与非分布式类型相比，达到实例化深度限制的可能性更大。

因此，我采取的一种方法是看看我是否可以通过关闭联合的分配性来继续(通过标准的单元组包装器技术 X extends Y ? A : B ➝ [X] 扩展 [Y] ? A : B):

type Height<Root extends Deno | undefined> =
    [Root] extends [Deno]
    ? Max<Increment<Height<Root[LEFT]>>, Increment<Height<Root[RIGHT]>>>  // okay
    : [];

至少对您的示例代码有效。

Playground link to code