www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Fun with recursions

reply Andrej Mitrovic <andrej.mitrovich gmail.com> writes:
One of my pet peeves about ranges is that they are sometimes hard 
to compose with recursive data structures.

For example, let's say you have a data structure like this:

struct Node
{
     string name;
     int[] numbers;
     Node[] nodes;
}

Maybe you are interested in collecting all of the names of the 
nodes, starting from some root node. Or maybe you want the 
numbers instead. And you want a range, damn it!

It's very easy to write a recursive function manually, but then 
we're writing dumb iterative functions and that's no fun. :>

I can't think of any helper functionality in Phobos that would 
let me do this. So I wrote something of my own with Generators:

https://gist.github.com/AndrejMitrovic/282d062c09a6df697476a8304bb23c19


Here's what it looks like:

-----
Node node = { ... };

auto r1 = node.getRecursive!(n => n.numbers);
r1.each!(numbers => writeln(numbers));

auto r2 = node.getRecursive!(n => n.name);
r2.each!(name => writeln(name));
-----

It's very simplistic, but I think it could easily be expanded 
upon. And it could use a better name. It's possible I'm not 
seeing an easier solution though, so destroy if you must.
Feb 21 2020
parent reply Steven Schveighoffer <schveiguy yahoo.com> writes:
On Friday, 21 February 2020 at 16:49:15 UTC, Andrej Mitrovic 
wrote:


 It's very simplistic, but I think it could easily be expanded 
 upon. And it could use a better name. It's possible I'm not 
 seeing an easier solution though, so destroy if you must.


This is pretty heavy handed. All that is needed is a stack and a 
recursion function.

This works, and returns a range of Node, then you have to map to 
what you actually want (reasonable to me instead of leaving the 
recursion up to introspection):

https://gist.github.com/schveiguy/962e36cea6a979a47b708cb4335f9f82

I don't love that chain call to get the first node in there. But 
I don't know your requirements, so...

-Steve
Feb 21 2020
parent reply Andrej Mitrovic <andrej.mitrovich gmail.com> writes:
On Friday, 21 February 2020 at 17:52:01 UTC, Steven Schveighoffer 
wrote:

 https://gist.github.com/schveiguy/962e36cea6a979a47b708cb4335f9f82


Well, I don't like the 'new' call there. :)
Feb 22 2020
parent Steven Schveighoffer <schveiguy gmail.com> writes:
On 2/22/20 4:59 AM, Andrej Mitrovic wrote:

 On Friday, 21 February 2020 at 17:52:01 UTC, Steven Schveighoffer wrote:

 https://gist.github.com/schveiguy/962e36cea6a979a47b708cb4335f9f82


 
 Well, I don't like the 'new' call there. :)


You know Generator is a Fiber/class and it allocates stack, right? Or is 
it just a problem with the GC running?

I also just noticed, this is potentially going to return a reference to 
stack space that goes out of scope (you are avoiding new at the cost of 
memory safety here). Even if you postblit the class pointer to the right 
place, the compiler is free to move your struct around. You really 
should allocate this on the heap.

https://gist.github.com/AndrejMitrovic/282d062c09a6df697476a8304bb23c19#file-get_recursive-d-L54

Not only that, but your destructor doesn't destroy the fiber, so you are 
leaking stack memory.

Any way you want to allocate stack, you can potentially use the gist I 
posted. The linked list is the easiest to do, but you could also do a 
amortized constant allocation scheme based on an array if you wanted. 
You can even use C malloc if you don't care about dangling pointers to 
range elements. Or use RefCounted to allocate the linked list.

-Steve
Feb 22 2020