Efficient but elegant Cross-Product iterator ?

LanX has asked for the wisdom of the Perl Monks concerning the following question:

I'm trying to create an iterator which takes a list of subs and creates the cross product of the returned lists:

the expected result is

for my $x ( $sub_x->() ) {
    for my $y ( $sub_y->() ) {
         return [ $x,$y ];
    }
}
[download]

Please note that an iterator can be interrupted and resumed, and that the numbers of subs (=nesting levels) should be free.

Since function calls are expensive in Perl I tried to implement it as a big while loop instead of recursive calls.

Now I'm wondering if there is a more elegant or faster way to code this:

use 5.12.0;

use strict;
use warnings;
use Data::Dump qw/pp dd/;


my $DBG;

;;; # skipped

$DBG = 0;
my $i_cross = cross(
                    sub {"A".."B"},
                    sub {1..2},
                    sub {"a".."b"},
                   );


my $count = 4;

while ( my ($v) = $i_cross->() ) {
    warn  "*** First 5 RESULTs: ", pp $v;
    last unless $count--;
}

warn "stopped";

while ( my ($v) = $i_cross->() ) {
    warn  "*** Remaining RESULT: ", pp $v;
}


sub cross {
    my @stack  = @_;
    my $level  = 0;
    my @ranges = ();
    my @res;

    return sub {

        while ( $level >= 0 ) {

            my $ra_range = \ $ranges[$level];

            # ENTER LOOP
            unless (defined $$ra_range ) {
                $$ra_range = [ $stack[$level]->() ];
                warn "ENTER level=$level left \@ranges=" ,pp \@ranges 
+ if $DBG;
            }

            # LOOP OVER
            if ( @$$ra_range  ) {
                $res[$level] = shift @$$ra_range ;

                # deepest level?
                if ( $level == $#stack ) {
                    return [@res];
                }
                # go deeper
                else {
                    $level++;
                }

            }

            #EXIT LOOP:
            else {
                $level--;
                $$ra_range = undef;
            }

        }
        return;
    }
}
[download]

RESULT

*** First 5 RESULTs: ["A", 1, "a"] at d:/exp/iter/cross.pl line 92.
*** First 5 RESULTs: ["A", 1, "b"] at d:/exp/iter/cross.pl line 92.
*** First 5 RESULTs: ["A", 2, "a"] at d:/exp/iter/cross.pl line 92.
*** First 5 RESULTs: ["A", 2, "b"] at d:/exp/iter/cross.pl line 92.
*** First 5 RESULTs: ["B", 1, "a"] at d:/exp/iter/cross.pl line 92.
stopped at d:/exp/iter/cross.pl line 96.
*** Remaining RESULT: ["B", 1, "b"] at d:/exp/iter/cross.pl line 99.
*** Remaining RESULT: ["B", 2, "a"] at d:/exp/iter/cross.pl line 99.
*** Remaining RESULT: ["B", 2, "b"] at d:/exp/iter/cross.pl line 99.
[download]

(it's part of a bigger file, so don't worry about the line numbers)

Cheers Rolf
_{(addicted to the Perl Programming Language :)

Wikisyntax for the Monastery}

Comment on Efficient but elegant Cross-Product iterator ? Select or Download Code

