Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Recursive generator - manual zip vs operator

Tags:

raku

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:

enter image description here

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...

enter image description here

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:

enter image description here


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.

like image 346
dharmatech Avatar asked Jun 29 '17 09:06

dharmatech


People also ask

What is the use of ZIP () operator in RxJava?

RxJava Parallelization Concurrency : Zip () Operator. Often zip () operator is misunderstood when it comes to parallelism. Think of a situation when you have multiple http request and combine the result in one, it actually happens Sequentially instead of Parallel. Zip operator is used to combine emission from multiple observable into ...

Do Python generators improve recursion memory?

In this (relatively short) article, we will look at Python's generators, and use them to improve the memory usage of recursive code. You know what recursion is.

Is ZIP () operator parallelism?

Often zip () operator is misunderstood when it comes to parallelism. Think of a situation when you have multiple http request and combine the result in one, it actually happens Sequentially instead of Parallel.

What are some examples of recursive logic?

The truth is that some logic is inherently recursive. A good example is printing out all the paths inside a folder, like what the find command does. Here's the source code for one of my projects: And its workings are fairly simple. Here's how you print all contents of a folder: Get all the things immediately inside the folder.


1 Answers

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 @a = <a b c>, <1 2 3>;          put [Z~] @a;  # a1 b2 c3
my @a = <a b c>,;                  put [Z~] @a;  # abc
my @a;                             put [Z~] @a;  # 

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.

like image 158
smls Avatar answered Oct 22 '22 20:10

smls