Programming languages should have a tree traversal primitive

#1

Post by TylerGlaiel » Tue, Apr 29, 2025, 3:49 AM UTC

Programming languages should have a tree traversal primitive
blog.tylerglaiel.com

Re: Programming languages should have a tree traversal primitive

#2

Post by hyperhello » Tue, Apr 29, 2025, 5:31 PM UTC

This is interesting, but the syntax doesn't seem to have the right expressiveness for such a large change.

    for recursive (Node t = tree.root; t != NULL;) {
      puts(t.value);
      if (t.value == target) break;
      if (t.value == dontfollow) continue;
      if (t.left) continue t.left;
      if (t.right) continue t.right;
      }
    return t;

Regular 'break' is to really break out of the structure like a regular for, as regular 'continue' is to do the next iteration. But if continue has a value to recurse on, it reenters the for loop like a subroutine.

As a bonus, I think this is tail-call-optimization friendly.

Re: Programming languages should have a tree traversal primitive

#3

Post by quuxplusone » Tue, Apr 29, 2025, 7:54 PM UTC

hyperhello wrote: post #2

This is interesting, but the syntax doesn't seem to have the right expressiveness for such a large change. for recursive (Node t = tree.root; t != NULL;) { puts(t.value); if (t.value == target) break; if (t.value == dontfollow) continue; if (t.left) continue t.left; if (t.right) continue t.right; } return t; Regular 'break' is to really break out of the structure like a regular for, as regular 'continue' is to do the…

Your zero-argument "continue" is Tyler's "prune", I think. At first glance I agree that something like your one-argument "continue" would also be helpful — like, "recurse but only down these k of the n possible child branches." That seems hard to find syntax for, unless you build the list of children ad-hoc as you go and then do "N : children)" in your increment step.