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");
}
-
Are you posting in the right place? Check out Where do I post X? to know for sure.
-
Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:
<code> <a> <b> <big>
<blockquote> <br /> <dd>
<dl> <dt> <em> <font>
<h1> <h2> <h3> <h4>
<h5> <h6> <hr /> <i>
<li> <nbsp> <ol> <p>
<small> <strike> <strong>
<sub> <sup> <table>
<td> <th> <tr> <tt>
<u> <ul>
-
Snippets of code should be wrapped in
<code> tags not
<pre> tags. In fact, <pre>
tags should generally be avoided. If they must
be used, extreme care should be
taken to ensure that their contents do not
have long lines (<70 chars), in order to prevent
horizontal scrolling (and possible janitor
intervention).
-
Want more info? How to link
or How to display code and escape characters
are good places to start.