Darren Duncan (Rosetta author) asked on a p6 mailing-list if there would be a standard function to sort of 'cross join' data. I wanted to exercise my perl6 skills with a stab at it. 
(quoted from Darren)

One thing I would like to be able to do is this:

  @baz = cross([1,2],[3,4]); # yields ([1,3],[1,4],[2,3],[2,4])

And alternately, this:

  for cross([1,2],[3,4]) -> $foo,$bar { ... } # loop has 4 iterations

More examples:

  cross() # yields ()
  cross([],[1]) # yields ()
  cross([1,2]) # yields ([1],[2])
  cross([1,2],[3]); # yields ([1,3],[2,3])
  cross([1],[2],[3]) # yields ([1,2,3])
  cross([1],[2],[3,4]) # yields ([1,2,3],[1,2,4])

[download]

Warning: Perl6 code ahead.

sub cross {
    my @list = @_.reverse or return;
    gather {
        my $count = [*] 1, @_.map:{ .elems };
        for 0 .. $count - 1 -> $idx is copy {
            take [
                @_.map:{ ($idx, my $elem) = divmod($idx, .elems); .[$e
+lem] }
            ].reverse;
        }
    }
}

[download]
Update: the default 1 goes first, I guess

Replies are listed 'Best First'.
Re: cross combinations
by Perl Mouse (Chaplain) on Oct 28, 2005 at 09:52 UTC
    In Perl5, it only takes four lines: 
    sub cross {
    my $f = shift or return;                  # Nothing.
    @_ or return map {[$_]} @{$f};            # Handle one argument.
    my @r = cross(@_);                        # Recurse.
    map {my $l = $_; map {[$l, @$_]} @r} @$f; # Distribute.
}

    [download]
    However, I think that the cross product of nothing should be the empty set ([]), which would make the function even simpler as it loses a special case: 
    sub cross {
    my $f = shift or return [];               # Nothing.    
    my @r = cross(@_);                        # Recurse.
    map {my $l = $_; map {[$l, @$_]} @r} @$f; # Distribute.
}

    [download]
    Perl --((8:>*
[reply]
[d/l]
[select]

      You can code the exact same thing in the same number of lines in p6. That was not the real point though. I don't think anyone was golfing. The p6 solution above has something yours doesn't, take and gather. By default (at least last week ;) ) take and gather are lazy.

      sub cross (*$f, *@a) {
    return unless $f;
    @a or return @{$f}.map:{[$_]} ;            # Handle one argument.
    my @r = cross(@a);                        # Recurse.
    @$f.map:{my $l = $_ ; @r.map:{[$l, @$_]} }; # Distribute.
}

cross().perl.say;
cross([],[1]).perl.say;
cross([1,2]).perl.say;
cross([1,2],[3]).perl.say;
cross([1],[2],[3]).perl.say;
cross([1],[2],[3,4]).perl.say;

      [download]

      ___________
      Eric Hodges $_='y==QAe=e?y==QG@>@?iy==QVq?f?=a@iG?=QQ=Q?9'; s/(.)/ord($1)-50/eigs;tr/6123457/- \/|\\\_\n/;print;
[reply]
[d/l]
        The p6 solution above has something yours doesn't, take and gather. By default (at least last week ;) ) take and gather are lazy.
        Sure, take and gather are lazy. But since you need the entire list anyway, it doesn't really matter, does it? Lazy lists are nice if you don't need the entire thing - if you need the entire thing, it hardly matters.

        I still don't see the point of the various Perl6 solutions. The solution you present above doesn't have any benefits of the Perl5 solution - it just uses a different syntax, not even syntax that's significantly shorter, or easier to understand (it isn't harder or longer either - just different). It doesn't score on the "see how much easier this problem is in perl6" scale.

        Perl --((8:>*
[reply]

      Cool solution -- but the original isn't recursive, so I'm not sure this is quite apples to oranges for comparing length.

      For the OP, I'm curious to know what about Perl6 makes this easier than Perl5. Or is that the point? Is the point just to play with perl6's new syntax?

      -xdg

      Code written by xdg and posted on PerlMonks is public domain. It is provided as is with no warranties, express or implied, of any kind. Posted code may not have been tested. Use of posted code is at your own risk.

[reply]
        Oh, there's a three line non-recursive solution as well, using the same algorithm (as the recursive solution). I just find recursion much easier. 
        sub cross {
    my @r = [];
    @r = map {my $l = $_; map {[@$_, $l]} @r} @$_ for @_;
    @r;
}

        [download]
        What I don't understand about the Perl6 solution is the need to count how many elements will be returned.
        Perl --((8:>*
[reply]
[d/l]
Re: cross combinations (lazy)
by tye (Sage) on Oct 28, 2005 at 13:43 UTC

    I'd hope that such things were lazy in Perl6. Doing combinatorial things by allocating them all in memory at once mostly sucks. In Perl5 I'd write an iterator. I'd hope Perl6 would support taking a list of lazy lists and "returning" a lazy list of lists (being able to take a lazy list of lazy lists and returning a lazy list of lazy lists would be even cooler).

    - tye        

[reply]
      I'd hope that such things were lazy in Perl6.

      As eric256 pointed out in Re^2: cross combinations, gather and take are indeed lazy in Perl 6. Some folks are angling to get that redacted as the default, but they also recognize how useful it will be in many cases, so their proposals include a simple, convenient way to turn laziness back on. In either event, I think the answer will be Yes. :-)

[reply]
[d/l]
[select]

        Surely, precalculating the count of items to be returned defeats much of the point of being lazy?

        - tye        

[reply]
Re: cross combinations
by chas (Priest) on Oct 29, 2005 at 06:31 UTC
    Just a remark: It has been discussed on PM in the past that the glob function will do most of the work in forming a cartesian product (I don't remember exactly where, though...) So, for example, 
    @a=map {split //} glob "{1,2}{3,4}";
while(@a){$x=shift @a;$y=shift @a;print "{$x,$y} "};

    [download]
    and you can clearly write functions like "cross" by formatting the output to taste.
    (Not that this is more efficient than other solutions presented...probably isn't.)
    chas
[reply]
[d/l]
Re: cross combinations
by Courage (Parson) on Nov 02, 2005 at 18:33 UTC
    I beleive Perl6's solution could be as concise and lazy as Haskell's one: 
    [(x,y)|x<-[1,2],y<-[3,4]]

    [download]
    ... reesults in (when running in GHCi) 
    [(1,3),(1,4),(2,3),(2,4)]

    [download]
[reply]
[d/l]
[select]

Back to Meditations