There should be a control flow construct in programming languages that can handle tree-like traversal in a nice way, similar to how for/foreach loops can handle linear traversal.
Lisp macro:
https://news.ycombinator.com/item?id=43838342
You give it a dummy variable, root expression, and expressions how to navigate left and right relative to dummy variable.
No iterator interfaces; the loop writes the code for walking the binary tree.
Haskell has a lot of ideas for this, e.g. Traversals, Prisms, Lenses, Uniplate, Scrap your Boilerplate.
Uniplate seems to be the most applicable to imperative languages, as it does not require any advanced type system features (just lists).
Some examples:
* In C#: https://github.com/benjamin-hodgson/Sawmill
* In Rust: https://lib.rs/crates/uniplate (shameless plug!)
The paper: https://ndmitchell.com/downloads/paper-uniform_boilerplate_and_list_processing-30_sep_2007.pdf
It's called sum types and pattern matching. It's like 80% of the reason why I like Swift and Rust.
clojure has clojure.walk for tree traversal: https://clojuredocs.org/clojure.walk
There was such an experiment: https://combinatorylogic.github.io/mbase-docs/pfdoc.pdf
For what it is worth, the ParaSail parallel programming language has this:
func Search_Binary_Tree(Root : Binary_Tree;
__Desired_Value : Value_Type) -> optional Id_Type is
____const Result : Id_Type;
____for X => Root then X.Left || X.Right while X not null concurrent loop
______if X.Value == Desired_Value then
_______exit loop with Result => X.Id;
______end if;
____end loop with Result => null;
____return Result;
end func Search_Binary_Tree;
See https://github.com/parasail-lang/parasail
[Is there a better way to preserve indentation? ;-)]
I don't use this feature much, because usually there is a key of some sort that determines which side of the tree is of interest.
Yes; post your comment on HackerNews, and link to it here.
It made front page: https://news.ycombinator.com/item?id=43831628
> Well a range based for loop requires that your tree exist in memory
Why?
Lisp macro:
https://news.ycombinator.com/item?id=43838342
You give it a dummy variable, root expression, and expressions how to navigate left and right relative to dummy variable.
No iterator interfaces; the loop writes the code for walking the binary tree.
Haskell has a lot of ideas for this, e.g. Traversals, Prisms, Lenses, Uniplate, Scrap your Boilerplate.
Uniplate seems to be the most applicable to imperative languages, as it does not require any advanced type system features (just lists).
Some examples:
* In C#: https://github.com/benjamin-hodgson/Sawmill
* In Rust: https://lib.rs/crates/uniplate (shameless plug!)
The paper: https://ndmitchell.com/downloads/paper-uniform_boilerplate_and_list_processing-30_sep_2007.pdf
It's called sum types and pattern matching. It's like 80% of the reason why I like Swift and Rust.
clojure has clojure.walk for tree traversal: https://clojuredocs.org/clojure.walk
There was such an experiment: https://combinatorylogic.github.io/mbase-docs/pfdoc.pdf
For what it is worth, the ParaSail parallel programming language has this:
func Search_Binary_Tree(Root : Binary_Tree;
__Desired_Value : Value_Type) -> optional Id_Type is
____const Result : Id_Type;
____for X => Root then X.Left || X.Right while X not null concurrent loop
______if X.Value == Desired_Value then
_______exit loop with Result => X.Id;
______end if;
____end loop with Result => null;
____return Result;
end func Search_Binary_Tree;
See https://github.com/parasail-lang/parasail
[Is there a better way to preserve indentation? ;-)]
I don't use this feature much, because usually there is a key of some sort that determines which side of the tree is of interest.
Yes; post your comment on HackerNews, and link to it here.
It made front page: https://news.ycombinator.com/item?id=43831628
> Well a range based for loop requires that your tree exist in memory
Why?