Programming languages should have a tree traversal primitive

Scope of the Proposed Primitive

• Many argue a “tree traversal primitive” is just a specialized iterator and should live in libraries, not in language syntax.
• Objection: making it a primitive is language bloat, especially in already feature-heavy languages like C++.
• Counterpoint: trees (and graphs) are fundamental; ergonomic traversal syntax could enable better default patterns and optimizations (e.g., parallelism).

Traversal Orders and Flexibility

• Critics note the primitive quickly becomes underspecified:
  • DFS vs BFS, and then pre-/in-/post-order variants.
  • Need to skip branches, terminate early, or traverse in unusual orders.
• By the time all options are encoded, the primitive looks like a general traversal framework—essentially the code you’d write anyway.

Existing Abstractions in Functional / Declarative Worlds

• Functional languages already have strong patterns:
  • Algebraic data types + recursion; typeclasses like Functor, Foldable, Traversable.
  • Recursion schemes (catamorphisms, hylomorphisms) to systematically define traversals.
  • Optics (lenses, prisms, traversals) and zippers for composable navigation and updates.
• Clojure examples: tree-seq, clojure.walk, zippers; SQL CTEs and logic/relational languages cited as tree/graph-friendly models.
• Some say this is exactly what the article wants, just as library-level abstractions rather than compiler magic.

Iterators, Generators, and Coroutines

• In imperative languages, the dominant view is: define iterators/generators:
  • C++ iterators, C++20/23 coroutines & generators, C# IEnumerable + yield, Python/Dart generators, Rust’s successors and ControlFlow.
  • Tree-specific traversal can be implemented once per structure and reused with normal for loops.
• Several concrete patterns are shown: explicit stacks/queues for DFS/BFS, generic “successor” functions, or iterator helpers.

Recursion, Stack Limits, and Performance

• Recursive traversals are easy to write but risk stack overflows; explicit stacks or generator-based state machines avoid this.
• Some suggest fixing stack limitations or using tail-call optimization; others note many traversals aren’t tail-recursive.
• Hardware/cache behavior and representation choice (binary vs general trees, parent pointers, indirection) complicate any “universal” primitive.

Design Sentiment

• Overall: strong skepticism that tree traversal deserves special syntax.
• Preference: powerful, composable library abstractions (iterators, optics, recursion schemes) over new control-flow primitives.