[HN Gopher] Programming languages should have a tree traversal p...
___________________________________________________________________
Programming languages should have a tree traversal primitive
Author : azhenley
Score : 157 points
Date : 2025-04-29 12:23 UTC (10 hours ago)
(HTM) web link (blog.tylerglaiel.com)
(TXT) w3m dump (blog.tylerglaiel.com)
| MJGrzymek wrote:
| sticking to dfs, there is still a difference between pre-
| order/in-order/post-order
| pbohun wrote:
| 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 wrote:
| 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 wrote:
| well, functional languages with recursive types, are very good at
| representing binary trees
|
| https://cs3110.github.io/textbook/chapters/data/trees.html
| tbct wrote:
| 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 wrote:
| Pick a language that allows users to define their own control
| structures and test your idea in practise.
|
| Candidates: Racket, Scheme, Rust.
| k__ wrote:
| You don't even have to got that far.
|
| Defining your own iterator would be enough for most cases.
| yxhuvud wrote:
| 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 wrote:
| 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 wrote:
| 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 wrote:
| 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 wrote:
| 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 wrote:
| 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 wrote:
| Don't forget recursion schemes. The last example in the article
| was just asking for a hylomorphism.
| jasperry wrote:
| 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 wrote:
| > 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
|
| I think people are often too enamored by general purpose
| languages that can express such abstractions natively. I
| don't see an issue with a language that provides this as a
| primitive without being able to express it itself,
| constraints can be useful for other properties. Once you can
| traverse trees, most programming problems can be tackled even
| in such constrained languages, eg. SQL with CTE.
| eru wrote:
| Haskell has 'Traversable' (and 'Foldable' etc) which are a
| lot more approachable than the fully generalised lens
| library.
| T-R wrote:
| I definitely agree for traversals, but Lenses need some sort
| of primitive support - even in Haskell they're mostly
| generated with TemplateHaskell, and the language developers
| have spent a long time trying to make the `record.field`
| accessor syntax overloadable enough to work with
| lenses[1][2]. Hopefully someday we'll be free from having to
| memorize all the lens operators.
|
| Optics are famously abstract in implementation, but I don't
| think people have trouble _applying_ them - people seem to
| like JQuery /CSS selectors, and insist on `object.field`
| syntax; it's kind of wild that no mainstream language has a
| first-class way to pass around the description of a location
| in an arbitrary data structure.
|
| [1] https://ghc-
| proposals.readthedocs.io/en/latest/proposals/002...
|
| [2] https://ghc-
| proposals.readthedocs.io/en/latest/proposals/015...
| aozgaa wrote:
| Like offsetof[1]?
|
| [1] https://en.cppreference.com/w/cpp/types/offsetof
| bts wrote:
| Agreed; also Traversable in Haskell is a simpler abstraction
| than lenses and pretty directly addresses what they seem to be
| looking for:
| https://hackage.haskell.org/package/base-4.21.0.0/docs/Data-...
| chowells wrote:
| Traversable and lenses are very closely linked. If you go to
| the original paper leading to Traversable [1] and read
| through it, it feels basically identical to reading through
| the parts of the lens library that lay down the core
| abstractions and the laws implementations must follow if you
| want to be able to blindly manipulate them. In fact, the
| traverse function is a Traversal, and so fits trivially into
| the lens ecosystem.
|
| [1] https://www.cs.ox.ac.uk/jeremy.gibbons/publications/itera
| tor...
| CyberDildonics wrote:
| This seems like dramatically over complicated iterators. Do
| they really need to be called 'optics' and 'lenses' and
| 'prisms' ?
|
| _Think of these as programmable accessors and updaters._
|
| How is iterating through something already not 'programmable' ?
| postepowanieadm wrote:
| SQL recursive CTE maybe?
| larodi wrote:
| how about we also get regex-parsable streams (IO::Async in perl
| has something like it, suboptimal perhaps) and regex-parsable
| treestructures (totally possible)? seems like just having the
| ~= work on structures (or whatever the API is called in other
| languages, this being Perl5)?
| akkartik wrote:
| I still love the Scrap Your Boilerplate papers.
|
| https://wiki.haskell.org/index.php?title=Research_papers/Gen...
| Avshalom wrote:
| To point out a prolog thing which is also applicable to other
| languages with good patter matching: the break/return/prune
| examples are all ergonomic to implement as recursion in a way
| that fails in C++ style type based dispatch.
| jerf wrote:
| 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 wrote:
| 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 wrote:
| 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.
| Retr0id wrote:
| I avoided the stack limit by using itertools.chain: https://g
| ithub.com/DavidBuchanan314/millipds/blob/15727d474c...
|
| (this is for iterating over nested JSON-like objects, which
| are just weird trees)
| packetlost wrote:
| CBOR objects, to be specific ;)
|
| There are a lot of ways you could avoid the recursion, but
| that's a particularly nice way!
| thrance wrote:
| Rust has a bisect [1], which is surprising since the std is
| kept relatively small.
|
| [1] https://doc.rust-
| lang.org/std/vec/struct.Vec.html#method.bin...
| imglorp wrote:
| Yes, it seems easy to implement.
|
| Yes, students should absolutely implement the classic
| algorithms to learn.
|
| Yes, there are some occasions when you need to home grow one at
| $work.
|
| BUT, in my opinion, most of the time, professional code should
| use a battle tested, vuln hardened library or builtin version.
| These things are VERY HARD to get exactly right. Jon Bently's
| Programming Pearls famously had a latent bug in its binary
| search for 20 years before someone caught it.
|
| https://research.google/blog/extra-extra-read-all-about-it-n...
|
| So yeah, it looks easy but don't do it. Stand on some giant's
| shoulders instead.
| Amadiro wrote:
| Sure but all pre-made, battle-tested tree datastructures
| you'd use in production in all languages already come with
| some form of iterator that you can just for-loop over, so the
| original articles point is still moot.
| thayne wrote:
| Sure, but it can be done by a library. There's no reason it
| needs to be built into the language.
| jerf wrote:
| Your reply is not relevant to my reply. The original poster
| is asking for this functionality and appears to believe it is
| something other than an iterator and requires some sort of
| special language support. However, it is completely
| implementable as an iterator, in a reasonably usable manner,
| with no additional language support. My specific code is
| written only to show that fact off.
|
| Anyone who copies and pastes it is welcome to both pieces
| when it breaks. Others have already alluded to possible
| improvements that could be made, and I already have my own
| analysis in a grandchild reply as to why I don't think this
| is a terribly pressing need or necessarily even a good idea.
|
| The reason I provide code is that it gets past the "oh, you
| _say_ it 's just an iterator, but I still don't believe you,
| since you haven't spelled it out to the n'th degree". When
| code is provided, belief ceases to be an issue. It is clearly
| something an iterator can implement, in existing languages,
| with existing iterator support.
|
| Unless you're going to claim it is somehow impossible to
| provide this functionality in a tested manner, you're
| completely changing the topic in an uninteresting direction,
| since it is always true that functionality generally needs
| testing and bits of code slammed into an HN conversation just
| to make a particular point probably shouldn't be copied
| wholesale into your production code.
| jerf wrote:
| Whoops, my edit window closed, but that first comment derives
| from a previous version that had a different signature for the
| functions in the "options" list. Ignore it.
| porphyra wrote:
| Well, the whole point of the blog post is to argue for a new
| kind of syntactic sugar and the author explicitly mentions
| iterators.
|
| > Well a range based for loop requires that your tree exist in
| memory AND that you have an iterator defined for your tree.
| With for_tree you could operate on an entirely imperative tree,
| without needing to define any iterators or generator functions.
| Here's an example where I'm checking every single string
| composed of "a", "b", and "c" of length 8 or less.
| for_tree(string x = ""; x.size() <= 8; x : {x+"a", x+"b",
| x+"c"}){ print(x); }
|
| You could definitely find every string composed of "a", "b",
| and "c" of length 8 or less by defining a custom iterator but
| it would be a verbose and unpleasant way of writing it:
| class StringIterator { public: using
| iterator_category = std::forward_iterator_tag;
| using value_type = std::string; using
| difference_type = std::ptrdiff_t; using pointer =
| const std::string*; using reference = const
| std::string&; StringIterator(bool begin =
| false) : is_end_(!begin) { if (begin) s_ = ""; }
| const std::string& operator*() const { if
| (is_end_) throw std::out_of_range("End iterator");
| return s_; } StringIterator&
| operator++() { if (is_end_) return *this;
| if (s_.size() < 8) return s_.push_back('a'), *this;
| while (!s_.empty() && s_.back() == 'c') s_.pop_back();
| if (s_.empty()) is_end_ = true; else s_.back()
| = s_.back() == 'a' ? 'b' : 'c'; return *this;
| } StringIterator operator++(int) { auto tmp =
| *this; ++(*this); return tmp; } bool
| operator==(const StringIterator& other) const {
| return is_end_ == other.is_end_ && (is_end_ || s_ == other.s_);
| } bool operator!=(const StringIterator& other)
| const { return !(*this == other); } private:
| std::string s_; bool is_end_; };
| int main() { StringIterator begin(true), end;
| int count = 0; for (auto it = begin; it != end;
| ++it) ++count; std::cout << (count == 9841 ? "Pass"
| : "Fail") << std::endl; return 0; }
| jerf wrote:
| def itWithStop(init, stop, *options): if init is
| not None and not stop(init): yield(init)
| for f in options: newVal = f(init)
| yield from itWithStop(newVal, stop, *options)
| for s in itWithStop("", lambda x:
| len(x) > 2, lambda x: x + "a",
| lambda x: x + "b", lambda x: x +
| "c"): print(s)
|
| yields the combinations of 0 - 2 length strings with a, b,
| and c.
|
| Python has a number of ways to achieve this depending on
| exactly how you want to pass the arguments; multiple
| functions, optional arguments, etc. How nice the final call
| looks is more about your local language's closures look.
|
| The main point here is that this will happily iterate on
| things that don't "exist". module Tmp where
| iter :: forall a. (a -> Bool) -> [a -> a] -> a -> [a]
| iter p opts x = if p x then x:concatMap (iter p opts) (opts
| <*> [x]) else [] ghci> :l tmp.hs [1
| of 1] Compiling Tmp ( tmp.hs, interpreted )
| Ok, one module loaded. ghci> iter (\x -> length x <
| 3) [(++ "a"), (++ "b"), (++ "c")] ""
| ["","a","aa","ab","ac","b","ba","bb","bc",
| "c","ca","cb","cc"]
|
| (Since things are lazy in Haskell, functions that return
| lists effectively are iterators. There's probably something
| in the standard library somewhere for (opts <*> [x]) to avoid
| the wrapping x in an unnecessary list, but my Haskell is
| rusty.)
| porphyra wrote:
| The iterator in my example will also happily iterate on
| things that don't exist. We all agree that it's possible to
| do in any language. But the main point is that the blog
| post is talking about syntactic sugar for an easier way to
| do it.
|
| And yes, Haskell is amazing at this sort of thing.
| jerf wrote:
| The syntactic sugar being asked for in this case is
| awfully thin. I definitely put this in the class of "stop
| pining for it and just use what's there".
|
| If the poster wants to particularize this to C++ because
| C++'s syntax can't support it in any reasonable manner,
| that's fine, but that's a C++ problem, not a "Programming
| languages..." problem. Which would be perfectly
| understandable and I'm not really complaining, more
| clarifying that most of the rest of the world can just
| rub together three or four existing constructs in a
| pretty reasonable manner to get this.
| samus wrote:
| Same thing, but the iterator is instead hidden inside the
| language implementation. `foreach` is already a quite general
| construct, and iterators are the way to extend them. However,
| I can see the benefit of designing a library to help
| implement more intricate iterators.
|
| Ceterum censeo this would be a family of simple macros in
| LISP.
| bawolff wrote:
| I kind of agree, but at the same time, for loops are just a
| fancy control structure that any student should be able to
| implement with goto.
| IshKebab wrote:
| I mean people do use iterator instead of for loops quite a
| lot.
|
| IMO the thing that would be really nice is if control flow
| like `for` was actually _the same_ as using an iterator. This
| would really help in Rust too where handling errors inside
| iterator callbacks is a right pain.
|
| I've seen a few languages try this but it seems to not be
| very popular. I think it can get a bit confusing how control
| flow keywords like `return` and `break` work if you turn `if`
| into syntactic sugar for a function call taking a closure
| etc.
| MontagFTB wrote:
| 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
| usrnm wrote:
| 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 wrote:
| 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 wrote:
| 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
| walleeee wrote:
| Do you keep your dicts fastidiously flat?
| pmontra wrote:
| 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 wrote:
| 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.
| pseudocomposer wrote:
| 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 wrote:
| 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)
| meltyness wrote:
| 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> i 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/6...
|
| [0] https://doc.rust-lang.org/std/iter/fn.successors.html
|
| [1] https://docs.rs/itertools/latest/itertools/fn.unfold.html
| bee_rider wrote:
| 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 wrote:
| 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 wrote:
| 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 wrote:
| 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 wrote:
| 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 wrote:
| 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 wrote:
| I read a similar argument for graphs in general,[0] where this
| is more obviously true.
|
| [0] https://www.hillelwayne.com/post/graph-types/ and
| https://news.ycombinator.com/item?id=39592444
| jpmonettas wrote:
| Clojure has tree-seq https://clojuredocs.org/clojure.core/tree-
| seq
| crvdgc wrote:
| https://hackage.haskell.org/package/base-4.21.0.0/docs/Data-...
| kreetx wrote:
| 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 wrote:
| > "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 wrote:
| If we're fixing the language, may as well fix the real problem
| and not artificially limit stack space.
| Retr0id wrote:
| 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.
| Xmd5a wrote:
| 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 wrote:
| How about clojure zipper:
|
| https://clojuredocs.org/clojure.zip/zipper
| nimih wrote:
| 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 wrote:
| (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 wrote:
| 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 wrote:
| > 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 wrote:
| So we can go back to just use them and just write a new
| library
| monkeyelite wrote:
| You don't need the standard library to make iterators.
| meindnoch wrote:
| 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 wrote:
| I'm 100% sure smug Haskellers have something very important to
| say here. :)
| Joel_Mckay wrote:
| Normally someone would respond, but they are prone to lazy
| evaluation...
|
| Thank you... I'll see myself out... lol =3
| monkeyelite wrote:
| 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.
| john-h-k wrote:
| 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
|
| 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 wrote:
| 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
| chess_buster wrote:
| 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 wrote:
| 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 wrote:
| 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 wrote:
| If nodes have pointers to their parent, constant space tree
| traversal is easy enough.
| HelloNurse wrote:
| 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 wrote:
| "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 wrote:
| 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 wrote:
| 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
| ivanjermakov wrote:
| I think functional languages handle this nicely with Foldable or
| Traversable typeclasses:
| https://hackage.haskell.org/package/base-4.21.0.0/docs/Data-...
| dtech wrote:
| Folding and traversing can be trivially done in all relevant
| programming languages if you have an iterator
| trealira wrote:
| 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 wrote:
| 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 wrote:
| 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.
| munchler wrote:
| Agreed. It's amusing to see procedural programmers slowly
| rediscovering what functional programmers have known for years.
| Paul Graham called this "The Blub Paradox".
| specialist wrote:
| 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. Voila, no more null checks or NPEs.
| kelseyfrog wrote:
| 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 wrote:
| Well, recursion is well-structured and can be reasoned about
| through induction. Goto is unstructured...
| Mikhail_K wrote:
| 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 wrote:
| 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 wrote:
| Well common lisp has it.
| hyperhello wrote:
| 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 wrote:
| 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 wrote:
| 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 wrote:
| 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/
| qoez wrote:
| How in the world is this getting a HN hug of death when it's a
| substack page?
| danieloj wrote:
| 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 wrote:
| 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 wrote:
| 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 wrote:
| The (V)DOM is a tree. Knowing that is useful for manipulating
| and composing it.
| ozten wrote:
| Folder UI components are a common case.
| demarq wrote:
| I would think iterators are exactly this. And they exist in
| almost every language.
| pgt wrote:
| 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
|
| 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.
| foota wrote:
| 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-...)
| :)
|
| 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.
| hinkley wrote:
| 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 wrote:
| 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 wrote:
| 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.
| adamc wrote:
| Or maybe you need a different language, where implementing an
| efficient tree traversal operation is easier?
| gue5t wrote:
| 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/...
| jdeaton wrote:
| 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 wrote:
| 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.
| kazinator wrote:
| Here is the same _for-tree_ macro processing TXR Lisp 's built-
| in search tree type. That does not use structs, but built in
| node and tree types.
|
| The left, right and key fields of a node object are accessed
| with like-named functions. We must call _tree-root_ on a tree
| object to get to the encapsulated root node: 1>
| (for-tree n (tree-root #T(() 1 2 3 4 5 6 7 8)) (left n) (right
| n) (prinl (key n))) 1 2 3 4
| 5 6 7 8
|
| How about a tree of integers. Let's say the root integer is 1,
| and to go left is to multiply by 2, and to go right is to
| multiply by 2 and mask in a 1. And let's say the depth caps out
| at the value 16: 2> (for-tree n 1 (if (< n 8)
| (* 2 n)) (if (< n 8) (+ 1 (* 2 n))) (prinl n))
| 8 4 9 2 10 5 11 1
| 12 6 13 3 14 7 15 nil
|
| Let's see that in binary: 3> (for-tree n 1 (if
| (< n 8) (* 2 n)) (if (< n 8) (+ 1 (* 2 n))) (format
| t "~b\n" n)) 1000 100 1001 10
| 1010 101 1011 1 1100 110
| 1101 11 1110 111 1111 nil
|
| Let's right-align digits to see different patterns in it:
| 2> (for-tree n 1 (if (< n 8) (* 2 n)) (if (< n 8) (+ 1 (* 2
| n))) (format t "~6b\n" n)) 1000 100
| 1001 10 1010 101 1011
| 1 1100 110 1101 11
| 1110 111 1111 nil
|
| Nah, left-aligned wins.
| kazinator wrote:
| I forgot I can remove the outer parentheses, and also use
| infix with C-like operators, since I have those modes turned
| on in the REPL. (Infix is an unreleased feature, coming in
| TXR 300). 3> for-tree n 1 (if (n < 8) (n <<
| 1)) (if (n < 8) (n << 1 | 1)) (format t "~b\n" n)
| 1000 100 1001 10 [...]
| thatguysaguy wrote:
| 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!
___________________________________________________________________
(page generated 2025-04-29 23:00 UTC)