[challenge] Lazy flatten/avoiding type forward reference with map

[Ali Çehreli]

On 10/31/2013 12:09 PM, David Nadlinger wrote:
> A while back, somebody raised the topic of implementing a lazy range for
> traversing/flattening a tree structure on #d.
>
> The obvious (in terms of Phobos primitives) solution would be something
> along the lines of this:
> ---
> struct Node(T) {
>     T val;
>     Node!T[] children;
> }
>
> auto flatten(T)(Node!T root) {
>     import std.algorithm, std.range;
>     return only(root.val).chain(map!flatten(root.children).joiner);
> }
>
> void main() {
>     alias N = Node!int;
>     auto a = N(1, [
>        N(2, [
>           N(3, [
>              N(4)
>           ])
>        ]),
>        N(5)
>     ]);
>
>     import std.stdio;
>     writeln(a.flatten); // [1, 2, 3, 4, 5]
> }
> ---
>
> But of course, that piece of code does not compile with current DMD, as
> the return type of flatten() can't refer to the function itself (during
> name mangling).
>
> Now, one way around this would be to add an array() call at the end of
> the return statement, which hides the type of map!flatten, but at the
> cost of many unnecessary memory allocations. A second option would be to
> use inputRangeObject to convert the return value to ForwardRange!T
> (well, that is if it actually worked, due to an implementation bug it
> leads to a runtime crash).
>
> But can you think of a more simple/elegant workaround?
>
> (Note aside: Obviously, the fact that the code relies on recursion might
> be an issue, and a simple opApply-based solution with a worklist stack
> would likely perform better. Still, I think it's a simple, yet
> interesting problem.)
>
> David

Y Combinator? (No, I have not solved it yet. :) )

   http://rosettacode.org/wiki/Y_combinator#D

Ali