Beefy Boxes and Bandwidth Generously Provided by pair Networks
Come for the quick hacks, stay for the epiphanies.
 
PerlMonks  

comment on

( [id://3333]=superdoc: print w/replies, xml ) Need Help??
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; } }

Caution: Contents may have been coded under pressure.

In reply to Re^2: Recursively-generated Iterators by Roy Johnson
in thread Recursively-generated Iterators by Roy Johnson

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post; it's "PerlMonks-approved HTML":



  • 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.
Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others pondering the Monastery: (4)
As of 2024-03-28 16:41 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found