How do you implement a recursive walker of a tree with a lazy range?

Chris Cain clcain at uncg.edu
Tue Oct 29 20:53:50 PDT 2013


Here's the code:
----
     InputRange!Tree walk()
     {
         return inputRangeObject(chain(
             [this],
             children.map!(a=>a.walk())().joiner()));
     }
----
Result:
---
[root, root.1, root.1.1, root.1.2, root.2, root.2.1, root.2.2]
---

It's a bit confusing to explain how I came up with that, but 
essentially you have to cleanly terminate the type inference 
(hence why I used an inputRangeObject) and make sure you map the 
walk function on all of the children. Mapping on the children 
creates a range of ranges (essentially, it turns your range of 
children into a range of results of walking, which are ranges), 
so you must flatten it into a single range using a join. After 
that, I prepended the [this] reference using a regular chain 
similar to what you were doing.

I'm not confident that this is the most efficient way, but it 
works.


More information about the Digitalmars-d-learn mailing list