I agree BrowserUK. ++tye for an incredible module! I missed the original discussions of A::L last year, but went back and read most of them last night after completely failing to understand the source for NestedLoops()! The prior posts were no help, so this is how I grok'd his code eventually.

I knew tye's approach was based on a closure as an iterator. Allright, I understand that, so I'll take what I understand and try to build it up to what NestedLoops() does...

sub make_iter { my @values = @_; my $idx = -1; return sub { # check if we are out of values, # return a value or undef if we're out return (++$idx > $#values) ? undef : $values[$idx]; } } my $iter = make_iter(3,4,6,7); print while( $_ = $iter->() );

Maybe that's a trivial example, but I understand it.

The crux of NestedLoops is it takes this trivial example to an arbitrary depth. Maybe I can do that, if I accept an AoA for my @values to iterate over. Then, use an array (@idx) for my old $idx value. And since the iterator returns multiple values, I'll have to store them in an array (@return), too. Finally, I need an index ($i) into my arrays, so I know where I'm currently working.

Let's make it work for just the "simplest" case of one set of values again (i.e. $i is always 0), then generalize.

sub make_iter_deeper { my @AoA = @_; my @idx; my $i = 0; # keeping it simple $idx[0] = -1; # same as $idx = -1 above; my @return; return sub { # if the index of the array i'm working in is # past the end of elements if ( ++$idx[$i] > $#{@{$AoA[$i]}} ) { return; } # if not, put the next element in the return value else { $return[$i] = $AoA[$i][$idx[$i]] } return @return; } } my $iter = make_iter_deeper([3,4,6,7]); print join(',',@_) . "\n" while( @_ = $iter->() );

The next step is to handle any number of lists to "nestedly" iterate over.

sub make_iter_deeperer { my @AoA = @_; my @idx; my $i = -1; $idx[0] = -1; my @return; return sub { # depth first to produce "nested" result behavior # if we aren't at the end of AoA's elements, go to # the next, reseting the next elements' index if( $i < $#AoA ) { $idx[++$i]= -1; } LOOP: { if ( ++$idx[$i] > $#{@{$AoA[$i]}} ) { # if the index of the array i'm working in is # past the end of elements it means we need to # go up a level and clear the last return value pop @return; # we may have finished everything return if --$i < 0; # we may have finished more than one # so check again redo LOOP; } # if not, put the next element in the return value else { $return[$i] = $AoA[$i][$idx[$i]] } } return @return; } }

Whew! Okay, I'll admit that I didn't come up with that last one all by myself--in fact, it was born of my examinations of tye's A::L::NestedLoops source. The important bit of which, is the subroutine _NL_iter. Let's take a look.

sub _NL_Iter { my( $loops, $code, $when )= @_; my @list; my $i= -1; my @idx; my @vals= @$loops; return sub { return } if ! @vals; return sub { while( 1 ) { # Prepare to append one more value: if( $i < $#$loops ) { $idx[++$i]= -1; if( isa( $loops->[$i], 'CODE' ) ) { local( $_ )= $list[-1]; $vals[$i]= $loops->[$i]->(@list); } } ## return if $i < 0; # Increment furthest value, chopping if done there: while( @{$vals[$i]} <= ++$idx[$i] ) { pop @list; return if --$i < 0; } $list[$i]= $vals[$i][$idx[$i]]; my $act; $act= !ref($when) ? $when : do { local( $_ )= $list[-1]; $when->(@list); }; return @list if $act; } }; }

Now, tye's function is chock-full of handy features and error-checking. If you can mentally strip that away, you'll find the iterators are identical.

If it weren't late on Saturday morning, I might go more into the usage and the features supported. But, tye's already said he's adding more, so maybe I'll wait until the next version! ;-)

++tye! Fantastic module!

--Solo
--
I think my eyes are getting better. Instead of a big dark blur, I see a big light blur.

In reply to A::L::NestedLoops walkthrough (was Re^3: Better algorithm than brute-force stack for combinatorial problems?) by Solo
in thread Better algorithm than brute-force stack for combinatorial problems? by Solo

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!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • 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, details, 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, summary, 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:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.