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

[Chris Cain]

On Wednesday, 30 October 2013 at 16:50:33 UTC, Chris Cain wrote:
> you would avoid allocations.

Actually, let me clarify. You'd avoid *those* allocations. 
inputRangeObject allocates a class. Unfortunately, I'm not 
certain it's possible to do this cleanly without such a thing 
using inputRangeObject because otherwise you'd have infinite 
recursion on the types.

To limit it to a single allocation, perhaps you could have two 
functions, walk and innerWalk. The outer walk could allocate some 
memory on the heap (requiring knowledge of the maximum depth of 
the tree either by exploring the tree prior to walking it or 
having the tree hold parent pointers & depths) and the inner walk 
could take the memory as a parameter. Each recursion would just 
do mem[1..$] Technically, this should work as well. But it won't 
be as clean of a solution. It still wouldn't have "no" 
allocations, but it's the best I can do to limit them.

Ultimately, if you want to do this lazily with no allocations and 
with maximum performance, I think you'll have to make a custom 
range struct holding the things you need. That said, it can be 
done with the standard library (and as I've shown, it can look 
pretty clean and simple) but it probably won't be maximum 
performance and have no allocations.