Type for a generic tree-visiting function

[odd tusk]

I'm struggling to define the type for a function that can visit a tree:

Give a structure like

[
  { name: "leaf" },
  { children: [
    { name: "sub-leaf" }
  ]}
]

A function that can visit it recursively can be defined like:

type VisitorResult = void | "break";

function visit<
  const ChildrenKey extends string,
  Items extends readonly (
    | Record<ChildrenKey, Items>
    | Record<ChildrenKey, never>
  )[],
>(
  items: Items,
  childrenKey: ChildrenKey,
  visitor: (
    item: Items[0],
    parents: readonly Record<ChildrenKey, Items>[],
  ) => VisitorResult,
): void {
  function visitItems(
    items: Items,
    parents: readonly Record<ChildrenKey, Items>[],
  ): VisitorResult {
    for (const item of items) {
      if (visitor(item, parents) === "break") {
        return "break";
      }
      if (
        childrenKey in item &&
        visitItems(item[childrenKey], [...parents, item]) === "break"
      ) {
        return "break";
      }
    }
    return;
  }
  visitItems(items, []);
}

The interesting part is that I want the key that contains the subtree be customizable by the caller.

Currently this function type doesn't really work, because:

1. each leaf node doesn't need to be a record, i would like to allow a leaf node to be of any type, string, number, etc
2. I can't make the following code satisfy the type constraint

interface Leaf {
  name: string;
}
interface Group {
  children: readonly Node[];
}

type Node = Leaf | Group;

const nodes: readonly Node[] = [{ name: "leaf" }, { children: [{ name: "sub-leaf" }] }];
visit(
  nodes,
  "children",
  (node, ) => console.log(node),
);

Any help is really appreciated.

[unkempt monolith]

why does childrenKey get passed in as a dynamic string? is it not always "children"?

[odd tusk]

the usage below the implementation is just an example, this visit function is supposed to be a very general one, one tree might use "children", another might use "items", etc.

[unkempt monolith]

hmm, alright. just curious: what's your use case for this?

[odd tusk]

it's pretty common for a code base to have trees with different kinds of "children keys", this key name depends on the semantic really

[unkempt monolith]

