Recursive generator - manual zip vs operator

Question

Here's exercise 5.F.2 from 'A Book of Abstract Algebra' by Charles C Pinter:

Let G be the group {e, a, b, b^2, b^3, ab, ab^2, ab^3} whose generators satisfy a^2 = e, b^4 = e, ba = ab^3. Write the table of G. (G is called the dihedral group D4.)

Here's a little Perl 6 program which presents a solution:

sub generate(%eqs, $s)
{
    my @results = ();

    for %eqs.kv -> $key, $val {
        if $s ~~ /$key/ { @results.push($s.subst(/$key/, $val)); }
        if $s ~~ /$val/ { @results.push($s.subst(/$val/, $key)); }
    }

    for @results -> $result { take $result; }

    my @arrs = @results.map({ gather generate(%eqs, $_) });

    my $i = 0;

    while (1)
    {
        for @arrs -> @arr { take @arr[$i]; }

        $i++;
    }
}

sub table(@G, %eqs)
{
    printf "     |";   for @G -> $y { printf "%-5s|", $y; }; say '';

    printf "-----|";   for @G -> $y { printf "-----|";    }; say '';

    for @G -> $x {

        printf "%-5s|", $x;

        for @G -> $y {
            my $result = (gather generate(%eqs, "$x$y")).first(* (elem) @G);

            printf "%-5s|", $result;
        }
    say ''
    }    
}

# ----------------------------------------------------------------------

# Pinter 5.F.2

my @G = <e a b bb bbb ab abb abbb>;

my %eqs = <aa e   bbbb e   ba abbb>; %eqs<e> = '';

table @G, %eqs;

Here's what the resulting table looks like:

Let's focus on these particular lines from generate:

my @arrs = @results.map({ gather generate(%eqs, $_) });

my $i = 0;

while (1)
{
    for @arrs -> @arr { take @arr[$i]; }

    $i++;
}

A recursive call to generate is made for each of the items in @results. Then we're effectively performing a manual 'zip' on the resulting sequences. However, Perl 6 has zip and the Z operator.

Instead of the above lines, I'd like to do something like this:

for ([Z] @results.map({ gather generate(%eqs, $_) })).flat -> $elt { take $elt; }

So here's the full generate using Z:

sub generate(%eqs, $s)
{
    my @results = ();

    for %eqs.kv -> $key, $val {
        if $s ~~ /$key/ { @results.push($s.subst(/$key/, $val)); }
        if $s ~~ /$val/ { @results.push($s.subst(/$val/, $key)); }
    }

    for @results -> $result { take $result; }

    for ([Z] @results.map({ gather generate(%eqs, $_) })).flat -> $elt { take $elt; }
}

The issue with the Z version of generate is that it hangs...

So, my question is, is there a way to write generate in terms of Z?

Besides this core question, feel free to share alternative solutions to the exercise which explore and showcase Perl 6.

---

As another example, here's exercise 5.F.3 from the same book:

Let G be the group {e, a, b, b^2, b^3, ab, ab^2, ab^3} whose generators satisfy a^4 = e, a^2 = b^2, ba = ab^3. Write the table of G. (G is called the quaternion group.)

And the program above displaying the table:

---

As an aside, this program was converted from a version in C#. Here's how generate looks there using LINQ and a version of ZipMany courtesy of Eric Lippert.

    static IEnumerable<string> generate(Dictionary<string,string> eqs, string s)
    {
        var results = new List<string>();

        foreach (var elt in eqs)
        {
            if (new Regex(elt.Key).IsMatch(s))
                results.Add(new Regex(elt.Key).Replace(s, elt.Value, 1));

            if (new Regex(elt.Value).IsMatch(s))
                results.Add(new Regex(elt.Value).Replace(s, elt.Key, 1));
        }

        foreach (var result in results) yield return result;

        foreach (var elt in ZipMany(results.Select(elt => generate(eqs, elt)), elts => elts).SelectMany(elts => elts))
            yield return elt;
    }

The entire C# program: link.

Answer 1

Why your use of zip doesn't work

Your code assumes that [Z] ("reducing with the zip operator") can be used to get the transpose of a list-of-lists.

Unfortunately, this doesn't work in the general case.
It 'usually' works, but breaks on one edge case: Namely, when the list-of-lists is a list of exactly one list. Observe:

my @a = <a b c>, <1 2 3>, <X Y Z>; put [Z~] @a;  # a1X b2Y c3Z
my @b = <a b c>, <1 2 3>;          put [Z~] @b;  # a1 b2 c3
my @c = <a b c>,;                  put [Z~] @c;  # abc
my @d;                             put [Z~] @d;  # 

In the first two examples (3 and 2 sub-lists), you can see that the transpose of @a was returned just fine. The fourth example (0 sub-lists) does the right thing as well.

But the third example (1 sub-list) didn't print a b c as one would expect, i.e. it didn't return the transpose of @a in that case, but rather (it seems) the transpose of @a[0].

Sadly, this is not a Rakudo bug (in which case it could simply be fixed), but an unforseen interaction of two Perl 6 design decisions, namely:

• The reduce meta-operator [ ] handles an input list with a single element by calling the operator it's applied to with one argument (said element).
  In case you're wondering, an infix operator can be called with only one argument by invoking its function object: &infix:<Z>( <a b c>, ).
• The zip operator Z and function zip (like other built-ins that accept nested lists), follows the so-called "single-argument rule" – i.e. its signature uses a single-argument slurpy parameter. This means that when it is called with a single argument, it will descend into it and consider its elements the actual arguments to use. (See also Slurpy conventions.)
  So zip(<a b c>,) is treated as zip("a", "b", "c").

Both features provide some nice convenience in many other cases, but in this case their interaction regrettably poses a trap.

How to make it work with zip

You could check the number of elements of @arrs, and special-case the "exactly 1 sub-list" case:

my @arrs = @results.map({ gather generate(%eqs, $_) });

if @arrs.elems == 1 {
    .take for @arrs[0][];
}
else {
    .take for flat [Z] @arrs
}

The [] is a "zen slice" - it returns the list unchanged, but without the item container that the parent Array wrapped it in. This is needed because the for loop would consider anything wrapped in an item container as a single item and only do one iteration.

Of course, this if-else solution is not very elegant, which probably negates your reason for trying to use zip in the first place.

How to write the code more elegantly without zip

Refer to Christoph's answer.