Working on an Ohm/Nim implementation I came in to this particular puzzle: when you want to loop through a tree item but you need the loop body to be recursive. Obviously I'm implementing it similar to this:
proc interior(...) =
if condition: refactor
else: interior(child)
for elem in node.children: interior(...)
visit elem in blah.children:
if elem.bleh: # refactor path
else: interior(elem)
I already do use an iterator.
assert root.kind == nkParser
for grammar in root.children:
if grammar.kind != nkGrammar: continue
# stash the name of the current rule
for rule in grammar.children:
if rule.kind != nkRule: continue
# XXX would be nice to have a macro so we can drop an in-place recursion without breaking the text up to a separate proc that gets called once
# recurse through every rule element
for elem in rule.children:
# whenever we see an implicit case
if elem.kind == nkImpliedCase:
# create a new rule that is the current rule name, an underscore, and a snake case version of the implicit rule's name
# replace the implied case definition with an invocation of the new rule
# append the new rule to the rules table
i've had one external suggestion to resort to a stack. i suppose a custom tree iterator that manages the stack on its own is an option.
You probably already know this, but you can also not to use recursion to go up/down trees recursively. It can be done with fixed 2D tables of references or other methods.
It's ugly as hell, hard to write, and chock full of border-case conditions to watch for; but it also runs insanely fast when finished.
i was mostly asking about if the syntax of the macro was good or cringey. traversal itself i already wrote but thought it could be made more succinct.
no idea what to search for for these "fixed 2D tables" but it seems like externalizing the traversal mechanism and hiding it with an iterator instead of making the traditional visitor look cleaner was the consensus.
Some prior related discussion on recursive iterators is here.
He can correct me if I am mistaken, but I think @JohnAD was describing an over-complex scenario to illustrate his idea. A simpler scenario is a binary tree where instead of using recursion you use a "path" through the tree as the object with which you iterate (just a simple vector/seq). You can step this forward or backward or use it as a handle to insert or delete. Besides the efficiency (no parent pointers taking space, no recursion taking time), this design also "factors concerns" well. In particular, initially populating the path (find) can be done various ways - stepped forward/backward from before, done via a left-left-left...all the way down "min" operation, a similar max operation, seeking by key, or if the tree is instrumented with ranks seeking by rank (or interval) or even seeking over a duplicate chain. Then if mutating the tree (ins/del) is done via this tree path object you have everything you need.
It starts seeming more like a 2D table in a B-tree setting (like in my adix) where instead of path being seq[ptr Node] it is a seq[(ptr Node, int)] where the int is an in-node index.
These aspects are not covered in school or common open source solutions/people copying other people arenas. Were I to speculate, that would be since search trees are usually taught by "algo people" not "sw engineering people". Algo people like the "elegance" of recursive descriptions over "dirty" real world things like performance. Concern factoring covers both human populations, though. So, maybe there is some hope for the future.