Fun with recursive anonymous subroutines

I'm doing lots of work with representing stuff stored in the file system as trees at the moment as part of my toolkit for open source qualitative research software.

One of the things I need to do (for making reports) is to transform this:

 [ [qw/foo bar/],
   [qw/a b /],
   [qw/x y/], ];

into this tree structure:

   'foo' => {
       'some_data' => 'lvl0',
       'children' => {'a' => {
           'some_data' => 'lvl1',
           'children' => { 'y' => 'leaf', 'x' => 'leaf' } },
                      'b' => {
                          'some_data' => 'lvl1',
                          'children' => {
                              'y' => 'leaf', 'x' => 'leaf' }}}}};

Being a nice golf problem I thought I'd ask on irc if there was a hacker better than me who felt like taking a look at this. ribasushi++ obviously had a little procrastination time available and wrote me a nice solution which I needed to make into a closure via a recursive subref:

There are two gotchas with this code. Firstly we need to weaken() the coderef before calling it in order to prevent a memory leak. The second problem is that we have to jump through some hoops to make the coderef in scope when $visit->(@args) is called inside itself. There are three ways of dealing with this. I could use Sub::Recursive, but the implementation is apparently non-ideal as it uses local, which is expensive. A more robust way via the CPAN is to use Sub::Current which provides a special function ROUTINE, which returns a code reference pointing at the currently executing subroutine. This is probably the correct way to do things. But the solution I plumped for (for now) is a little scope trick:

my ($visit, $v); 
$v = $visit = sub { ... $visit->(@args) ... };
my $data $visit->();

This is more fragile in terms of memory leak protection than using Sub::Current, but for my purposes is adequate for the present day. I have of course added a comment to the effect that I may need to upgrade to Sub::Current at some point in the future. (Thanks to mst++ for explaining this stuff to me in words that I could understand).

Now I have to work out how to get the real data into the leaf nodes :)


Another way you might want to look at to do that is CPS. A basic way to repeatedly call the anonymous closure is to use kwhile. What you've built there is recursive descent on a data structure, so you might also prefer one of the recursive descent helpers, kdescendd or kdescendb.

Perhaps you've found an interesting use case that's worthy of a tree-shaped map-style functional to be added to CPS::Functional.

Thanks for an example on how to use weaken in this case.

Sub::Recursive deals with the problem. It makes execution slower, but code looks a little bit cleaner.

Leave a comment

About Holy Zarquon's Singing Fish

user-pic Catalyst hacker, management researcher and health informatician.