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

[bearophile]

Chris Cain:

>     InputRange!Tree walk()
>     {
>         return inputRangeObject(chain(
>             [this],
>             children.map!(a=>a.walk())().joiner()));
>     }


I have used your nice idea to create another partial D solution 
for this task:
http://rosettacode.org/wiki/Tree_traversal#D


import std.stdio, std.algorithm, std.range, std.conv, std.string;

struct Tree(T) {
     T value;
     Tree* left, right;
}

alias VisitRange(T) = InputRange!(const Tree!T);

VisitRange!T preOrder(T)(in Tree!T* t) {
     enum self = mixin("&" ~ __FUNCTION__.split(".").back);
     if (t == null)
         return typeof(return).init.takeNone.inputRangeObject;
     return [*t]
            .chain([t.left, t.right]
                   .filter!(t => t != null)
                   .map!(a => self(a))
                   .joiner)
            .inputRangeObject;
}

VisitRange!T inOrder(T)(in Tree!T* t) {
     enum self = mixin("&" ~ __FUNCTION__.split(".").back);
     if (t == null)
         return typeof(return).init.takeNone.inputRangeObject;
     return [t.left]
            .filter!(t => t != null)
            .map!(a => self(a))
            .joiner
            .chain([*t])
            .chain([t.right]
                   .filter!(t => t != null)
                   .map!(a => self(a))
                   .joiner)
            .inputRangeObject;
}

VisitRange!T postOrder(T)(in Tree!T* t) {
     enum self = mixin("&" ~ __FUNCTION__.split(".").back);
     if (t == null)
         return typeof(return).init.takeNone.inputRangeObject;
     return [t.left, t.right]
            .filter!(t => t != null)
            .map!(a => self(a))
            .joiner
            .chain([*t])
            .inputRangeObject;
}

VisitRange!T levelOrder(T)(in Tree!T* t) {
     enum self = mixin("&" ~ __FUNCTION__.split(".").back);
     return typeof(return).init.takeNone.inputRangeObject;
     // UNFINISHED
}

void main() {
     alias N = Tree!int;
     auto tree = new N(1,
                       new N(2,
                             new N(4,
                                   new N(7)),
                             new N(5)),
                       new N(3,
                             new N(6,
                                   new N(8),
                                   new N(9))));

     tree.preOrder.map!(t => t.value).writeln;
     tree.inOrder.map!(t => t.value).writeln;
     tree.postOrder.map!(t => t.value).writeln;

     // Should print: [1, 2, 3, 4, 5, 6, 7, 8, 9]
     tree.levelOrder.map!(t => t.value).writeln;
}


As you see levelOrder is not finished.

I don't know if there is a simple way to return that something 
for empty input (simpler than 
typeof(return).init.takeNone.inputRangeObject). I have used it to 
avoid bugs caused by the successive map.writeln.

I don't know if there are nice ways to refactor this code to 
shorten it some.

I'd like that function pointer self to be a D built-in feature. I 
have used it because when you write such kind of code and you 
copy&paste the implementations to create a new visit function 
it's very easy to forget to update the name of the function to 
call recursively.

A related task that is not yet using this idea:
http://rosettacode.org/wiki/Same_Fringe#Haskell

Bye,
bearophile