note
ikegami
<p>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.
<p>Let's say your recursive function visits a tree in preorder. The following would be the a non-iterative solution:
<c>
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;
}
</c>
<p>Change the visitor code to <c>return \$val;</c> where <c>$val</c> is the data to return from the iterator. <c>return \@val;</c> is also acceptable if you wish to return more than one value.
<p>Break up the function where a recursive call is made. Return each block as a function as follows:
<c>
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; },
);
}
</c>
<p>In this case, it can be simplified a little.
<c>
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); } : (),
);
}
</c>
<p>Now we just need an engine to drive this.
<c>
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;
};
}
</c>
<p>Finally, an example caller.
<c>
{
# 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");
}
</c>
640382
640382