Front page | perl.perl6.language | Postings from April 2003

## Re: Ruminating RFC 93- alphabet-blind pattern matching

From:
Austin Hastings
Date:
April 3, 2003 16:10
Subject:
Re: Ruminating RFC 93- alphabet-blind pattern matching
Message ID:
20030404001050.49034.qmail@web12302.mail.yahoo.com
```This is a big long post containing essentially me scratching my head at
Luke's code. Since Uri asked yesterday for a tutorial-type explanation
of some of the syntax, and since I wanted to scream and ask the same
thing of Luke today when I first read his "5 unobfuscated friggin
lines", I'm putting it on the list. But chances are you already know
the answers to all the questions I'm asking, and can skip this post
safely.

--- Luke Palmer <fibonaci@babylonia.flatirons.org> wrote:
> > On Thu, Apr 03, 2003 at 07:29:37AM -0800, Austin Hastings wrote:
> > >This has been alluded to before.
> > >
> > >What would /A*B*/ produce?
> > >
> > >Because if you were just processing the rex, I think you'd have to
> > >finish generating all possibilities of A* before you began
> iterating
> > >over B*...
> >
> > The "proper" way would be to first produce all possibilities of
> length n
> > before giving any possibility of length n+1.
> >
> > ''
> > 'A'
> > 'B'
> > 'AA'
> > 'AB'
> > 'BB'
> > 'AAA'
> > 'AAB'
> > ...
> >
> > I haven't spent a milisecond of working out whether that's feasible
> to
> > implement, but from a theoretical POV it seems like the solution.
>
> Well, I'm not certain there is really a "proper" way.  But sure, your
> way is doable.
>
>     use Permutations <<permutations compositions>>;
>
>     # Generate all strings of length \$n
>     method Rule::Group::generate(Int \$n) {  # Type sprinkles :)
>         compositions(\$n, +@.atoms) ==> map {
>             my @rets = map {
>                 \$^atom.generate(\$^n)
>             } zip(@.atoms, \$_);
>             *permutations(*@rets)
>         }
>     }
>
> How's that for A4 and A6 in a nutshell, implementing an A5 conept? :)
> I hope I got it right....
>
> Provided each other kind of rx element implemented generate, that
> returned all generated strings of length \$n, which might be zero.
> This would be trivial for most other atoms and ops (I think).
>
> Oh, compositions(\$a,\$b) is a function that returns all lists of
> length
> \$b whose elements sum to \$a.  Yes, it exists.
>

Pardon my ignorance, here:

For the example:  /(A*B*(C*|Z+))/.generate(4)

>         compositions(\$n, +@.atoms) ==> map {

This C< +@.atoms > is supposed to compute the length of the @.atoms
member-array, right? So that you can call "compositions(\$a,\$b)" with
two numbers?

compositions(4,3) = [
[0, 0, 4],
[0, 1, 3],
[0, 2, 2],
:
[4, 0, 0]
]

right?

And then map passes each of the 3-tuples, above, to the block as \$_.

>             my @rets = map {
>                 \$^atom.generate(\$^n)
>             } zip(@.atoms, \$_);
>             *permutations(*@rets)

And the block is going to take the @.atoms array, which has (in my
example) three members: A*, B*, and (C*|Z+); and the 3-tuple, and pair
each @.atom with a number from the 3-tuple in \$_ via the zip function.

A* => 1, B* => 2, (C*|Z+) => 1,

And map will run A*.generate(1), B*.generate(2), (C*|Z+).generate(1)
because the ^atom and ^n are alphabetically the first and second
arguments. (Note: I had thought that currying was limited to one-char
names, but I can't find anything right now about it...I like multichar
names better [as in this example], but it's going to take a lot of
practice to learn to watch out for that '^'.)

And then presumably the results would be:

A* => [ 'A' ]              # Array of one, for compatibility (below)
B* => [ 'BB' ]             # ditto
(C*|Z+) => [ 'C', 'Z' ]

>
>     \$^atom.generate(\$^n)
>
> I want @rets to be an array of array refs.  Do I have to explicitly
> take the reference of that, or does that work by itself?

I get the impression that if you don't flatten or append the results,
you'll get the reference automatically.

Continuing:

my @rets = [ ['A'], ['BB'], ['C', 'Z'] ]

When you say

>             *permutations(*@rets)

The *@rets is supposed to flatten the array once, right? So that the
effect was as if you had stripped off the outer [ ... ] above.

And permutations presumably iterates over each possible setting for
each independent argument.

sub permutations(?@arg1, *@rest)
{
@arg1 ==> map -> \$arg {
map { \$arg, *\$_ } permutations(@rest);
};     # <-- Is the semicolon needed?
}

Which should generate
[   ['A', 'BB', 'C', ]   ,    ['A', 'BB', 'Z', ]  ]

and then strip off the [ , ] because of the * in *permutations,
yielding the list.

The final strippage is because the *permutations() is making up only a
single component of the product of the map output, right? In order to
get

[ ['CCCC'], ..., [ 'A', 'BB', 'C', ], ['A', 'BB', 'Z'], ... ]

you flatten once to "glue" them together?

>     zip(@.atoms, \$_)
>
> I want the array ref in \$_ to be zipped up with @.atoms as if \$_ were
> a real array.  If this I<is> correct, am I allowed to say:
>
>     zip(@.atoms, @\$_)
>
> for documentation?

>
> Also, related to the first question:
>
>     *permutations(*@rets)
>
> Does that interpolate the returned list from permutations right into
> the map's return, a la Perl5?  Do I need the * ?
>

I talked myself into believing it, above.

> Wow, 5 unobfuscated friggin lines!  This language is gorgeous!

In a scary kind of way, yes.

>
> Luke

=Austin

```