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

Andrej Mitrovic andrej.mitrovich at gmail.com
Tue Oct 29 16:48:20 PDT 2013


Instead of the usual opApply approach, how would you implement an auto
return walker function *without* defining a special external struct
that holds all the logic? In other words, using existing Phobos
functionality only, composing functions like map and chain. Example
code which isn't correct:

-----
module test;

import std.algorithm;
import std.range;
import std.stdio;

struct Tree
{
    string value;
    Tree[] children;

    /** Walk the entire tree. */
    auto walk()
    {
        return map!(
            // note the [] workaround to make it a range
            a => chain([a], a.children)
        )([this]);  // note the [] workaround to make it a range
    }

    string toString()
    {
        return value;
    }
}

void main()
{
    auto tree =
        Tree("root",
        [
            Tree("root.1",
            [
                Tree("root.1.1"),
                Tree("root.1.2")
            ]),

            Tree("root.2",
            [
                Tree("root.2.1"),
                Tree("root.2.2")
            ]),
        ]
    );

    writeln(tree.walk);
}
-----

In case it's not displayed correctly I've pasted it here too:
http://dpaste.dzfl.pl/88409749

Can this be properly implemented using map?


More information about the Digitalmars-d-learn mailing list