Question about recursively generated iterators

[perlfan]

I've been going over the posts and tutorials here on this subject, and I have made it to the point where I can code a very straightforward example of very simple recursion.

#!/usr/bin/env perl
use strict;
use warnings;

sub recurse_factory {
  my $max = shift;
  my $number = shift;
  if ($number < $max) {
    return sub { return recurse_factory($max,$number+1); }
  } else {
    return sub { print "done ... $number\n"; };
  }
}

my $TIMES = 100;
my $next = recurse_factory(100,0);
for (1..$TIMES+1) {
  $next = $next->();
}

However, I am trying to figure out how one may use this method (if at all) for a more complicated recursive algorithm. In essence what I'd like to do is find all acyclic paths in a digraph using the recursive depth first search method.

In otherwords, the recursion pattern looks more like the depth first traversal of a tree than a simple straight line like my simple example above. I am sure locked away in the great explanations I've found on this site is the key, but I need to be hit with a really big clue stick.

I think for this discussion, the recursive depth first traversal of a tree that returns a full root-to-leaf path would be an appropriate example...btw, I am assuming that this can be done with rgi's, but I could be wrong there, too.

TIA

[ikegami]

I tried to see if I could find a generic way of transforming a recursive function into an iterator. I found a method that's can be applied rather mechanically.

Let's say your recursive function visits a tree in preorder. The following would be the a non-iterative solution:

sub visit_preorder(&$) {
   my ($visitor, $node) = @_;
   my ($val, $l, $r) = @$node;
   $visitor->() for $val;
   &visit_preorder($visitor, $l) if defined $l;
   &visit_preorder($visitor, $r) if defined $r;
}

Change the visitor code to return \$val; where $val is the data to return from the iterator. return \@val; is also acceptable if you wish to return more than one value.

Break up the function where a recursive call is made. Return each block as a function as follows:

sub visit_preorder {
   my ($node) = @_;
   my ($val, $l, $r) = @$node;
   return (
      sub { return \$val;                                    },
      sub { return visit_preorder($l) if defined $l; return; },
      sub { return visit_preorder($r) if defined $r; return; },
   );
}

In this case, it can be simplified a little.

sub visit_preorder {
   my ($node) = @_;
   my ($val, $l, $r) = @$node;
   return (
      \$val,
      defined($l) ? sub { return visit_preorder($l); } : (),
      defined($r) ? sub { return visit_preorder($r); } : (),
   );
}

Now we just need an engine to drive this.

sub make_iter {
   my $f = shift @_;
   my @todo = $f->(@_);
   return sub {
      while (@todo) { 
         my $todo = shift @todo;
         if (ref($todo) eq 'CODE') {
            unshift @todo, $todo->();
         } elsif (ref($todo) eq 'ARRAY') {
            return @$todo;
         } else {
            return $$todo;
         }
      }
      return;
   };
}

Finally, an example caller.

{
   #      a
   #     / \
   #    b   e
   #   / \   \
   #  c   d   f

   my $tree = [
      'a',
      [
         'b',
         [
            'c',
            undef,
            undef,
         ],
         [
            'd',
            undef,
            undef,
         ], 
      ],
      [
         'e',
         undef,
         [
            'f',
            undef,
            undef,
         ], 
      ], 
   ];

   my $iter = make_iter(\&visit_preorder, $tree);
   while (my ($name) = $iter->()) {
      print($name);
   }
   print("\n");
}

[ikegami]

This method can be used when a function has a loop, since loops can be implemented using recursion. This is great because it facilitates making iterators from functions where the call to the visitor is not at the end and from functions with multiple calls to the visitor.

For example, let's create a fibonacci generator. A simple implementation is:

sub fibonacci {
   my ($visitor) = @_;
   my ($i, $j) = (0, 1);
   $visitor->() for $i;
   for (;;) {
      $visitor->() for $j;
      ($i, $j) = ($j, $i+$j);
   }
}

Replace the loop with recursion.

sub fibonacci {
   my ($visitor) = @_;
   my ($i, $j) = (0, 1);
   $visitor->() for $i;
   _fibonacci($i, $j);
}

sub _fibonacci {
   my ($visitor, $i, $j) = @_;
   $visitor->() for $j;
   _fibonacci($j, $i+$j);
}

Convert for make_iter.

sub fibonacci {
   my ($i, $j) = (0, 1);
   return ( \$i, sub { _fibonacci($i, $j) } );
}

sub _fibonacci {
   my ($i, $j) = @_;
   return ( \$j, sub { _fibonacci($j, $i+$j) } );
}

Try it out

{
   my $iter = make_iter(\&fibonacci);
   for (0..15) {
      my ($n) = $iter->()
         or last;
      print("$n ");
   }
   print("\n");
}

0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610

[perlfan]

Very much appreciated, ikegami! This is very helpful.

[Limbic~Region]

perlfan,
Have you seen Recursively-generated Iterators? I have written a number of tutorials on iterators but they do not deal with recursion.

[perlfan]

Thank you, yes I have. I prefaced this in the beginning of the question, but maybe I should have listed them explicitly. Your stuff actually got me started down this dark and scary road :)

[Limbic~Region]

perlfan,
Your stuff actually got me started down this dark and scary road :)

I am truly flattered. I can show you examples of both DFS and BFS iterators but they are not ones that I converted from a recursive algorithm. I almost never think of problems in terms of recursion. Probably why Haskell still eludes me.

Don't hesitate to /msg me with questions about something I have written, if you would like some examples, or if you would like me to write up a tutorial on something (assuming I am capable).

[artist]

You might want to read Higher Order Perl