Welcome to the Monastery PerlMonks

### Re: Question about recursively generated iterators

by ikegami (Pope)
 on Sep 21, 2007 at 15:52 UTC ( #640390=note: print w/replies, xml ) Need Help??

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");
}

Replies are listed 'Best First'.
Re^2: Question about recursively generated iterators
by ikegami (Pope) on Sep 21, 2007 at 16:48 UTC

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
Very much appreciated, ikegami! This is very helpful.

Create A New User
Node Status?
node history
Node Type: note [id://640390]
help
Chatterbox?
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others scrutinizing the Monastery: (5)
As of 2018-06-18 23:56 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
Should cpanminus be part of the standard Perl release?

Results (111 votes). Check out past polls.

Notices?