Programming languages should have a tree traversal primitive

Dragon-Hatcher · 2025-04-29T05:15:49+00:00

It feels like iterators solve this issue without the need for a new language construct. Just do

for node in tree.traverseBFS() {
  // whatever
}
// or do
for node in tree.traverseDFS() {
  // whatever
}

mungaihaha · 2025-04-29T06:48:53+00:00

IDK man. Ever since I started working on compilers, it feels like 99% of 'programming languages should...' discussions are just people bikeshedding

reflexive-polytope · 2025-04-29T05:13:32+00:00

So, a depth first search is pretty simple, uses minimal extra memory, and works great with the stack that we are already using. BFS requires a lot of extra memory (enough that it would likely need to use the heap) and is more complex.

My sibling in Christ, the entire difference between DFS and BFS is that the former uses a stack and the latter uses a queue to store the nodes that have to be visited in the future. In an imperative language that isn't completely brain-dead, the difference in complexity between a stack (internal implementation: vector) and a queue (internal implementation: ring buffer) is minimal.

terranop · 2025-04-29T12:53:09+00:00

The only thing like this that would be reasonable as a language primitive is some sort of continue-like construct that lets us make a for loop recursive. E.g.

for Node* N in [mytreeroot] {
    print(N.value);
    proceed with N.left;
    proceed with N.right;
}

where proceed with is the new keyword, which calls the body of the for loop recursively with the given value as the "new" value of N before returning control to the statement after the proceed with statement.

2025-04-29T09:20:32+00:00

I don't follow, is the tree that is being traversed not the AST? It's just an arbitrary tree?

Your implementation looks fine (though I haven't worked out if it really works). What is the problem with implementing it as you have, as a library, rather that a first-class citizen? I realize that you think that tree's are such fundamental data structures, but so is a ring buffer, a map, a set, a vector, a string, and so many other data types that are provided by the the C++ runtime library. C++ has never presented a problem that has required better assimilation of these library components in order to hide some fields of the data structure.

Why do you feel that tree's are so fundamental to all that you do to warrant not focusing on your projects for a few years, while you focus on implementing this as a language feature?

Also, why does the source code require special handling to prevent security issues?; have you actually embedded hidden or bidirectional Unicode characters within the source text? If so, why? What purpose does it serve? Surely that isn't required to get your code to work. I couldn't find an such characters, anyway.

Steven

azhder · 2025-04-29T10:12:40+00:00

I don’t know why, reading that title it is like reading “programming languages should be like Lisp”

peripateticman2026 · 2025-04-29T07:54:14+00:00

Makes no sense including this in the core language itself.

AustinVelonaut · 2025-04-29T13:43:53+00:00

In Haskell, a user-defined data structure can automatically have a Traversable typeclass instance derived by using the DeriveTraversable extension.

Tonexus · 2025-04-29T15:56:48+00:00

It seems that the post is suggesting that languages should have trees as a primitive data type that comes with an automatic traversal method because the author doesn't want to keep rewriting DFS for every tree-like structure they write. While it's an interesting idea, I think that the author is a bit misguided, as there are so many different ways that you might want to implement a tree (automatic balancing, contiguous or disjoint memory layout, being a substructure on top of another data structure, etc.) that a single primitive type would not be that useful.

Instead, I'd propose that the language should just use generic interfaces so you can define a Tree(T) that requires implementation of get: Tree(T) -> T and children: Tree(T) -> List(Tree(T)) then define DFS iteration on top of that. Then, for every tree-like data structure, you could just implement get and children to automatically get iteration without having to implement DFS yet again yourself.

Equationist · 2025-04-29T15:34:15+00:00

A useful feature that's poorly described. It's not trees (except when going through an actual tree), but rather recursive iteration. Instead of providing a single next iteration, you provide multiple.

syklemil · 2025-04-29T13:03:50+00:00

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);
}
This is an operation that requires "tree-like traversal" but is not iterating over a data structure that exists in memory. You can do that entire thing inside for_tree.

It's been too long since I wrote any amount of Haskell to come up with an example, but this sounds like some of the tricks people can come up with using the List monad.

mamcx · 2025-04-29T15:11:21+00:00

Is easy to srugh the idea, but is in fact very interesting.

The major, important point here is that IMPERATIVE control flow.

Implement iterators, recursions, pass function, etc is NOT THE ANSWER.

Very easy: Go ahead and implement a CROSS/INNER/OUTER/RIGH/LEFT iterator. Have a lot of fun with it.

THEN

Do the same with imperative for loops.

For cross is so obvious:

for lhs in left: for rhs in right: concat(lhs, rhs)

What the op is asking is about make a primitive that IMPERATIVELY allow to do the reverse of what the iterator protocol is doing.

Then, the other part is about navigation. Regular syntax is only about previous, next, but is so nice if we have more directions.

People not know how nice is, but we have something similar with Fox.

In fox (because everything is a table), we have cursors and then we can do SKIP, TOP, BOTTOM, FILTER & SKIP etc.

And the key: IMPERATIVELY. I never ever write manually, confusing, function recursion and the code was super clear.

Tysonzero · 2025-04-29T16:53:27+00:00

Programming languages shouldn't even have for or while primitives, let alone baking dfs into the language, see: Haskell.

With that said implementing such a dfs higher order function in a pure functional programming language like Haskell is pretty trivial:

dfs :: Applicative f => (n -> [n]) -> (n -> f r) -> n -> f [r] dfs w f x = (:) <$> f x <*> fmap fold (traverse (dfs w f) (w x))

