Programming languages should have a tree traversal primitive

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

Arent haskell traversables different in that they preserve the structure if you were to map over them, as compared to the solution posted in the article, where they get flattened to what amounts to a list?

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

Haskell has 'Traversable' (and 'Foldable' etc) which are a lot more approachable than the fully generalised lens library.

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

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

The "syntax extension" thing is precisely the reason I have an interest in (and advocacy for) Common Lisp.

Be that as it may, for C++, Eric Neibler's [Boost.Proto](https://www.boost.org/doc/libs/1_84_0/doc/html/proto.html) could likely help conveniently connect syntax to implementation to achieve something similar to what the author is taking about.

Does this mean something like $tree_object =~ m/regex/ will work and return a sub tree?

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

Linus Torvalds also spoke in favour of using adequate data structures instead of the code.

Lisp gives you an infinite amount of functions that operate on one data structure: the cons cell. :P

I guess all you really need are dynamically allocated arrays. A cons cell is an array of two. A struct with N fields is an array of N. Everything else is built on that.

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.

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.

Sure, but it can be done by a library. There's no reason it needs to be built into the language.

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.

I avoided the stack limit by using itertools.chain: https://github.com/DavidBuchanan314/millipds/blob/15727d474c...

(this is for iterating over nested JSON-like objects, which are just weird trees)

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

    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)

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

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.

It seems like it should be possible to factor out most of the iterator boilerplate into a helper class. Then each place where you want to iterate you can construct an instance of that helper class and supply a lambda that specifies how to descend into children. If you're doing the same iteration in several places then you can use a named function instead of a lambda, which means less typing for each `for` loop. Here's a rough sketch: https://godbolt.org/z/x94WY77rv

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.

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

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`?

> (which avoid potential problems with recursion stack depth).

Iterators for trees are not implemented with call stack recursion.

> I'm surprised nobody's brought up C++ generators yet

You cannot modify, insert, or use standard algorithms with a generator.

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

> Sequences, trees and graphs are core abstractions to most programming, why try to flatten all trees and graphs to sequences?

Because "trees" and "graphs" aren't actually single concepts, they're families of concepts that can vary along many dimensions. Most programming languages offer one or a small handful of sequence types, because most sequence use patterns are the same. Most languages don't offer a tree or graph type, and as soon as you try to implement one you see why: there are multiple different kinds of trees and graphs, and multiple different representations that are appropriate for different use cases, and any one you might pick would be unsuitable for most programs people want to write.

The point wasn't that it should be treated as a sequence of not, but that with good base abstractions you can move the decision of what to do, and how, into the data structure itself, rather than having to have the language decide for it.

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

Don't iterators necessarily "forget" the structure of the tree? I can see how you can write an iterator to, for example, compute the size of a tree, or generate the set of all variables that occur in an expression tree.

But it's not obvious to me how you'd write a generic iterator that supports something like finding all free variables in an expression tree, or even just express a tree mapping function that constructs a new tree with the same structure (for example, "make all variables in the expression uppercase"). It's been a while since I worked with iterators so correct me if I'm wrong and this is in fact easy with iterators.

With something like Haskell's recursion-schemes library [0] these operations are all just a few lines long, guaranteed to terminate, and don't need to be updated if your data structure changes (for example you add new expression nodes). I'm not aware of any non-functional programming language that can do that. See for example the freeVars function at the bottom of the linked recursion-schemes doc.

[0] https://hackage.haskell.org/package/recursion-schemes-5.2.3

I do think recursion schemes are pretty cool, particularly the idea that a list fold could be generalized to the concept of catamorphisms, which could be mechanically derived upon defining a data structure, because the shape of the recursion that's defined is the same as the shape of the recursion of the data constructors. It makes me realize that programming languages still could be higher-level; what if a programming language automatically derived the equivalent of the "fold" and "map" functions for any recursive data type defined by the programmer?

At the same time, the way it's implemented in Haskell's recursion-schemes library might be hard to wrap one's head around at first, kind of like how the list functions "foldr" and "foldl" are also often confusing to newbies, even though they're like the go-to, default way to make list functions in Haskell.

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.

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.

The point is not to do that.