Thread overview
Fun with recursions
Feb 21, 2020
Andrej Mitrovic
Feb 22, 2020
Andrej Mitrovic
February 21, 2020
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.
February 21, 2020
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
February 22, 2020
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. :)
February 22, 2020
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