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