Post #2191176
2026-05-05 18:24 UTC
I would rather have iterators/cursors for the tree walks, but those are much more work to implement. They also are not as fast. But they are far more flexible.
Given that the tree height is known, it is not THAT bad. One can allocate an array rather than use linked lists to store backtracking data.
Really the way I like to implement such a thing is either with call/cc or by continuation-passing style. The former is definitely not possible. Even using libguile, its call/cc is broken!
Replies (1)
-
@chemoelectric@masto.ai 2026-05-05 18:30
Say you want to go forwards in-order. Your iterator is something that can go in various ways. Here what it must first do is start at the root node and then follow every left node until it reaches the leaf. This is its actual start point. Along the way it must store backtracking data. The next node is the first backtrack. After that comes the right subtree of the first backtrack. Then one must do the second backtrack. And so on like that. Can this be done in continuation-passing style?