16 ms·

Programming languages should have a tree traversal primitive

• MJGrzymek 1y ago
  sticking to dfs, there is still a difference between pre-order/in-order/post-order
• pbohun 1y ago
  I think this kind of control mechanism is not a great idea and could lead to easy bugs. I think it's a better idea to write a function that applies a function to the elements of a tree. Ideally you'd make a function for each traversal order. This makes it obvious what is happening. map_tree_pre(my_tree, my_func); map_tree_in(my_tree, my_func); map_tree_post(my_tree, my_func); map_tree_bfs(my_tree, my_func);
• mubou 1y ago
  I bet you could do something generic like this in languages that have deferred execution like C#'s IEnumerable. Something like foreach (Node node in EnumerateNodes(root, x => x != null, x => [x.Left, x.Right])) where EnumerateNodes uses `yield return` (i.e. is a generator) and calls itself recursively. Though it'd probably be easier / better performance to write an implementation specific to each node type.
• systems 1y ago
  well, functional languages with recursive types, are very good at representing binary trees https://cs3110.github.io/textbook/chapters/data/trees.html https://cs3110.github.io/textbook/chapters/data/trees.html
  • tbct 1y ago
    Once you have algebraic data-types in a language, writing a recursive visitor pattern is pretty simple. Encoding the semantics of a tree traversal operator likewise is difficult in the general case. What exactly would the order be, what if I want to traverse in a non-standard ordering, what about skipping branches; all would be difficult to cleanly represent. I have seen it done where you return actions with key ones being recurse, stop, replace, and replace & then carry out some function, but again, this is pretty simple to implement.
• soegaard 1y ago
  Pick a language that allows users to define their own control structures and test your idea in practise. Candidates: Racket, Scheme, Rust.
  • k__ 1y ago
    You don't even have to got that far. Defining your own iterator would be enough for most cases.
    • scotty79 1y ago
      The point is not to do that.
  • scotty79 1y ago
    I think Scala is also close. It has really flexible syntax.
• deleted 1y ago
  [deleted]
• yxhuvud 1y ago
  No, that seems like language bloat. Better to make your language have internal iterators, as then data structures can add their own logic that matches their need for iteration. Then special cases don't need additional syntax.
  • naasking 1y ago
    Trees aren't really a "special case". Sequences, trees and graphs are core abstractions to most programming, why try to flatten all trees and graphs to sequences?
    • smallnamespace 1y ago
      Because your code is actual running serially so no matter what there is an iteration order, and the order matters for performance even if your code does not care. For example if you literally don’t care about the order then your code can map over a default iterator that is efficient (DFS).
      • naasking 1y ago
        Not true due to parallelism. Also, SQL demonstrates that you can describe the desired result declaratively without being concerned about iteration order. I see SQL's CTEs as a good example of the kind of primitive the article is talking about.
        • alterom 1y ago
          Sure, and perhaps that's the reason why we don't have a built-in for_tree: for some people, order matters; for others, it doesn't. Then, for some cases, depth-first traversal is needed; for others, breadth-first. Then, there's parallelism, and even the plain old for loops aren't parallel by default. By the time you specify exactly what you need from a tree traversal, you've written code to do it. And if you're fine with some default choice — you already can use the default iterator with the for_each loop. I don't see what need there is for adding an extra for_tree syntax to do that.
• aeonik 1y ago
  I agree with the author, we need better primitives, if you need functionality now: Major tools that exist today for partial structure traversal and focused manipulation: - Optics (Lenses, Prisms, Traversals) Elegant, composable ways to zoom into, modify, and rebuild structures. Examples: Haskell's `lens`, Scala's Monocle, Clojure's Specter. Think of these as programmable accessors and updaters. - Zippers Data structures with a "focused cursor" that allow local edits without manually traversing the whole structure. Examples: Huet’s original Zipper (1997), Haskell’s `Data.Tree.Zipper`, Clojure’s built-in zippers. - Query Languages (for semantic traversal and deep search) When paths aren't enough and you need semantic conditionals: - SPARQL (semantic web graph querying) - Datalog (logic programming and query over facts) - Cypher (graph traversal in Neo4j) - Prolog (pure logic exploration) These approaches let you declaratively state what you want instead of manually specifying traversal steps.
  • rebeccaskinner 1y ago
    Don’t forget recursion schemes. The last example in the article was just asking for a hylomorphism.
    • moomin 1y ago
      Honestly when I read the article I was, "Do you have a minute to talk about our Lord and Saviour, derive (Functor) and how her son hylo saved us all?"
  • jasperry 1y ago
    These are what I think the author is looking for. But it shouldn't be a "primitive" in terms of code automatically generated by the compiler, but an interface or typeclass like your examples (in a language advanced enough to have them.) The problem is that 'lens', 'monocle', etc. are famously abstract and difficult for people to apply to their actual problems. IMO, the solution would be for standard libraries to specify interfaces called 'BreadthFirstTraverse', 'DepthFirstTraverse', etc.
    • naasking 1y ago
