Your solution is more traditional. It does essentially the same thing as mine — delaying evaluation of later elements until they're needed — by keeping an explicit stack (or what should be a stack, but you seem to be using it as a queue, which explains the different order of return values). You note that it "avoids recursion altogether", but that's not really a legitimate goal. Recursion is not a bad thing in and of itself. It is often a very helpful thing.
The reason I think my solution is an improvement is that it saves you the trouble of manipulating a stack, and allows the iterative solution to more closely resemble the recursive one. In a word: simplicity. You can follow a foolproof recipe, and in five or ten minutes have an iterator that returns exactly the same set as the recursive one. Same order, same structure, same arguments. Here's the recipe (this is new since my original post):
That last is a little complicated to describe in words, so I'll demonstrate with
.
Here's the simple recursive solution:
sub hanoi {
my ($disks, $start, $end, $via) = @_;
return () if $disks == 0;
return ( hanoi($disks-1, $start, $via, $end),
[$start, $end],
hanoi($disks-1, $via, $end, $start)
);
}
Now I'll apply the recipe.
sub iter_hanoi {
my ($disks, $start, $end, $via) = @_;
return sub{} if $disks == 0; # Base case is empty, replace with em
+pty sub
# List of iterators, wrapped in sub{}s to delay their evaluation:
my @sub_iter = (
sub { iter_hanoi($disks-1, $start, $via, $end) },
# Explicit return is assigned to array for iterato
+r to shift
sub {
my @middle_val = ([$start, $end]);
sub {shift @middle_val}
},
sub { iter_hanoi($disks-1, $via, $end, $start) },
);
# Below here is boilerplate: if you've done the above steps right,
+ just plug
# this in, and it works. It returns the first iterator from the li
+st that
# returns anything.
# Grab and unwrap an iterator from the list
my $iter = (shift @sub_iter)->();
return sub {
my $rval;
$iter = (shift @sub_iter)->()
until ($rval = $iter->() or @sub_iter == 0);
return $rval;
}
}
To me, the parallel structure is beautiful and it's just about foolproof. Exhausted iterators are garbage-collected, and you don't have an or-chain to evaluate on every iteration.
sub iter_choose_n {
my $n = pop;
# Base cases get assigned to an array, which the iterator shifts t
+hrough
my @base_case = ([]);
return sub{ shift @base_case } if $n == 0 or $n > @_;
@base_case = (\@_);
return sub { shift @base_case } if $n == @_;
# otherwise..
my ($first, @rest) = @_;
my @sub_iter = (
sub {
my $recurse = iter_choose_n(@rest, $n-1);
my $set;
sub { ($set = $recurse->()) ? [$first, @$set]
+: () }
},
sub { iter_choose_n(@rest, $n) }
);
# Below here is boilerplate: if you've done the above steps right,
+ just plug
# this in, and it works. It returns the first iterator from the li
+st that
# returns anything.
# Grab and unwrap an iterator from the list
my $iter = (shift @sub_iter)->();
return sub {
my $rval;
$iter = (shift @sub_iter)->()
until ($rval = $iter->() or @sub_iter == 0);
return $rval;
}
}