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.

Answer 2

It might be possible with a Z, but for my poor little brain, zipping recursively generated lazy lists is too much.

Instead, I did some other simplifications:

sub generate($s, %eqs) {
    take $s;

    # the given equations normalize the string, ie there's no need to apply
    # the inverse relation
    for %eqs.kv -> $k, $v {
        # make copy of $s so we can use s/// instead of .subst
        my $t = $s;
        generate $t, %eqs
            if $t ~~ s/$k/$v/;
    }
}

sub table(@G, %eqs) {
    # compute the set only once instead of implicitly on each call to (elem)
    my $G = set @G;

    # some code golfing
    put ['', |@G]>>.fmt('%-5s|').join;
    put '-----|' x @G + 1;

    for @G -> $x {
        printf '%-5s|', $x;

        for @G -> $y {
            printf '%-5s|', (gather generate("$x$y", %eqs)).first(* (elem) $G);
        }

        put '';
    }    
}

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

# use double brackets so we can have empty strings
my %eqs = <<aa e   bbbb e   ba abbb   e ''>>;

table @G, %eqs;

---

Here is a compact rewrite of generate that does bidirectional substitution, still without an explicit zip:

sub generate($s, %eqs) {
    my @results = do for |%eqs.pairs, |%eqs.antipairs -> (:$key, :$value) {
        take $s.subst($key, $value) if $s ~~ /$key/;
    }

    my @seqs = @results.map: { gather generate($_, %eqs) }
    for 0..* -> $i { take .[$i] for @seqs }
}

Answer 3

Here's a version of generate that uses the approach demonstrated by smls:

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, $_) });

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

I've tested it and it works on exercises 2 and 3.

As smls mentions in his answer, zip doesn't do what we were expecting when the given array of arrays only contains a single array. So, let's make a version of zip which does work with one or more arrays:

sub zip-many (@arrs)
{
    if @arrs.elems == 1 { .take for @arrs[0][];     }
    else                { .take for flat [Z] @arrs; }
}

And now, generate in terms of zip-many:

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; }

    zip-many @results.map({ gather generate(%eqs, $_) });
}

That looks pretty good.

Thanks smls!

---

smls suggests in a comment below that zip-many not invoke take, leaving that to generate. Let's also move flat from zip-many to generate.

The slimmed down zip-many:

sub zip-many (@arrs) { @arrs == 1 ?? @arrs[0][] !! [Z] @arrs }

And the generate to go along with it:

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)); }
    }

    .take for @results;

    .take for flat zip-many @results.map({ gather generate(%eqs, $_) });
}

Answer 4

Testing the keys and values separately seems a bit silly; your strings aren't really regexes, so there's no need for // anywhere in your code.

sub generate($s, @eqs) {
    my @results = do for @eqs.kv -> $i, $equation {
        take $s.subst($equation, @eqs[ $i +^ 1 ]) if $s.index: $equation
    }

    my @seqs = @results.map: { gather generate($_, @eqs) }
    for 0..* -> $i { take .[$i] for @seqs }
}

Obviously with this version of generate you'll have to rewrite table to use @eqs instead of %eqs.