www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - [challenge] Lazy flatten/avoiding type forward reference with map

reply "David Nadlinger" <code klickverbot.at> writes:
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
Oct 31 2013
next sibling parent reply =?UTF-8?B?QWxpIMOHZWhyZWxp?= <acehreli yahoo.com> writes:
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
Oct 31 2013
next sibling parent =?UTF-8?B?QWxpIMOHZWhyZWxp?= <acehreli yahoo.com> writes:
On 10/31/2013 02:19 PM, Ali Çehreli wrote:

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

    http://rosettacode.org/wiki/Y_combinator#D
Ok, I was actually trying to find the following one: https://github.com/gecko0307/atrium/blob/master/dlib/functional/combinators.d Ali
Oct 31 2013
prev sibling parent Timon Gehr <timon.gehr gmx.ch> writes:
On 10/31/2013 10:19 PM, Ali Çehreli wrote:
 ...

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

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

 Ali
Oh my god, my eyes! auto y(S,T...)(S delegate(T) delegate(S delegate(T)) f){ struct F{ S delegate(T) delegate(F) f; alias f this; } return (x=>x(x))(F(x=>f((T v)=>x(x)(v)))); }
Nov 03 2013
prev sibling parent reply Philippe Sigaud <philippe.sigaud gmail.com> writes:
 But can you think of a more simple/elegant workaround?
Is a standard lazy struct range authorized?
Nov 01 2013
parent reply "David Nadlinger" <code klickverbot.at> writes:
On Friday, 1 November 2013 at 09:34:20 UTC, Philippe Sigaud wrote:
 But can you think of a more simple/elegant workaround?
Is a standard lazy struct range authorized?
Sure. This wasn't intended as an actual challenge, as I don't have a "right" answer myself (or a prize, for that matter). ;) I just thought I'd be interested to see what the best solution we can find in terms of conciseness is. David
Nov 01 2013
parent Andrej Mitrovic <andrej.mitrovich gmail.com> writes:
On 11/1/13, David Nadlinger <code klickverbot.at> wrote:
 I just thought I'd be interested to see what the best solution we
 can find in terms of conciseness is.
Note that I've already asked this in D.learn: http://forum.dlang.org/thread/mailman.43.1383090512.9546.digitalmars-d-learn puremagic.com
Nov 01 2013