## digitalmars.D - Fun with recursions

• Andrej Mitrovic (28/28) Feb 21 One of my pet peeves about ranges is that they are sometimes hard
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
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
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
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