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

sticking to dfs, there is still a difference between pre-order/in-order/post-order

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);

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.

well, functional languages with recursive types, are very good at representing binary trees

https://cs3110.github.io/textbook/chapters/data/trees.html

Pick a language that allows users to define their own control structures and test your idea in practise.

Candidates: Racket, Scheme, Rust.

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.

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.

    Account acc = getAccount();
    QVERIFY(acc.person.address.house == 20);

    auto houseLens = personL() to addressL() to houseL();
    std::function<int(int)> modifier = [](int old) { return old + 6; };
    
    Account newAcc2 = over(houseLens, newAcc1, modifier);

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.

    for_tree(string x = ""; x.size() <= 8; x : {x+"a", x+"b", x+"c"}){
     print(x);
    }

    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;
    }

    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)

    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"]

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

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

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.

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/6...

[0] https://doc.rust-lang.org/std/iter/fn.successors.html

[1] https://docs.rs/itertools/latest/itertools/fn.unfold.html

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?

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.

Clojure has tree-seq https://clojuredocs.org/clojure.core/tree-seq

> "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!

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."

    (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)))

    (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))))

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.

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.

I'm 100% sure smug Haskellers have something very important to say here. :)

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.

    for (const auto&node: await depth_first_tree(node)) 

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

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