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

Question

** This is a question relating to TypeScript ^4.1 **

I have a recursive linked-list type.

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

Here's an example of a type-level instance.

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

I'd like to flatten this narrow linked list type into the following type.

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

I keep running into TS error 2589 (excessive depth / possibly infinite).

Here are the two approaches I've taken so far.

1. Recursive tuple spread.

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

2. Simulating a tuple with a mapped type.

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">>;

I even tried hardcoding the incrementation.

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">>;

Still, I get error 2589.

If anyone has devised a workaround, I'd be extremely grateful to hear what it is.

Thank you.

Answer 1

Turns out this error only occurs when the input linked-list type is derived from other recursive types. The above flatten methods work as expected.

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"}]