Replies are listed 'Best First'.
Re: Efficient but elegant Cross-Product iterator ? by haukex (Archbishop) on Jun 20, 2020 at 16:39 UTC
My Algorithm::Odometer::Tiny has some code, in addition to a "See Also" section with quite a few references to other modules. If you want speed, `forsetproduct` from Math::Prime::Util or Set::Product::XS are probably going to be best.	[reply] [d/l]
Re^2: Efficient but elegant Cross-Product iterator ? by LanX (Saint) on Jun 20, 2020 at 17:23 UTC
Thanks! :) The code in Algorithm::Odometer::Tiny is indeed tiny, but loops over lists/arrays not subs. (like the other listed solutions) (my title Cross Product might be misleading though ... sorry) EDIT: I suppose though it is possible to re-init the arrays once one loop level is entered. I wasn't able to locate the code for "forsetproduct from Math::Prime::Util" but the docs say Our "forsetproduct" matches Set::Product in both high performance and functionality (that module's single function "product" in Set::Product is essentially identical to ours). But that's not a lazy iterator but returning a greedy list. Regarding Set::Product::XS , I'm more interested in PP solutions. Cheers Rolf _{(addicted to the Perl Programming Language :) Wikisyntax for the Monastery} update On a side note, if you want to create a string from the product, consider using the glob-iterator `DB<65> p "$_\n" while <"{1,2,3}:{a,b,c}"> 1:a 1:b 1:c 2:a 2:b 2:c 3:a 3:b 3:c` [download]	[reply] [d/l]
Re^3: Efficient but elegant Cross-Product iterator ? (updated) by haukex (Archbishop) on Jun 21, 2020 at 09:56 UTC
The code in Algorithm::Odometer::Tiny is indeed tiny, but loops over lists/arrays not subs. (like the other listed solutions) Well, part of the idea of the module was to have the code small and simple enough so that it can be copy & pasted into other code. This simple patch allows you to produce your expected output from your shown input: `croak "no wheels specified" unless @_; - my @w = map { [ 1, ref eq 'ARRAY' ? @$_ : $_ ] } @_; + my @w = map { [ 1, ref eq 'CODE' ? $_->() : $_ ] } @_; my $done;` [download] You can of course do the same kind of mapping simply before calling the sub, as in `odometer( map { ref eq 'CODE' ? [$_->()] : $_ } ... )`, that'd allow you to use the other modules as well. Of course, it's a different story if the `sub`s passed to the function are to be called as iterators themselves? Update: That'd look something like this: `sub odometer { die "no wheels specified" unless @_; my @w = map { [ $_, $_->() ] } @_; my $done; return sub { if ($done) { $done=0; return } my @cur = map { $_->[1] } @w; for ( my $i=$#w; $i>=0; $i-- ) { defined( $w[$i][1] = $w[$i][0]->() ) and last; $w[$i][1] = $w[$i][0]->(); $done=1 unless $i; } return wantarray ? @cur : join '', map {defined()?$_:''} @cur; }; }` [download] Read more... test code (1442 Bytes)	[reply] [d/l] [select]
Re^4: Efficient but elegant Cross-Product iterator ? (updated) by LanX (Saint) on Jun 21, 2020 at 16:55 UTC
Re^5: Efficient but elegant Cross-Product iterator ? (updated) by haukex (Archbishop) on Jun 21, 2020 at 19:10 UTC
Some notes below your chosen depth have not been shown here
Re: Efficient but elegant Cross-Product iterator ? by Corion (Patriarch) on Jun 20, 2020 at 19:50 UTC
I'm not sure from your description, but what you want sounds very much like Algorithm::Loops::NestedLoops, which takes subroutines to create loops and nests those to create the data structure (as another iterator).	[reply]
Re^2: Efficient but elegant Cross-Product iterator ? by LanX (Saint) on Jun 20, 2020 at 21:22 UTC
Thanks, pretty close but not exactly what I'm trying to achieve in the end. Some interesting ideas though. The code looks like written by an experienced C programmer.° ;) One point with "when" looks buggy, will need to install and test. Didn't know it's possible to use `isa` instead of `ref` to test for a CODE ref (?) Strange! Cheers Rolf _{(addicted to the Perl Programming Language :) Wikisyntax for the Monastery} °) hey Tye, where are you? :)	[reply]
Re: Efficient but elegant Cross-Product iterator ? by ikegami (Patriarch) on Jun 20, 2020 at 21:36 UTC
That's exactly what Algorithm::Loops's `NestedLoop` does. `use Algorithm::Loops qw( NestedLoop ); my $iter = NestedLoop([ map { [ $_->() ] } @subs ]); while ( my @items = $iter->() ) { ... }` [download] Update: LanX points out the above can be simplified if the subs return the same thing each time they are called. They also need to return the values via a reference to an array. `use Algorithm::Loops qw( NestedLoop ); my $iter = NestedLoop(\@subs); while ( my @items = $iter->() ) { ... }` [download]	[reply] [d/l] [select]
Re^2: Efficient but elegant Cross-Product iterator ? by LanX (Saint) on Jun 20, 2020 at 21:44 UTC
Almost, instead of code refs, you are expanding the subs to arrays before passing them. For this simplified example the result is the same though. Cheers Rolf _{(addicted to the Perl Programming Language :) Wikisyntax for the Monastery}	[reply]
Re^3: Efficient but elegant Cross-Product iterator ? by ikegami (Patriarch) on Jun 20, 2020 at 21:59 UTC
Well yeah. You necessarily need to store the results of the subs somewhere, and in what else would store the results of the subs but in arrays?	[reply]
Re^4: Efficient but elegant Cross-Product iterator ? by LanX (Saint) on Jun 20, 2020 at 22:00 UTC
Re^5: Efficient but elegant Cross-Product iterator ? by ikegami (Patriarch) on Jun 20, 2020 at 22:05 UTC
Some notes below your chosen depth have not been shown here
Re: Efficient but elegant Cross-Product iterator ? by perlfan (Parson) on Jun 22, 2020 at 06:15 UTC
I am sure whatever you end up doing, PDL will make things a little easier for you.	[reply]
Re^2: Efficient but elegant Cross-Product iterator ? by etj (Priest) on Apr 21, 2022 at 08:20 UTC
The thing PDL is best for is rectangular, in-memory data. Then you can achieve incredibly terse, powerful, fast-running code. Iterators are a bit of a roadblock to this, though with sufficient "chunking" to read blocks of data and processing those (if the application allows), it may still be possible. If you want to work with gigantic data that sufficiently appears "in-memory", there's memory-mapping with PDL::IO::FastRaw.	[reply]

update