迭代 TypeScript 类型级链表而不会出现过大的深度错误

Question

** 这是一个关于 TypeScript 的问题 ^4.1 **

我有一个递归链表类型。

interface ListNode {
  value: string;
  next: ListNode | undefined;
}

这是类型级实例的示例。

type RootNode = {
  value: "a";
  next: {
    value: "b";
    next: {
      value: "c";
      next: undefined;
    };
  };
};

我想将这个窄链表类型扁平化为以下类型。

type Flattened = [
  {value: "a"},
  {value: "b"},
  {value: "c"},
]

我将运行保存到 TS 错误 2589（深度过大/可能无限）。

这是我目前采用的两种方法。

递归元组传播。

type Flatten<T extends ListNode> = [
  Omit<T, "next">,
  ...(T["next"] extends ListNode
    ? Flatten<T["next"]>
    : [])
]

模拟具有映射类型的元组。

type Flatten<
  T extends ListNode,
  I extends undefined[] = []
> =
  T["next"] extends ListNode
    ? Record<I["length"], Omit<T, "next">> & Flatten<T["next"], [...I, undefined]>
    : Record<I["length"], Omit<T, "next">>;

我什至尝试对增量进行硬编码。

type Increment = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20];

type Flatten<
  T extends ListNode,
  I extends number = 0
> =
  T["next"] extends ListNode
    ? Record<I, Omit<T, "next">> & Flatten<T["next"], Increment[I]>
    : Record<I, Omit<T, "next">>;

我仍然收到错误 2589。

如果有人设计了解决方法，我将非常感激听到它是什么。

谢谢。

Answer 1

原来只有当输入 linked-list 类型从其他递归类型派生时才会出现此错误。上述展平方法按预期工作。

interface ListNode {
  value: string;
  next: ListNode | undefined;
}

type RootNode = {
  value: "a";
  next: {
    value: "b";
    next: {
      value: "c";
      next: undefined;
    };
  };
};

type Flatten<T extends ListNode> = [
  Omit<T, "next">,
  ...(T["next"] extends ListNode
    ? Flatten<T["next"]>
    : [])
]

type Result = Flatten<RootNode>; // [{value: "a"}, {value: "b"}, {value: "c"}]

迭代 TypeScript 类型级链表而不会出现过大的深度错误

Iterate Over TypeScript Type-level Linked List without Excessive Depth Error

tuples

variadic

type-level-computation

typescript

recursive-type