Posts Tagged ‘operators’

Day 6 – The X and Z metaoperators

December 6, 2010

One of the new ideas in Perl 6 is the metaoperator, an operator which combines with an ordinary operator in order to change its behaviour. There are several of them, but in this post we will concentrate on just two of them: X and Z.

The X operator is one you might already have seen in its ordinary role as the infix cross operator. It combines lists together, one element from each, in every combination:

> say ((1, 2) X ('a', 'b')).perl
((1, "a"), (1, "b"), (2, "a"), (2, "b"))

However, this infix:<X> operator is actually just a shorthand for the X metaoperator applied to the list concatenation operator infix:<,>. Indeed, you’re perfectly at liberty to write

> say ((1, 2) X, (10, 11)).perl
((1, 10), (1, 11), (2, 10), (2, 11))

If you like. So what happens if you apply X to a different infix operator? How about infix:<+>

> say ((1, 2) X+ (10, 11)).perl
(11, 12, 12, 13)

What’s it done? Instead of creating a list of all the elements picked for each combination, the operator applies the addition infix to them, and the result is not a list but a single number, the sum of all the elements in that combination.

This works for any infix operator you care to use. How about string concatenation, infix:<~>?

> say ((1, 2) X~ (10, 11)).perl
("110", "111", "210", "211")

Or perhaps the numeric equality operator infix:<==>?

> say ((1, 2) X== (1, 1)).perl
(Bool::True, Bool::True, Bool::False, Bool::False)

But this post is also meant to be about the Z metaoperator. We expect you may have already figured out what it does, if you’ve encountered the infix:<Z> operator before, which is of course just a shortcut for Z,. If a Haskell programmer understands infix:<Z> as being like the zip function, then the Z metaoperator is like zipWith.

> say ((1, 2) Z, (3, 4)).perl
((1, 3), (2, 4))
> say ((1, 2) Z+ (3, 4)).perl
(4, 6)
> say ((1, 2) Z== (1, 1)).perl
(Bool::True, Bool::False)

Z, then, operates on each element of each list in turn, working on the first elements together, then the second, then the third for however many there are. It stops when it reaches the end of a list regardless of which side that list is on.

Z is also lazy, so you can apply it to two infinite lists and it will only generate as many results as you need. X can only handle an infinite list on the left, otherwise it would never manage to get anywhere at all.

At the time of writing, Rakudo appears to suffer from a bug where infix:<Z> and infix:<Z,> are not identical: the former produces a flattened result list. S03 shows that the behaviour of the latter is correct.

These metaoperators, then, become powerful tools for performing operations encompassing the individual elements of multiple lists, whether those elements are associated in some way based on their indexes as with Z, or whether you just want to examine all possible combinations with X.

Got a list of keys and values and you want to make a hash? Easy!

my %hash = @keys Z=> @values;

Or perhaps you want to iterate over two lists in parallel?

for @a Z @b -> $a, $b { ... }

Or three?

for @a Z @b Z @c -> $a, $b, $c { ... }

Or maybe you want to find out all the possible totals you could get from rolling three ten-sided dice:

my @d10 = 1 ... 10;
my @scores = (@d10 X+ @d10) X+ @d10;

If you want to see some real-world use of these metaoperators, Sudoku.pm in Moritz Lenz’s Sudoku solver.

Day 4 – The Sequence Operators

December 4, 2010

Last year, there was a brief tease of the sequence operator (tweaked slightly to be correct after a year’s worth of changes to the spec):

my @even-numbers  := 0, 2 ... *;    # arithmetic seq
my @odd-numbers   := 1, 3 ... *;
my @powers-of-two := 1, 2, 4 ... *; # geometric seq

This now works in Rakudo:

> my @powers-of-two := 1, 2, 4 ... *; 1;
1
> @powers-of-two[^10]
1 2 4 8 16 32 64 128 256 512

(Note: All the code examples in this post have been run in Rakudo’s REPL, which you can reach by running the perl6 executable with no command line arguments. Lines that start with > I what I typed; the other lines are Rakudo’s response, which is generally the value of the last expression in the line. Because the variable @powers-of-two is an infinite lazy list, I’ve added 1; at the end of the line, so the REPL prints that instead of going into an infinite loop.)

