good chemistry is complicated,and a little bit messy -LW PerlMonks

Comment on

 ( #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":

• Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
• Read Where should I post X? if you're not absolutely sure you're posting in the right place.
• Please read these before you post! —
• Posts may use any of the Perl Monks Approved HTML tags:
a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
• You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
 For: Use: & & < < > > [ [ ] ]
• Link using PerlMonks shortcuts! What shortcuts can I use for linking?
• See Writeup Formatting Tips and other pages linked from there for more info.

Create A New User
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others examining the Monastery: (23)
As of 2015-08-28 14:22 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?