• jerf 1y ago
  That's "just" a particular kind of fancy iterator that you should be able to implement in any language with iterator support. Here's one in Python: # Expects: # Tuple of iterateOn where iterateOn can be None def fancyIt(init, *options): if init != None: yield(init) for f in options: newVal = f(init) yield from fancyIt(newVal, *options) class Tree: def __init__(self, val, left = None, right = None): self.val = val self.left = left self.right = right def left(self): return self.left def right(self): return self.right myTree = Tree( 1, Tree(2, Tree(3), Tree(4, None, Tree(5))), Tree(6, None, Tree(7))) for node in fancyIt(myTree, Tree.left, Tree.right): print(node.val) which prints the numbers 1 through 7 in order. Breadth-first is slightly trickier, but only slightly trickier one time.
  • packetlost 1y ago
    Yeah, tree traversal is really easy and implementing it as an iterator is natural. Maybe don't use a recursive technique if you plan on working with non-toy datasets, Python's default stack limit is pretty small (1000), but this is otherwise a very flexible API. While easy, I think bisect would be a good addition to every stdlib too.
    • jerf 1y ago
      I did the tree just to match the author's example. I would agree that a bespoke iterator for breadth- and depth-first iteration for any given tree is probably a better way to go. As long as we're in a language like Python, build in something that allows you to examine a branch and decline to descend into it while you're at it. I don't think this is a large problem in practice because you shouldn't be using dozens of tree types in a given code base, so adding iterators to a tree is no big deal. In general there aren't enough types of iteration available to a given data structure that you need to describe how to iterate on it from the "outside". (Generally when you are doing that, it's too non-trivial to fit into this pattern anyhow; see the Visitor pattern in general.) This strikes me as maybe the sort of default tool you might slap in a library somewhere, but it should be a niche tool. If you're using it all the time you're probably doing something wrong. By default your data structures should be providing iteration packaged with them and it should generally be what you need. And your language should support aborting iteration, in whatever that looks like normally. I'm not sure I know a language that doesn't, it's a fairly basic element of iterator support when you get into implementation. There are also many cases where a tree iterator will perform significantly better, including CPython. I don't have enough experience with PyPy to know if it could inline the Tree.left and Tree.right calls down to zero penalty at JIT time. Rust and C++ and the other static languages with sophisticated compilers might be able to get that down to fully inlined and zero-cost, but even if they can it's probably better not to push that on to the optimizer as the optimizers will eventually give up if this is composed with enough other stuff. Better to just have an efficient implementation in the first place.
• MontagFTB 1y ago
  Sean Parent developed ‘forest’ for C++ that automatically maintains the invariant that its structure is always a hierarchy. It includes full-order iteration through its default iterator: https://stlab.cc/2020/12/01/forest-introduction.html https://stlab.cc/2020/12/01/forest-introduction.html
  • usrnm 1y ago
    Don't need to go that far, std::map is a tree (the standard does not dictate it, but it is in all ilmplementations), and you could always traverse it. The whole idea of iterators was popularized by C++ and its STL.
    • MontagFTB 1y ago
      std::map uses a tree as an implementation detail to achieve certain performance guarantees. It is not a tree from the user’s perspective, however. That is, there are no parent/child relationships between the elements in a std::map.
• pmontra 1y ago
  I remember that I was using trees quite often last century, when I was writing programs in C. I seldom use tree or comparably complex data structures nowadays, when I almost only write web apps (mostly backend in Ruby or Python but some frontend in JS.) I'm bet that both Ruby and Python have plenty of trees written in C inside their interpreters. I do everything with arrays (lists) and hash tables (dicts) in Ruby and Python. Maybe a language construct for trees would be nice for lower level languages and almost out of scope for higher level ones. The same from another angle: there are a lot of trees in the indices of SQL databases (example [1]) but we don't zoom in to that level of detail very often when defining our tables. [1] https://www.postgresql.org/docs/current/btree.html https://www.postgresql.org/docs/current/btree.html
  • walleeee 1y ago
    Do you keep your dicts fastidiously flat?
    • pmontra 1y ago
      Usually yes. Web apps are simple. There isn't much to do inside a request params to db to response call. But sometimes, not every year, there is something to really reason about. I still remember some project from 10 or 20 years ago.
  • thesz 1y ago
    User interface widgets form a forest - windows contain layouts that contain widgets which also can be layouts, etc, etc. To implement Brown's algorithm to optimize class-based language models I had to implement a complex forest (DAG, actually) in Python using lists of fixed length. That was not especially nice to work with.
  • scotty79 1y ago
    Nested dicts are trees.
• pseudocomposer 1y ago
  Couldn't you just do this with a regular for loop and a few datatypes/functions? (This pseudocode is an Elm/Haskell/Rust/TypeScript-inspired abomination, but pretty portable to any language...) type Node = { value: Any, left: Node, right: Node } type Direction = Left | Right type TreePosition = { root: Node, currentNode: Node = root, position: Direction[] = [] } # Implementation left as an exercise but should be obvious and run in O(1), I believe. Returns Nothing when we're out of nodes. function nextPosition(position: TreePosition): Option<TreePosition> # The tree you want to iterate through const myTree: Node = ... # The loop for(let position: TreePosition? = TreePosition(root: myTree); position != Nothing; position = nextPosition(position) { node = position!.currentNode # Your loop code } I'd argue this doesn't belong as a language-level feature, but maybe an API/stdlib-level feature.
  • xxs 1y ago
    Indeed, I don't see any need to have a tree as a language primitive along with a traversal function (iterator). Tree traversal is not really different than iterating over a vector/list. E.g. even java has stuff like: TreeSet.forEach(consumerRef) or for(Type val : tree) doStuffWith(val)
    • HelloNurse 1y ago
      Trees are an insignificant middle ground between lists (which, by the way, are degenerate trees) and general iterators (on general object graphs, or not even materialized).
• meltyness 1y ago
  For perspective, I'm a novice with algorithm design, I've been grinding leetcode for the past 6 months or so, almost exclusively in Rust. I was bewildered by the same concern since I had initially set out to, not only focus on Rust, but to primarily maximize use of the Iterator construct, since I was not intricately familiar with it. A few months in I discovered that there was an appropriate Iterator construct which accomplishes the same thing. // Comments for the non-Rust native reader, regarding this Function declaration: // successors is a function that accepts an `Option` container for some Value of type T, called `first` // and a Closure called `succ`, constrained below: pub fn successors<T, F>(first: Option<T>, succ: F) -> Successors<T, F> ⓘ where // `succ` must receive the iterated state, and return the next iterated state F: FnMut(&T) -> Option<T>, // Each time the `next()` function is called on the returned Iterator (a Successors-flavored iterator), // the state of `first` is yielded, and then // `succ` is called to progress // until a `None` type is reported by `succ` I'm not sure where the concept came from, but it's not dissimilar to the author's implementation, but instead of the ControlFlow enum, it relies simply on the Option enum. I know though, that it was initially built in the Itertools crate as unfold and then upstreamed some time later. Essentially you use `first` to contain a Queue, Stack, or Level for the different traversals, and define traversal or activities from there. It's fairly ergonomic in practice, ergonomic enough for Leetcode. Here's a BFS: https://leetcode.com/problems/course-schedule-iv/solutions/6297286/functional-iterator-approach-with-successors-2ms/ https://leetcode.com/problems/course-schedule-iv/solutions/6... [0] https://doc.rust-lang.org/std/iter/fn.successors.html https://doc.rust-lang.org/std/iter/fn.successors.html [1] https://docs.rs/itertools/latest/itertools/fn.unfold.html https://docs.rs/itertools/latest/itertools/fn.unfold.html
• bee_rider 1y ago
  What is this note before the code about? > This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Also I’m slightly confused by this example. for_tree(string x = ""; x.size() <= 8; x : {x+"a", x+"b", x+"c"}){ print(x); } So, our “next node” operation is to concatenate to x. Won’t we either have to have a method for modifying x to go “up” a node, or we’ll have to keep a record of what x was upon entering each node? Like in this example we’ll end up with x=“aaaaaaaa” and then go up a node, over to a “b” node, and get x=“aaaaaaaab”, right?
  • dmurray 1y ago
    I think the intention is that you keep a record of what x is in the current node, and at every node above the current node. In the recursive implementation which the author describes as equivalent, these values are kept in the stack.
    • bee_rider 1y ago
      Seems a bit inefficient… I guess we can delete the a node’s copy of x after all of a node’s child nodes are visited, at least.
      • dmurray 1y ago
        Well, it doesn't need to be any worse than the stack-based implementation of a recursive tree traversal, and it can't be significantly better. You have to store that state somewhere. Perhaps it can be optimized to be a little better than the recursive version, depending on how much overhead your language uses for a stack frame that it won't need for this special case.
  • voidUpdate 1y ago
    The author said it could be implemented recursively, so a call with x="aaaaaaa" would call three more functions with x="aaaaaaaa", "aaaaaaab" and "aaaaaaac". you never need to go up a node
• lutusp 1y ago
  The article's thesis relies on the idea that a genuinely primitive traversal action exists, in the way that a for-loop is primitive and widely applicable, or adding two floats is common enough to justify building it into the language (or processor). But tree traversal doesn't have this universal property. There are too many methods and purposes for traversing a tree, sufficient that IMHO no single primitive embodiment could materially improve a language. Also, modern compilers efficiently break down high-level traversal code so well that expressing the idea at a high level incurs no serious penalty compared to having a primitive for that purpose, or a series of them.
  • fngjdflmdflg 1y ago
    I read a similar argument for graphs in general,[0] where this is more obviously true. [0] https://www.hillelwayne.com/post/graph-types/ https://www.hillelwayne.com/post/graph-types/ and https://news.ycombinator.com/item?id=39592444 https://news.ycombinator.com/item?id=39592444
• jpmonettas 1y ago
  Clojure has tree-seq https://clojuredocs.org/clojure.core/tree-seq https://clojuredocs.org/clojure.core/tree-seq
• crvdgc 1y ago
  https://hackage.haskell.org/package/base-4.21.0.0/docs/Data-Traversable.html https://hackage.haskell.org/package/base-4.21.0.0/docs/Data-...
  • kreetx 1y ago
    Though Haskell's Traversable is similar in name, then depending on what the developer intends, both Functor, Foldable or Monad could also help with the traversal. I.e, Haskell already has what the blog post asks for.
• Retr0id 1y ago
  > "Why not just use recursive functions" One great reason not to use recursive functions for traversing trees is that you can allocate your own stack data structure rather than relying on the call stack itself. In most languages/runtimes, the call stack has a maximum depth which limits the depth of trees you can process, usually on the order of thousands of stack frames. Managing your own stack usually produces weirder looking code (personally I find "naive" recursive approaches more readable) - but having it as a first-class language feature could solve that!
  • cobbal 1y ago
    If we're fixing the language, may as well fix the real problem and not artificially limit stack space.
    • Retr0id 1y ago
      The language doesn't get much of a say, stack limits are usually inherited from the OS itself. It's fixable by not using the OS-provided stack but that's a much more invasive change than a new syntax/stdlib feature.
      • worthless-trash 1y ago
        The compiler/language absolutely gets a say in this, you can do tail call recursion without stack saturation.
        • Retr0id 1y ago
          Tail call elimination is an optimisation that is only possible for certain code patterns. How would you write a tail-recursive tree walk, without using a separate stack or queue data structure to store state?
          • worthless-trash 1y ago
            Challenge accepted, I'll do it over my next long weekend.
• Xmd5a 1y ago
  Tree traversal primitives (clojure.walk): (defn walk [inner outer form] (cond (list? form) (outer (with-meta (apply list (map inner form)) (meta form))) (instance? clojure.lang.IMapEntry form) (outer (clojure.lang.MapEntry/create (inner (key form)) (inner (val form)))) (seq? form) (outer (with-meta (doall (map inner form)) (meta form))) (instance? clojure.lang.IRecord form) (outer (reduce (fn [r x] (conj r (inner x))) form form)) (coll? form) (outer (into (empty form) (map inner form))) :else (outer form))) (defn postwalk [f form] (walk (partial postwalk f) f form)) (defn prewalk [f form] (walk (partial prewalk f) identity (f form))) Another reason why this perlisism holds: 9. It is better to have 100 functions operate on one data structure than 10 functions on 10 data structures. "Let's move on."
  • MarkMarine 1y ago
    How about clojure zipper: https://clojuredocs.org/clojure.zip/zipper https://clojuredocs.org/clojure.zip/zipper
  • nimih 1y ago
    In addition, clojure.core has the handy tree-seq function: (defn tree-seq "Returns a lazy sequence of the nodes in a tree, via a depth-first walk. branch? must be a fn of one arg that returns true if passed a node that can have children (but may not). children must be a fn of one arg that returns a sequence of the children. Will only be called on nodes for which branch? returns true. Root is the root node of the tree." {:added "1.0" :static true} [branch? children root] (let [walk (fn walk [node] (lazy-seq (cons node (when (branch? node) (mapcat walk (children node))))))] (walk root)))
    • Xmd5a 1y ago
      (defn tree-seq-breadth "Like tree-seq, but in breadth-first order" [branch? children root] (let [walk (fn walk [node] (when (branch? node) (let [cs (children node)] (lazy-cat cs (mapcat walk cs)))))] (cons root (walk root))))
• lucasoshiro 1y ago
  This is heavy biased to C++, which is a language that already has too many features that people just want to use. This is a very specific case to be placed as a language feature, and could be just a lib. If this becomes a C++ feature, imagine how many data structures we would need to support? Many other languages, specially the FP languages, allow to do that as a library. Even the languages that are only inspired by FP. Example, Ruby: class BinTree include Enumerable def initialize v, l, r @v, @l, @r = v, l, r end def each &block @l.each(&block) unless @l.nil? yield @v @r.each(&block) unless @r.nil? end end Using the Enumerable mixin includes many FP-based methods, such as map, filter and reduce by only defining each, which in this case is DFS. Then we can proceed to define a binary tree: tree = BinTree.new( 1, BinTree.new( 2, BinTree.new(4, nil, nil), BinTree.new(5, nil, nil) ), BinTree.new( 3, BinTree.new(6, nil, nil), BinTree.new(7, nil, nil), ) ) Iterate over all the elements: tree.each{|v| puts v} Iterate over the even elements: tree.filter{|v| v.even?}.each{|v| puts v} Stop iteration when finding a value: tree.each do |v| break if v == 1 puts v end And so on. The same can be done in Python, Kotlin and many others.
  • monkeyelite 1y ago
    > If this becomes a C++ feature, imagine how many data structures we would need to support? C++ already solved that problem. Iterator are designed so that an algorithm can be written once and used with multiple data structures.
    • lucasoshiro 1y ago
      So we can go back to just use them and just write a new library
      • monkeyelite 1y ago
        You don’t need the standard library to make iterators.
        • 1y ago
• meindnoch 1y ago
  Horrible idea. 1. BFS is not supported. 2. Traversal type (inorder, preorer, postorder, or even mixed order!) is also not handled. 3. The syntax doesn't make it apparent that stack overflow can occur, e.g. by doing DFS on a linked list.
• bjourne 1y ago
  I'm 100% sure smug Haskellers have something very important to say here. :)
  • Joel_Mckay 1y ago
    Normally someone would respond, but they are prone to lazy evaluation... Thank you... I'll see myself out... lol =3
  • chowells 1y ago
    You know, if Haskellers already have that functionality, maybe it's less that they're smug and more that they have already solved the problem. Do you call someone smug when you complain about being freezing and they invite you in out of the cold?
• monkeyelite 1y ago
  This is solved by iterators in C++. The idea of an iterators is to generalize the concept of a pointer —- something which refers to a location in your data structure. For example the most basic operations of a pointer are to advance and dereference. std::map is actually implemented as a tree. To iterator its members you can do for (cost auto &pair : map) The only requirement for your custom data structure to work is to implement begin() and end() which return iterators - “pointer like” objects.
  • rerdavies 1y ago
    I'm surprised nobody's brought up C++ generators yet (which avoid potential problems with recursion stack depth). for (const auto&node: await depth_first_tree(node)) And generators have the added advantage that walking trees is just a special case of the more general case of traversing a directed graph of elements, which is equally easy. Are generators not a thing in other languages?
    • trealira 1y ago
      I didn't even know C++ had generators, but you're right, generators make functions that walking trees much more obviously correct and convenient to write. The site cppreference has an example of walking trees in C++ using them. https://en.cppreference.com/w/cpp/coroutine/generator https://en.cppreference.com/w/cpp/coroutine/generator But I have a question: why is it that in your example, you write `await` before the generator function, but it's not in the example given on cppreference? Also, did you mean `co_await`?
      • rerdavies 1y ago
        To answer your question: I have used them, but I was too lazy to look up the correct syntax. Yes. It should be co_await. The library I used was layered on top of the C++20 co-routine implementation, not c++23, and used co_await there (but probably should not have). Do NOT use the c++20 co-routine APIs (a half-implemented nightmare of an API, although what is there does miraculously work, contrary to expectations). Probably better to wait for c++23 generators, which are so far available as an experimental feature on GCC 14.0 (which makes the feature unusable in any of my projects). All of which, I guess, answers my question about why nobody has brought up c++ generators yet. C# has nice generators. Sorry I brought it up. :-(
• john-h-k 1y ago
  Excellent time to mention rust's `ControlFlow` enum which allows doing this exact sort of thing https://doc.rust-lang.org/std/ops/enum.ControlFlow.html https://doc.rust-lang.org/std/ops/enum.ControlFlow.html Not as ergonomic as a direct tree-iterator, but I can't see of an elegant way to introduce that in an imperative language while keeping the forking/recursion aspect clear
• injidup 1y ago
  That's what c++20 coroutines paired with c++23 generators are for. It's easy to define whatever traversal you want and then expose it as generic code. https://godbolt.org/z/fnGzszf3j https://godbolt.org/z/fnGzszf3j
  • ellis0n 1y ago
    Great example!
  • uecker 1y ago
    Yeah, but is this really better than explicitly managing a stack? Here is how I one could write in C: https://godbolt.org/z/P3ErP4T4d https://godbolt.org/z/P3ErP4T4d or possibly with the setup code moved into the helper function for convenience: https://godbolt.org/z/soz7W5z1G https://godbolt.org/z/soz7W5z1G
    • injidup 1y ago
      Sure you can do it any way but the OP was about adding language features for iteration of a specific data structure. Iteration in C++ is state machine based and coroutines give you a neat way to implicitly model them without having to manage the boiler plate yourself.
      • uecker 1y ago
        Yeah, but what I do not get is why you need all this. What problem does this solve? The C function that advances to the next tree node does exactly the same. And what is neat about it? It just seems a lot more complicated. Or in other words: A new language feature should make things simpler and not more complicated to express. But maybe I am just missing a realistic examples where it actually makes things simpler?
• chess_buster 1y ago
  Nonsense. Programming languages should have less primitives like this and instead we should have better foundation libraries for the languages, i.e., containing iterator/-interfaces like Rust and Python (or Smalltalk).
• tbrownaw 1y ago
  Standard tree traversal loop (yes, missing some obvious conditionals I didn't feel like typing out): var todo = new List<T>(); todo.append(root); while (var item = todo.pop_front()) { todo.append(item.left); // or .prepend for depth-first todo.append(item.right); // or .prepend() // do stuff... }
• JonChesterfield 1y ago
  This implementation recurses on the call stack and calls that out as a feature. A built into the language tree walk which overflows the stack on large trees is perfect for C++, get a paper over to WG21. Or for a possibly more useful comment, constant space tree traversal is genuinely quite difficult to implement. I don't know a general solution to it (other than walk from the start N times, quadratic style), would be interested to hear of one.
  • kevinventullo 1y ago
    If nodes have pointers to their parent, constant space tree traversal is easy enough.
  • HelloNurse 1y ago
    Constant space tree traversal is impossible and unnecessary. On the other hand predictable space, including adding parent pointers to cheat, is easy to achieve by counting the total number of nodes or the depth of the tree.
    • somat 1y ago
      "Constant space tree traversal is impossible..." Naively I would expect something like left-hand-rule maze traversal to be constant space. The tree may need additional structures to support this sort of travel. Other thoughts: most state machines are constant space.... there may be something there.
      • HelloNurse 1y ago
        The "left-hand-rule maze traversal" requires backing out of dead ends (in a tree data structure, up from leaf nodes), which amounts to one permanent parent pointer per node instead of a transient stack of nodes that we have not finished visiting (in addition to the baseline of child pointers).
        • JonChesterfield 1y ago
• deleted 1y ago
  [deleted]
• HelloNurse 1y ago
  The simplifying assumption that all tree nodes have the same type and the same function should be called on them seems unrealistic. This kind of imperative iteration seems better served by the traditional visitor design pattern: more verbose (more explicit, not more complex) and more general.
• vinceguidry 1y ago
  When I went looking for this in Ruby, I eventually landed on RubyTree[1]. Being able to subclass the TreeNode makes everything so much friendlier. Sure, I could implement them myself, but getting converters to/from primitives for free is a lot off my mind. Would be nice to have it built into the language but honestly Ruby has a whole lot of stdlibs and default gems already. 1: https://github.com/evolve75/RubyTree https://github.com/evolve75/RubyTree
• ivanjermakov 1y ago
  I think functional languages handle this nicely with Foldable or Traversable typeclasses: https://hackage.haskell.org/package/base-4.21.0.0/docs/Data-Foldable.html https://hackage.haskell.org/package/base-4.21.0.0/docs/Data-...
  • dtech 1y ago
    Folding and traversing can be trivially done in all relevant programming languages if you have an iterator
    • trealira 1y ago
      I feel like programming an iterator like this akin to a state machine is just not that convenient or trivial, though. Below is pseudo-Java. class InOrderTreeIterator { Stack stack; TreeNode cursor; InOrderTreeIterator(TreeNode root) { cursor = root; s = new Stack; } bool hasNext() { return cursor != null || !stack.empty(); } TreeNode next() { if (cursor != null) { while (cursor.left != null) { stack.push(cursor); cursor = cursor.left; } } else if (!stack.empty()) { cursor = stack.pop(); } else { throw new NoSuchElementException(); } TreeNode ret = cursor; cursor = cursor.right return ret; } }
      • munificent 1y ago
        It's much easier if the language has built-in support for generators. Here's an in-order tree iterator in Dart: Iterable<TreeNode> inOrder(TreeNode node) sync* { if (node.left != null) yield* inOrder(node.left!); yield node; if (node.right != null) yield* inOrder(node.right!); }
        • trealira 1y ago
          Yeah, if it has built-in support for generators, it basically makes the state machine implicit for you, which is nice and convenient; it's like going from having to manage your own stack call stack to using a programming language that just allows function calls and recursion.
• specialist 1y ago
  FWIW, I use Null Objects to eliminate null checks. Makes recursion (tree climbing) more concise, legible. Bonus: Java's HotSpot magick will NOP (most?) methods of Null Objects, making this a zero cost abstraction. I should probably write a concrete example for a blog or something. TLDR: For every base class such as TreeNode, create a NullTreeNode that does nothing, then replace all uses of null with NullTreeNode. Voilá, no more null checks or NPEs.
• kelseyfrog 1y ago
  I've written about this before, but suggesting recursion for tree traversal is equivalent to suggesting goto is a replacement for if/for/while. We don't have syntax and semantics for recursion schemes in any programming language - it's always deferred to library support at best. As far as I'm concerned, this is an open problem in programing language design where we finally replace the vestigial recursion hack with a proper structured programming solution.
  • skribanto 1y ago
    Well, recursion is well-structured and can be reasoned about through induction. Goto is unstructured…
• Mikhail_K 1y ago
  Ordering pizza is much more important and frequent part of a developer's work than tree traversal. Therefore, programming languages need pizza ordering primitive even more, than tree traversal ones.
• jonstewart 1y ago
  I worked for Guidance Software in the aughts and their main product, EnCase, had its own proprietary scripting language built in, called EnScript. Everything in EnCase inherited from “NodeClass”, a linked list for creating trees. EnScript had a forall(NodeClass n in tree.GetRoot(){} construct that was very easy. It was essentially a depth-first iterator.
• f1shy 1y ago
  Well common lisp has it.
• hyperhello 1y ago
  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.
  • toxik 1y ago
    Now allow it to do BFS or DFS, suddenly you're not far from just a vanilla BFS or DFS if you have a sensible stack/queue API.
    • hyperhello 1y ago
      DFS is pure flow control, like iterating an array. BFS isn't really the same simple deal as DFS, it either requires approaching the next level and saving it for the next depth somewhere, or navigating the entire previous level again.
• cdrini 1y ago
  I'm not sure if it needs to be at the syntax level, but I think having built in standard library support for graphs (general trees) would help make graphs more common in programming. And seeing how powerful they are, I think that would be a good thing! I explored this idea with gstd, a standard library for graphs inspired by the JS Array interface: https://github.com/cdrini/gstd/ https://github.com/cdrini/gstd/
• qoez 1y ago
  How in the world is this getting a HN hug of death when it's a substack page?
• danieloj 1y ago
  As a fullstack web engineer I've never had to implement a tree structure at work. I'd love to hear examples of what kinds of companies/platforms people are writing these structures regularly. If anyone is willing to share where they use them I'd appreciate it
  • mvc 1y ago
    You might not implement them but as a web engineer you're using them all the time. So all these tools that you use will have tree implementations in them. - Every html document is a tree structure. And css documents have special syntax to address nodes within those trees - If it's any good, you're routing framework probably uses some kind of tree to quickly match the request to it's handler - The database you write to uses a tree to quickly find the location it needs to write to
    • chuckadams 1y ago
      I think that’s kind of the GP’s point, that there’s no “implementing a tree” so much as just using the tree that’s naturally there. When I make nested objects, I don’t think of trees or some boxes-and-arrows diagram, I just think “product type”. It’s good to know your graph algorithms, sure, but thinking about the data representation isn’t something one needs to have in the front of their mind in any decently abstracted language.
  • Philpax 1y ago
    The (V)DOM is a tree. Knowing that is useful for manipulating and composing it.
  • deleted 1y ago
    [deleted]
  • ozten 1y ago
    Folder UI components are a common case.
  • rcxdude 1y ago
    I've used them (though more generally a directed acyclic graph) when doing certain kinds of analysis of code execution paths (working in embedded software). They do tend to show up in UI work as well (in an ad-hoc, implicit fashion), in my experience, though generally when you're looking at something across the whole UI as opposed to implementing a specific element of it. I've also used them in a somewhat ad-hoc build-system like utility as well. (And to be clear, none of these involve sitting down and writing some generic Tree<T> structure, they're all cases of "Well, there's some tree-like datastructure that already exists or is a natural fit for this system and I'm going to be traversing it depth-first or breadth-first to do something to the elements of it or calculate something based on what nodes I pass through on a given traversal")
• demarq 1y ago
  I would think iterators are exactly this. And they exist in almost every language.
• pgt 1y ago
  Nathan Marz' talk on Specter (Clojure Library that decouples navigation from transformation) is must-watch if you deal with data: https://www.youtube.com/watch?v=VTCy_DkAJGk https://www.youtube.com/watch?v=VTCy_DkAJGk I use it in every project for data navigation and transformation, and it's more performant than standard Clojure data manipulation, while retaining types (instead of coercing back from seqs). E.g. if you have a map and you want to increment every value in the map: (require '[com.rpl.specter :as S]) ``` (->> {:a 5, :b 6, :c 7} (S/transform [S/MAP-VALS] inc)) => {:a 6, :b 7, :c 8} ``` ^ try to write that in normal clojure. Now let's say you have a map of vectors and want to increment all of those? (->> {:a 5, :b 6, :c 7} (S/transform [S/MAP-VALS S/ALL] inc)) ;; note the navigator juts got another level of nesting => {:a [2 3], :b [4 5], :c [6 7]}works for all clj data types, and of course it has navigators for recursive walking . It took me a while to get good at Specter, but it was worth it. I hear Rama uses Specter navigators internally.
  • erichocean 1y ago
    Meander is also useful if you need to map from one structure to another, and Malli if you need to write coercisions that check the validity of structures at runtime (aka "schema checking"). https://www.metosin.fi/blog/transforming-data-with-malli-and-meander https://www.metosin.fi/blog/transforming-data-with-malli-and...
• mrorigo 1y ago
  [dead]
  • suddenlybananas 1y ago
    Why clog up crates.io with AI slop?
• foota 1y ago
  One thing I wish for is for standard library trees to present a way to take advantage of a trees structure, even if they don't directly expose the tree itself. For instance, C++ map could expose a way to start find or e.g., lower_bound from some node. While I'm making a wishlist, I also wish lower_bound worked with reverse iterators (see e g., https://stackoverflow.com/questions/64351187/stdlower-bound-on-a-set-with-its-reverse-order https://stackoverflow.com/questions/64351187/stdlower-bound-...) :) I think allowing for starting this kind of search from a given node would cover most (though not all) of what you'd want to expose the trees structure for directly.
• deleted 1y ago
  [deleted]
• hinkley 1y ago
  I think Java did the right thing by making tree shaped collections, since they’re iterable and that covers the for loop situation, but it doesn’t expose the tree structure, so you can’t tell if two nodes are siblings or relatives or indeed if they are even in the same tree. But I think grafting those two together is the right answer, not inventing a new loop construct. Trees are easy to write iterators for. DAGs are a bit harder and full graphs are an advanced interview question.
• taeric 1y ago
  Tree traversal is an odd one to want to try and make primitive. There are a lot of hidden questions that you need to consider when traversing a tree. Would you want your syntax to indicate what order traversal? Should it indicate a way to control the extra memory that you allow for the common stack/queue used in basic traversal? If you have a threaded tree, should the syntax work without any extra memory usage?
• eru 1y ago
  Haskell (for example) doesn't even have a looping primitive. Why would it have a tree traversal primitive? Both looping and tree traversal can be done with library functions. In general, everything that can be done with library functions, should be done with library functions. > Doesn't for_tree(...) look a lot nicer and simpler and less error prone than needing to implement a recursive function for each operation you would want to do on a tree? Eh, in Haskell you can derive many of these things automatically. And even Rust has some automatic derivation.
• deleted 1y ago
  [deleted]
• adamc 1y ago
  Or maybe you need a different language, where implementing an efficient tree traversal operation is easier?
• gue5t 1y ago
  It seems like this is grasping for languages to expose recursors[1] or induction principles. These factor out the structure of an inductive type (e.g. trees) and leave the caller to simply plug in the behavior to perform for each possible situation that might arise during traversal. [1]: https://lean-lang.org/doc/reference/latest//The-Type-System/Inductive-Types/#recursors https://lean-lang.org/doc/reference/latest//The-Type-System/...
• jdeaton 1y ago
  Its called recursion > Doesn't for_tree(...) look a lot nicer and simpler and less error prone than needing to implement a recursive function for each operation you would want to do on a tree? No it does not
• kazinator 1y ago
  Here you go! A TXR Lisp macro for-tree for traversing a tree, given a variable, an expression for the root node, and expressions for how to to left and right relative to the variable. A node structure that for-tree knows nothing about. No iterator abstraction or API, nothing. (defstruct node () value left right) Example tree (a balanced binary tree whose numeric values happen to be sorted): (defvar example-tree #S(node value 5 left #S(node value 3 left #S(node value 1) right #S(node value 4)) right #S(node value 7 left #S(node value 6) right #S(node value 9))) Walk it: (for-tree nod example-tree nod.left nod.right (prinl nod.value)) 1 3 4 5 6 7 9 Code: (defmacro go-leftmost (var root left-expr stack) ^(for ((,var ,root)) (,var) ((set ,var ,left-expr)) (push ,var ,stack))) (defmacro for-tree (var root left-expr right-expr . body) (with-gensyms (stack node left right) ^(let (,stack) (go-leftmost ,var ,root ,left-expr ,stack) (for ((,var (pop ,stack))) (,var) ((iflet ((,right ,right-expr)) (go-leftmost ,var ,right ,left-expr ,stack)) (set ,var (pop ,stack))) ,*body)))) The left-expr and right-expr must be expressions that involve the var variable; the construct evaluates these to find the left or right child. When the value is nil it means there is no child. This is almost exactly what the blog is asking for, transliterated to Lisp syntax. Original concept in fantasy C syntax: for_tree(Node* N = mytreeroot; N != NULL; N : {N->left, N->right} { print(N->value); } Lispified: (for-tree nod example-tree nod.left nod.right (prinl nod.value)) As required, the construct specifies the node variable to be the loop dummy, the root expression giving its initial value and the two accessor expressions for left and right traversal. The termination test N != NULL is made implicit in the Lisp version, so early termination requires a break out of the loop. It could be arranged. The fantasy C syntax specifies a variable name in the navigation declarator: N : { N->left, N->right }. Presumably, the variable here can be renamed to anything you want; it just arbitrarily happens to have the same name as the loop dummy. I didn't replicate this feature exactly because it just adds verbosity for nothing. It's okay if the navigation declarator just refers to the loop's one and only dummy variable. Anyway, programming languages should definitely not have a tree traversal primitive. Rather, languages should be Lisp.
• thatguysaguy 1y ago
  It's not at the language level, but for python JAX has the notion of a pytree (arbitrarily nested combination of lists, dicts, and tuples), and includes map and reduce operations for those objects. It's very convenient!
• SuperV1234 1y ago
  What you want is 'yield' and generator coroutines. We have them in C++20, but their codegen is very poor compared to a manual implementation.
• jheriko 1y ago
  [dead]
• andyferris 1y ago
  My thoughts on this are to add a third keyword alongside `break` and `continue` to loops that allow you to push another (loop) stack frame and descend into a tree-like data structure. For exposition, lets seperate loop initialization from the rest, make `continue` mandatory to repeat the loop with another specified value (i.e. the loop implicitly ends without a continue) and lets say `descend` to recurse into the tree. sum = 0; loop (node = tree.root) { sum += node.value; if (node.left) descend node.left; if (node.right) descend node.right; } Compare with a linear loop: sum = 0; loop (i = 0) { if (i >= array.length) break; sum += array[i]; continue i + 1; } The `descend` keyword differs from `continue` in that its more of a continuation - control flow will continue from that point once it is done. You could make this more functional and less imperative (and I'd be surprised if such things don't exist as libraries in some functional languages). Yes ultimately we can transform this to recursive functions and compile it that way... but for imperative languages (especially those without closures) something like the above might be useful. Arguably the above loops are _more_ imperative and less declaritive than the standard ones from the C family. You could add a functional twist by breaking with a value (which is the result of the overall `loop` expression).
• colbyn 1y ago
  It's called sum types and pattern matching, and this is like 80% of the reason why I like Swift and Rust.
• sttaft 1y ago
  For what it's worth, the ParaSail parallel programming language (https://github.com/parasail-lang/parasail https://github.com/parasail-lang/parasail) supports this: func Search(Root : Tree; Desired_Value : Tree_Value) -> optional Tree_Id is var Identifier : optional Tree_Id := null; for T => Root then Left(T) || Right(T) while T not null concurrent loop if Value(T) == Desired_Value then // Found desired node, // exit with its identifier exit loop with Identifier => Key(T); end if; end loop; return Identifier; end func Search; I actually don't use this feature much, because usually there is a key of some sort that determines which side of the tree is of interest.
• austin-cheney 1y ago
  Operating systems have this with file systems. Web browsers have this. It’s the DOM and it scares the shit out of most JavaScript developers. The fun part is confronting people about their irrational fears watching them spin their wheels with all the imagined excuses. I am a tremendous fan of tree systems. Tree systems should completely replace inheritance in programming to enforce the composition over inheritance principle.
• globular-toast 1y ago
  For isn't "linear traversal", it's linear execution. It's up to the data structure to define what linear traversal is. For arrays and lists that's trivial. For trees and, more generally, graphs there are many ways to do traversal. This is what iterators are for.
• swiftcoder 1y ago
  To some extent, this seems like it's just a symptom of "writing iterators in C++ is harder than it ought to be". You don't need to have a tree in memory to build an iterator over it - folks write iterators over implicit data all the time. Here's the range based for loop counterexample from the blog post, as a python generator: import itertools def iterate_tree(): for length in range(1, 8): for combo in itertools.product("abc", repeat=length): yield ''.join(combo) for s in iterate_tree(): print(s)
  • uzerfcwn 1y ago
    C++ also has generators[1], but the author is perhaps unaware of them. [1] https://en.cppreference.com/w/cpp/coroutine/generator https://en.cppreference.com/w/cpp/coroutine/generator
  • hiccuphippo 1y ago
    "yield from" is also very useful to iterate trees in python.
• fedeb95 1y ago
  programming languages shouldn't have such primitives, because they're not primitive. Otherwise, people programming different stuff all the time, would need other primitives, and you'd have unmaintainable languages full of bugs.
• mpweiher 1y ago
  Adaptive Programming[1] by Karl Lieberherr is the most comprehensive attempt I have seen to formalize and separate iteration over arbitrary structures as a distinct PL construct. It allows you to specify traversal in a structure-shy way. Personally, I think it goes a little too far, but it's definitely a good inspiration. [1] https://www2.ccs.neu.edu/research/demeter/ https://www2.ccs.neu.edu/research/demeter/ Presentation: https://www2.ccs.neu.edu/research/demeter/talks/overview/quad2000.pdf https://www2.ccs.neu.edu/research/demeter/talks/overview/qua...
• JaumeGreen 1y ago
  One of the projects that I have only in my mind space is an Iversonian language with more data structures and the tools to easily navigate an traverse them. Trees, graphs, ... the sky is the limit. And with the power of notation as a tool of thought, and a pen interface, it would be fun to do whiteboard sessions that produced real code that could be executed as is. OTOH I read/heard that the beauty of array languages is that they have few data types, but they can be easily worked on. So maybe the answer is not easier tree traversal primitives, but better literature/training on how to transform it in a more manageable data type. Sometimes the answer is to adapt our vision to our world, sometimes the answer is to adapt the world to our vision.
• scotty79 1y ago
  Branching iteration seems like a great idea. But I think the syntax shouldn't come from tree traversal. It should be something general. You tell the normal for loop how to go to the next sibling (`increment`) and when to end naturally (`condition`) or prematurely (`break`) and how to skip current sibling (in whole or partially) (`continue`). Branching iteration would also need to know how and when to branch, that includes skipping branching for this particular item, end whole iteration naturally and prematurely. So something similar to `break` and `continue` should be the method of branching (descending into the tree). I think Scala might be a great language to prototype implementation of such construct.
• drbojingle 1y ago
  What programming languages need is dimensional analysis. The fact that I can make variables like Const km = 1 Const velocity = 11 And do km + velocity = 12 is all kinds of silly.
  • erichocean 1y ago
    What programming languages need is linguistic analysis. The fact that I can make variables like Const true = False Const false = True And do if (true) "won't happen" else if (false) "will happen" is all kinds of silly.
  • zupa-hu 1y ago
    That exists, it is called a nominal type system, while in your example the language has a structural type system. Edit: Assuming your example is even statically typed.
• Someone 1y ago
  I would start with a tree primitive. That’s difficult enough, with variations on branching factor, whether the tree is self-balancing, whether it is immutable, etc) I guess/expect that will have to expose the implementation detail of the branching factor (yes, a binary tree is a special-case of a https://en.wikipedia.org/wiki/B-tree https://en.wikipedia.org/wiki/B-tree for B = 2, but algorithms tend to be different) On top of that, build a library of tree traversal routines (breadth first, depth first with a few variants), allowing the user to specify code that decides, on each node visited, whether to navigate further down and whether to stop the traversal. Now, whether the language proper needs a generic way to specify tree traversals? I doubt it, and doubt even more that it is possible too that in a way so that a) most graph traversal algorithms can use the primitive and b) the result is easier to use/looks significantly nicer than just calling those routines.
• branko_d 1y ago
  In C#, you can implement an iterator method with the signature like this: public static IEnumerable<TNode> DepthFirstTraverse<TNode>( TNode root, Func<TNode, IEnumerable<TNode>> children ) You can then just ‘foreach’ over it. This doesn’t require the whole tree to be in-memory. Optimal implementation would recurse via programmer-controlled stack (instead of language-controlled) to avoid nested iterators. Here is a TypeScript version: function* traverseDepthFirst<T>( root: T, children: (parent: T) => Iterable<T> ) A similar approach should be possible in any language which supports iterators/generators.
• Nerdx86 1y ago
  My concern here is what a recursive primitive like this in a low level language (like C/C++/Zig/Rust) would imply to the execution context of the "code within the brackets". If it was within the context of a lambda, etc that's one thing. I will be transparent here, I do not know of a non recursive, tree traversal alogorthim that uses constant storage but doesn't modify the tree.. (Morris Traversal satisfies 2 but makes temporary changes to the tree) Most primatives do not allocate hidden data (even C++ iterators require you to instantiate the iteration state as a variable) and operate within a known stack/execution context. Having an actual primitive that implements arbitrary tree traversal would require a substantial complier generated, but non-transparent, framework for that execution. It would either need to be recursive, have localized dynamic data, or would require tree structures that are well defined to use something like Morris. (And Morris is natively non-concurrent even for reads) While this means that that simple primitive would actually do a lot of potentially problematic things under the hood. How many Junior programmers would call it concurrently for reads because it's not "modifying the data". Why do you need to lock? Things like brake and continue and other control mechanisms wouldn't actually work as assumed from the flat context.... I.E what happens if somebody called a goto inside of that block? Also, in an embedded context where you may not have a dynamic allocator, how would a version written as in reiterative function with a expanding stack data structure function? From a language standard point of view, there are so many complexities to building something like this that runs in any context that the language is supported. Something like this that runs in any context that the language is supported. I mean look at C++, they have specifically and (deliberately / arguably rightfully) failed to build copy on write strings (a simpler abstraction) because there are cases where they couldn't guarantee that they would have the expected results in all contexts. This to me sounds more like something that should be a lambda function and a standard library, not a primitive... Languages that support dictionaries and maps as part of their standard data structures already have library support for tree traversal internally. They have solved many of the problems of making that language exposed, so that would be a much smaller ask. And programmers rightfully assume a lot more complexity within library calls then they do within primitives. Primitives are designed to be primitive. Having primitives able to create stack frames, dynamically allocate hidden memory, and/or recurse honestly worries me.
• rurban 1y ago
  Of course not. You already have iterators.