We need to trim the infinite list so that Rakudo doesn’t spend an infinitely long time calculating it. In this case, I used [^10], which is a quick way of saying “Give me the first ten elements.” (Note that when you bind a lazy list to an array variable like this, values which have been calculated are remembered; it’s a quick form of memoization.)

The sequence operator ... is a very powerful tool for generating lazy lists. The above examples just start to hint at what it can do. Given one number, it just starts counting up from that number (unless the terminal end of the sequence is a lower number, in which case it counts down). Given two numbers to start a sequence, it will treat it as an arithmetic sequence, adding the difference between those first two numbers to the last number generated to generate the next one. Given three numbers, it checks to see if they represent the start of an arithmetic or a geometric sequence, and will continue it.

Of course, many interesting sequences are neither arithmetic nor geometric, in which case you need to explicitly provide the sub to generate the next number in the sequence:

> my @Fibonacci := 0, 1, -> $a, $b { $a + $b } ... *; 1;
1
> @Fibonacci[^10]
0 1 1 2 3 5 8 13 21 34

The -> $a, $b { $a + $b } there is a pointy block (ie a lambda function) which takes two arguments and returns their sum. The sequence operator figures out how many arguments the block takes, and passes the needed arguments from the end of the sequence so far to generate the next number in the sequence. And so on, forever.

Or not forever. So far all these examples have had the Whatever star on the right hand side, which means “There is no terminating condition.” If you instead have a number there, the list will terminate when that number is exactly reached.

> 1, 1.1 ... 2
1 1.1 1.2 1.3 1.4 1.5 1.6 1.7 1.8 1.9 2
> 1, 1.1 ... 2.01
... Rakudo spins its wheels, because this is an infinite list ...
> (1, 1.1 ... 2.01)[^14]
1 1.1 1.2 1.3 1.4 1.5 1.6 1.7 1.8 1.9 2 2.1 2.2 2.3

The first one of those terminates naturally, but the second one missed the terminator and kept right on going. The result is an infinite list, so I limited it to the first 14 elements so that we could see what it was doing.

Those of you with backgrounds doing floating point math are probably sputtering about the dangers of assuming that adding .1 repeatedly will add up to exactly 2. In Perl 6, that’s not quite such an issue because it will use Rat (ie fractional) math where possible. But the general point is still very solid. If I want to find all the Fibonacci numbers below 10000, needing to know exactly the number to stop on is a big hassle. Luckily, just as you can use a block to specify how to generate the next element in a sequence, you can also use one to test to see whether the sequence should end yet:

> 0, 1, -> $a, $b { $a + $b } ... -> $a { $a > 10000 };
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946

The pointy block -> $a { $a > 10000 } creates a block which takes one argument, and returns true when that argument is greater than 10000; just the test we want.

Except we were looking for all the Fibonacci less than 10000. We generated that plus the first Fibonacci number greater than 10000. When passed a block as a termination test, the sequence operator returns all its elements until that block returns true, then it returns that last element and stops. But there is alternative form of the sequence operator that will do the trick:

> 0, 1, -> $a, $b { $a + $b } ...^ -> $a { $a > 10000 };
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765

Switching from ... to ...^ means the resulting list does not include the first element for which the termination test returned true.

Two side notes on this. This is actually a long-winded way of specifying these sequences in Perl 6. I don’t have space to explain Whatever Closures here, but this post from last year talks about them. Using them, you can rewrite that last sequence as

> 0, 1, * + * ...^ * > 10000;
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765

It’s up to you whether or not you think this is clearer; there’s more than one way to do it.

Also, the left-hand-side of the sequence operator can be any list, even lazy ones. This means you can easily use a terminating block to get a limited portion of an existing lazy list:

> my @Fibonacci := 0, 1, * + * ... *; 1;
1
> @Fibonacci ...^ * > 10000
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765
> @Fibonacci[30]
832040

(I stuck the last check there just to demonstrate that @Fibonacci still goes on past 10000.)

This only begins to scratch the surface of what sequences can do. For more information, see “List infix precedence” in the spec, and scroll down to the sequence operator. (Though note that it is still not completely implemented! It is an extremely complex operator.)

One particular twist I’d like to leave you with: the sequence operator is not constrained to working with numeric values. If you explicitly specify your own generator, you can make a sequence out of any type at all. But I’d like to leave that for a future Advent present…


Follow

Get every new post delivered to your Inbox.

Join 36 other followers