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.
