Re^2: Recursively-generated Iterators

[Roy Johnson]

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):

1. Empty-set return values are replaced by empty subs
2. Explicit (non-recursing) return values are assigned to an array; the iterator will be a sub that shifts that array
3. A list of return values that includes recursive calls is replaced by a list of sub-wrapped iterators (wrapping the iterator calls in subs delays their evaluation), the iterator will be a sub that shifts its way through that list, unwrapping iterators until it finds one that returns something.
4. See the rewrite of iter_choose_n (at the end of this post) for what to do when you have to accumulate data with a recursive call, as choose_n does (but Hanoi doesn't).

That last is a little complicated to describe in words, so I'll demonstrate with Towers of Hanoi.

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.

Rewriting iter_choose_n to work with the boilerplate:

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