Beefy Boxes and Bandwidth Generously Provided by pair Networks
Perl Monk, Perl Meditation
 
PerlMonks  

Re: NestedLoops (Algorithm::Loops) and Iterators

by tmoertel (Chaplain)
on Jul 26, 2005 at 22:49 UTC ( #478394=note: print w/replies, xml ) Need Help??


in reply to NestedLoops (Algorithm::Loops) and Iterators

One way of looping over nested iterators is to combine them into a single iterator that loops over their Cartesian product. In A mini-language for sequences (part 1), I give the code for seq_prod, which does this for sequences, which are similar to iterators.

Assuming that your iterators wrap around upon exhaustion, it is easy to convert them into sequences. Then you can combine them with seq_prod and iterate over the resulting sequence. If you want to work with iterators, you can convert the resulting sequence back into an iterator, or you can write an iter_prod function and avoid sequences altogether. In the example code below, I will take the first route.

Let us say that iterators are defined as follows:

sub iter { my $vals = \@_; my $i = 0; sub { $i >= @$vals ? do { $i = 0; undef } : $vals->[$i++]; }; } sub enumerate_iter { local $Data::Dumper::Indent = 0; local $Data::Dumper::Terse = 1; my ($iter) = @_; my $i = 0; while (defined($_ = $iter->())) { printf "%2d: (%s)\n", $i++, Dumper($_); } print "\n"; } enumerate_iter( iter( qw[a b c] ) ); # 0: ('a') # 1: ('b') # 2: ('c')

Then, the following functions let us convert between iterators and sequences.

sub iter_to_seq { my ($iter) = @_; sub { my $val = $iter->(); defined $val ? ($val) : (); }; } sub seq_to_iter { my ($seq) = @_; sub { my @val = $seq->(); @val ? [@val] : undef; }; } enumerate_iter( seq_to_iter( iter_to_seq( iter( qw[a b c] ) ) ) ); # 0: (['a']) # 1: (['b']) # 2: (['c'])

Note that we wrap sequences with array references in order to convert them into iterators. (Thus the iterator-sequence-iterator round trip is not equivalent to an identity function.)

Finally, with the following functions, we can combine iterators as sequences and convert the resulting sequence back to an iterator. The iter_prod function encapsulates the entire process.

use List::Util qw( reduce ); sub seq_prod { no warnings 'once'; reduce { seq_prod2($a,$b) } @_ ; } sub seq_prod2 { my ($s, $t) = @_; my @sval; sub { my @tval; while ( !@sval || !(@tval = $t->()) ) { return () unless @sval = $s->(); } ( @sval, @tval ); }; } sub iter_prod { seq_to_iter( seq_prod( map iter_to_seq($_), @_ ) ); }

The following example shows how iter_prod works.

my $abcees = iter(qw(a b c)); my $xyzees = iter(qw(x y z)); enumerate_iter( iter_prod( $abcees, $xyzees ) ); # 0: (['a','x']) # 1: (['a','y']) # 2: (['a','z']) # 3: (['b','x']) # 4: (['b','y']) # 5: (['b','z']) # 6: (['c','x']) # 7: (['c','y']) # 8: (['c','z'])

Now you can replace your nested loops with a single loop over the iterator product.

my $product = iter_prod( $abcees, $xyzees ); while (defined (my $vals = $product->())) { my @vars = @$vals; print "Got vars: @vars\n"; # do real work here } # Got vars: a x # Got vars: a y # Got vars: a z # Got vars: b x # Got vars: b y # Got vars: b z # Got vars: c x # Got vars: c y # Got vars: c z

I hope this helps.

Cheers,
Tom

Replies are listed 'Best First'.
Re^2: NestedLoops (Algorithm::Loops) and Iterators
by ikegami (Patriarch) on Jul 26, 2005 at 23:35 UTC

    That's the same thing as:

    $iter_prod = NestedLoops([ sub { iter(qw(a b c) }, sub { iter(qw(x y z) }, ]);

    Wasn't the whole point to avoid flattening the iterator and to provide arbitrary nesting? Your solution flattens, and the depth is hardcoded as a sequence of calls to iter_prod.

    Note: NestedLoops's iterator returns an array rather than an array ref.

    Update: Your solution does support arbitrary depth:

    my $iter = do { my $done = 0; sub { $done++ ? undef : 1 } }; iter_prod($iter, ...) if ...; iter_prod($iter, ...) if ...;

    With NestedLoops, you'd do:

    my @iters; push(@iters, ...) if ...; push(@iters, ...) if ...;
      Can you define what you mean by "flattening" and "arbitrary depth"? My understanding of these things does not lead me to see unresolved problems in the original post. (Also, I do not believe that the NestedLoops code you provided is equivalent to seq_prod.)

      In the OP's example while loop, the iterator returns scalar values. Thus I don't see how the seq_prod of such iterators could "flatten" the results: there are no intermediate array results to flatten.

      On the arbitrary depth issue, if you mean that iter_prod works only for a fixed number of iterators, that is not the case. You can pass it any number of iterators, and (as long as they are independent) it will yield an iterator over their Cartesian product. If you mean something else, say that the Cartesian product is not what is desired, we can derive a suitable combinator to replace seq_prod2 and use it (with reduce) to build the desired output iterator. For example, we could define a combinator that takes the product of two iterators when the second is generated dynamically from the output of the first.

      Cheers,
      Tom

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://478394]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others studying the Monastery: (3)
As of 2022-11-29 05:42 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    Notices?