Cartesian Product of two Strings

Question

I am trying to write a function in Perl that computes the cross product (cartesian product) of two Strings. I have similar code in Python that looks like this:

def cross(A, B):
    "Cross product of elements in A and elements in B."
    return [a+b for a in A for b in B]

How could I mimic this list comprehension in an elegant way?

Here is what I have so far:

# compute the cross product of two Strings 
# cross('12','AB') = ((1,A), (1,B), (2,A), (2,B))
sub cross {
    # unpack strings
    my ($A, $B) = @_;

    # array to hold products 
    my @out_array;

    # split strings into arrays
    my @A_array = split(//, $A);
    my @B_array = split(//, $B);

    # glue the characters together and append to output array
    for my $r (@A_array) {
        for my $c (@B_array) {
            push @out_array, [$r . $c];
        }
    } 

    return \@out_array;
}

This isn't working exactly as I would expect, for some reason a reference is coming back from split() instead of a List.

Any suggestions or other more elegant cartesian product solutions would be appreciated.

Answer 1

Your problem is in this part:

push @out_array, [$r . $c];

$r . $c concatenates the two scalars to a string. [EXPR] creates an array reference. You don't want a reference, just plain strings:

push @out_array, $r . $c;

---

If you don't like push, but syntactic sugar, you can use a module that implements gather/take:

my @cross = gather {
  for my $x (@A) {
    for my $y (@B) {
      take $x . $y;
    }
  }
};

This is implemented e.g. by List::Gather or Syntax::Keyword::Gather.

I myself am fond of elaborate map expressions:

my @cross = map { my $x = $_; map $x.$_, @B } @A;

(same as for with push for all practical purposes).

---

Note: Perl does not have a concept of “characters” that is related to arrays. When single characters are needed, these are modelled by strings of length 1. Perl arrays always contain scalars, but for (memory) performance reasons strings are not implemented as Perl arrays, but as a pointer to a C array (of known length). The downside is different sets of operations for strings and arrays, the upside is less memory usage.

As characters are just very short strings, to join them we use standard string concatenation with ..