huh, not in my world. i don't think i've ever had this scenario, usually there's a single tree implementation in use in any given project i've worked on (though sometimes there are things from the outside world that need to be transformed into the project's tree representation)

anyway, i think part of the problem is that Record<ChildrenKey, never>

are you trying to have Leaf be assignable to that? because it isn't

it seems like you probably ought to be generic over the Leaf type too

anyway i'll fiddle with this and send back an iteration if i come up with anything promising

[odd tusk]

thank you very much. i think you're right, this problem can be greatly simplified if i use converters for example and always use "children".

still very curious about the solution though, seems like it's hitting the limit of typescript?

are you trying to have Node be assignable to that? because it isn't
yes, that was the error

[unkempt monolith]

there are multiple problems here, first one being what i mentioned above: your Leaf type isn't assignable to Record<"children", never>. this isn't a limitation of typescript, it's intentional. never doesn't mean "delete the property" or whatever you were thinking there

the second problem i see is more conceptual: you said you want to allow Leaf to be of any type. what if it happens to be an object type with a key named "children" (or whatever childrenKey is)? how will you distinguish a leaf from a group?

seems like you would need a way to express a negated constraint ("a leaf can be anything that doesn't have a ChildrenKey property"), but this is not something that typescript supports. see https://github.com/Microsoft/TypeScript/issues/4196

[odd tusk]

yes, i actually have no idea how to express that properly. i want to use a discriminated union so i can use in to do type narrowing.

[unkempt monolith]

that's the "proper" way to do it i think, but it requires relaxing the "Leaf can be any type" thing. you instead make a discriminated union and wrap all leaves in an "envelope"

hang on lemme whip up an example because that probably doesn't make sense

something like this:

type Tree<T> =
  | { kind: 'leaf', value: T }
  | { kind: 'group', children: readonly Tree<T>[] }

now there's no ambiguity; you can always just look at the kind property. but it means you can't directly use an arbitrary tree structure (but your original version couldn't either; i've used models of trees that didn't have a property like children at all; instead were like type Tree = Primitive | readonly Tree[] or similar)

[odd tusk]

makes sense, using Tree[] is probably too limiting, because sometime you need to attach some meta data

yeah, enforcing the structure first makes the problem much more approachable

So Record<ChildrenKey, never> is quite useless i guess?

[unkempt monolith]

it means something like "a value with a key named ChildrenKey whose value is something that can never exist", so yeah kinda useless

maybe there's a use for types like that in type testing libraries ¯_(ツ)_/¯

i had thrown this together before your first reply, maybe it'll be helpful:

[ripe geyser]

mkantor#0

Playground Link

Preview:```ts
type VisitorResult = void | "break"

function visit(
items: readonly TreeNode[],
visitor: (
item: TreeNode,
parents: readonly Group[]
) => VisitorResult
): void {
function visitItems(
items: readonly TreeNode[],
parents: readonly Group[]
): VisitorResult {
f
...```

You can choose specific lines to embed by selecting them before copying the link.

[unkempt monolith]

it's not generic at all, which makes it nice and simple. but if you still want to be able to use arbitrary leaves then it won't fly

[odd tusk]

yeah, that's much much simpler. i will convert the tree structure then. thanks for helping me think outside the box

[unkempt monolith]

i riffed some more and came up with this version that uses the discriminated union we discussed above:

[ripe geyser]

mkantor#0

Playground Link

Preview:```ts
type Leaf<T> = {kind: "leaf"; value: T}
type Group<T> = {
kind: "group"
children: readonly TreeNode<T>[]
}
type TreeNode<T> = Leaf<T> | Group<T>

type VisitorResult = void | "break"

function visit<T>(
items: readonly TreeNode<T>[],
visitor: (
item: TreeNode<T>,
parents: readonly G
...```

You can choose specific lines to embed by selecting them before copying the link.

[unkempt monolith]

one more small thing: i wouldn't use void in VisitorResult there. void has some surprising behavior which makes it "more than just a type" and that may come back to bite you (see #42709 for some examples). i'd probably use undefined or null or another string literal type there

[odd tusk]

huh, didn't know that, let me take a look. i use it because i remember if it's undefined, then a eslint rule will complain that you need to explicitly use return undefined to match that

[unkempt monolith]

could actually make this generic over the result type, which could be nice nevermind, this doesn't make sense now that i look again. you're visiting, not reducing

[unkempt monolith]

that lint rule seems bad. typescript doesn't require that, and javascript certainly doesn't

[odd tusk]

oh, right. it's Not all code paths return a value.ts(7030)

typescript requires that

well, requires an explicit return at the end

not return undefined

[unkempt monolith]

oh, with the union return type i guess it does

[odd tusk]

yeah, i didn't want to force an useless return at the end

[unkempt monolith]

this may just be a personal thing, but i usually avoid early returns so i wouldn't write it like this anyway. i like having the control flow in most of my functions be explicit

[odd tusk]

if you don't use early returns, you code tends to nest pretty deeply, or maybe you have another way of avoiding it?

[unkempt monolith]

not sure that i have a single strategy, but composing the main logic from many smaller functions helps, and i also try to use expressions rather than statements much of the time (e.g. ternaries rather than if/else, which i know is still nested but is not as syntactically-heavy; i find arrow functions can help for the same reason)

in this case maybe i'd use reduce? or maybe i would just resort to a for loop like you did here; after all this idea of "visit until some condition is met and then abort" is kinda fundamentally imperative rather than functional

but even keeping the for loop i think this isn't too bad:

for (const item of items) {
  if (visitor(item, parents) === "break") {
    return "break";
  } else if (
    "children" in item &&
    visitItems(item.children, [...parents, item]) === "break"
  ) {
    return "break";
  }
}
// If we haven't returned yet then tell callers to continue.
return undefined;

writing that comment made me think it should be type VisitorResult = "continue" | "break" to line up with the standard looping terminology

[odd tusk]

haha, yeah, that matches nicely, but not sure everyone in my team is going to like it

[unkempt monolith]

fair enough, gotta go with something everyone can get on board with

[odd tusk]

hey, thanks again for the help!