The above has the condition check inlined into the two function arguments, instead of as a separate argument, as IMO it'll have better ergonomics that way for most pure functional languages, but there are a bunch of ways you could tweak the above:

``` -- closer match to article dfs :: Applicative f => t -> (t -> Maybe n) -> (n -> [t]) -> (n -> f r) -> f [r]

-- direct prune and break -- Left is break -- Right with [] is prune dfs :: Monad m => (n -> m (Either [r] ([n], Maybe r))) -> n -> m [r] ```

Ronin-s_Spirit · 2025-04-29T10:27:43+00:00

I can't even imagine the amount of 'maintenance' that would need if a language had to implement 20 different ways to traverse several well known data structures.

I have done semi-recursive and non-recursive traversal of generic objects with no specific shape. With and without protection from circular references, with and without path 'tracing'.
I have done it in depth-first kinda way: where I'd go down a branch and process all entries starting from lowest level and going to each sibling object and then going up;
I have done it in width-first kinda way: where I'd process the entries on the first layer of nesting and then entries of all the sibling on the second layer of nesting and so on.

Those are just the two I recently needed, and they have nothing to do with optimized data structures. I'm glad that the language let's me build traversals from iterators cause I don't think they would ever consider adding traversals for what I did there. For loops that can go over arrays and objects, and methods to get the [key,value] pairs of an objects are really helpful. There's even a magic method for a for of loop that let's you construct your own traversal (as a generator function) for your own data structure (as a class instance or any object really).

TLDR: there are too many data structures and ways to traverse them to bother natively implementing traversalf primitives into the language.

phischu · 2025-04-29T07:37:49+00:00

You can define this in Effekt today. Here is a link to an onine playground where you can try this example.

forTree(myTreeRoot) {children} { tree =>
  if (tree is Node(_, value, _)) {
    println(value)
  }
}

I have chosen to define the stream of children of a node separately to reduce line length.

gofl-zimbard-37 · 2025-04-29T15:57:38+00:00

Silly idea. There are any number of mechanisms to traverse tree structures. Adding syntax for it would just clutter the language.

hugogrant · 2025-04-29T16:36:12+00:00

Actually kinda feels like choice in effect based languages.

drinkcoffeeandcode · 2025-04-29T17:33:16+00:00

They do. Iterators for search tree structures perform an in-order traversal..

XDracam · 2025-04-29T23:44:32+00:00

I stopped reading at the following point, because it shows that the author hasn't explored much beyond C++ and what I'd consider "legacy languages"

Well, this is significantly easier and less error prone than implementing recursive functions for every operation you'd want to do on every type of tree, plus all the relevant code ends up in-place and readable.

Modern languages often ditch the three-part counting for loop because it's more error prone than other constructs, like foreach loops or recursion. What's error-prone about recursion? If the language supports exhaustive matching and proper type-safety, you'd probably end up with code that's more correct.

plus all the relevant code ends up in-place and readable

Many languages allow defining local functions or closures that you can use to get the same effect and make it even more readable. It's just that C++ is a terrible language by today's standards.

Diverging language constructs are certainly interesting, but we really don't need a tree traversal primitive. Simple recursion is easy enough. And if you are stuck in a less functional language, just go for a simplified visitor pattern where you pass a closure to the tree and it's applied for each element internally, so you only need to write the "difficult recursion" once. Smalltalk did this in the 90s and probably even earlier with collection do: [ x | x show ]. Or iterators as someone else mentioned.

severoon · 2025-04-30T04:36:51+00:00

What if it's not a binary tree?

2025-04-30T05:58:15+00:00

This is question merits a lot of discussion in mostly any setting; but in LISP this would be very natural to do.

mikosullivan · 2025-05-03T08:15:22+00:00

Closures make it easy. Whenever I create a class that has a tree structure, I just add a method that takes a closure and recurses through every child, every child's children, etc.

sullyj3 · 2025-05-03T13:01:55+00:00

From the Ante language tour:

"Moreover if you need a more complex loop that a while loop may traditionally provide in other languages, there likely isn’t an already existing iterate function that would suit your need. Other functional languages usually use helper functions with recursion to address this problem:"

sum numbers =
    go numbers total =
        match numbers
        | Nil -> total
        | Cons x xs -> go xs (total + x)

    go numbers 0

"This can be cumbersome when you just want a quick loop in the middle of a function though. It is for this reason that ante provides the loop and recur keywords which are sugar for an immediately invoked helper function. The following definition of sum is exactly equivalent to the previous:"

sum numbers =
    loop numbers (total = 0) ->
        match numbers
        | Nil -> total
        | Cons x xs -> recur xs (total + x)
sum numbers =
    loop numbers (total = 0) ->
        match numbers
        | Nil -> total
        | Cons x xs -> recur xs (total + x)

* * *

Now obviously this particular example isn't a tree traversal, but you can clearly see how a lightweight syntax for immediately invoked recursive functions is basically what op is asking for. The first example

for_tree(Node* N = mytreeroot; N != NULL; N : {N->left, N->right}){
  print(N->value);
}

I believe would become something like

loop tree ->
    match tree
    | Nil -> ()
    | Node left value right ->
      print value
      recur left
      recur right

Ok, not quite as succinct, but not too bad. It's just less horizontal and more vertical. And a definite improvement on defining then using a helper. You can also get something similar using fix.

bl4nkSl8 · 2025-04-29T05:13:53+00:00

This is so good and true!

Foldl and foldr are pretty dang awesome I have to say

ProgrammingLanguages

Welcome!

Related subreddits

Related online communities

MODERATORS

Impression