Day 4 – The Sequence Operators

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 676

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…