## Infinite work is less work

The first task of last week's Perl Weekly Challenge was to print the

first ten strong and weak primes. A prime *p _{n}* is "strong" if it's larger

than the average of its two neighbouring primes (

*i.e.*

*p*).

_{n}> (p_{n-1}+p_{n+1})/2A prime is "weak" if it's smaller than the average of its two neighbours.

Of course, this challenge would be trivial if we happened to have a list

of all the prime numbers. Then we'd just filter out the first ten that

are strong, and the first ten that are weak. In fact, it would be even

easier if we happened to have a list of all the strong primes, and a

list of all the weak ones. Then we'd just print the first ten of each.

But there are an infinite number of primes and of weak primes *(and
possibly of strong primes too, though that's still only conjectured)*,

so building a complete list of the various subspecies of primes

is impractical in most programming languages.

Yet another of the things I love about Perl 6 is how well it handles

infinite lists and sequences. Not having to worry about finite upper

limits simplifies a large number of tasks...and this is one of them.

The sequence of primes is just the sequence of positive integers,

filtered (with a `.grep`

) to keep only the ones that are prime.

And, of course, Perl 6 already has a prime number tester: the built-in

`&`

`is-``prime`

function. The sequence of primes never changes, so we can

declare it as a constant:

` constant p = [ (1..∞).grep( &`

`is-``prime ) ];`

Now we need to extract just the strong and weak primes.

Given the earlier definitions of "strong" and "weak",

we get:

` sub strong (\n) { n > 0 && p[n] > p[n-1, n+1].sum/2 }`

` sub weak (\n) { n > 0 && p[n] < p[n-1, n+1].sum/2 }`

Note that `p[n-1, n+1]`

is the list of `p[n]`

's two neighbours,

which we then add together (`.sum`

) and average (`/2`

).

These two strength tests operate on a prime's index, not its value,

so to generate the full lists of strong and weak primes, we need to

take those indices (`p.keys`

), filter them to keep only the ones that

are strong or weak (another `.grep`

) and then map each index

back to the corresponding prime.

Which gives us:

` constant strong-p = [ p.keys.grep(&strong).map(->\n { p[n] }) ];`

` `

` constant weak-p = [ p.keys.grep(&weak ).map(->\n { p[n] }) ];`

That works fine, but it's a little *clunky* to have to convert all the

primes (`p`

) back to indices (`.keys`

), and then later convert

each index back to the corresponding prime: `.map(->\n { p[n] })`

So, instead, we could convert each prime in `p`

to a key/value pair,

`grep`

through just the keys, and then `map`

out just the values.

Like so:

` constant strong-p = p`

**.pairs.grep(*.key.&strong).map(*.value)**;

` constant weak-p = p`

**.pairs.grep(*.key.&weak ).map(*.value)**;

...where `*.key.&strong`

is just a shorthand for: `-> \pair { strong( pair.key ) }`

In other words, filter out the pairs whose keys, when passed to `&strong`

, return `True`

.

Or, even more simply, we could filter and test the indices and values

in a single mapping, using more readable names for the current prime

and its index. Like so:

` constant strong-p = p`

**.kv.map: ->\n,\pₙ {pₙ if strong n}**;

` constant weak-p = p`

**.kv.map: ->\n,\pₙ {pₙ if weak n}**;

That is: take the infinite list of primes (`p`

) and convert it to an infinite list

of alternating *key-then-value* (`p.kv`

). For each such *index-then-prime*,

call the index `n`

and the prime `pₙ`

(`.map: ->\n,\pₙ`

),

then keep `pₙ`

only if it is of the appropriate strength

(`{pₙ if strong n}`

or `{pₙ if weak n}`

).

Whichever way we generate the infinite `strong-p`

and `weak-p`

lists,

printing the first ten of each is then trivial:

` say 'strong primes: ', strong-p[^10];`

` say 'weak primes: ', weak-p[^10];`

Note that in all the code shown above, all the `grep`

s and `map`

s work

lazily, on-demand, and just-in-time. Each `grep`

and `map`

only iterates

through as many list elements as are required to produce the value at

the index you actually query (in this case: the values at indices 0

to 9). So it takes no more work to operate on these infinite lists

than it would to use finite lists.

In fact, it generally takes *less* work.

If we preferred to work with only a finite list of primes, we'd need to

magically know in advance (*i.e.* guess) how many primes were required to

guarantee that our lists contain at least ten strong and ten weak primes.

For example, we might reasonably assume that the first 1000 integers

would probably contain at least 10 strong and 10 weak primes,

so we could try:

` constant p = [ (1..`

**1000**).grep(&`is-``prime) ];`

And, indeed, that would work fine. Except that we just did

about ten times as much work as was actually required.

Or we might have guessed a tighter upper limit instead:

` constant p = [ (1..`

**100**).grep(&`is-``prime) ];`

which would have eliminated all the extra work, but which only works by

a happy accident. The 10^{th} strong prime is 97, but to test its *strong*-ness

correctly we'd need the following prime (101) as well. However, as we stopped

generating primes at 100, the `&strong`

subroutine would have received an

undefined value when it requested that *n+1 ^{th}* prime. When used as a number,

that undefined value would convert to zero, so the average of 97's two prime

neighbours would be computed as (89+0)/2, which is certainly less than 97,

which would (erroneously, but correctly!) indicate that 97 is a strong prime.

That's not science; that's voodoo.

If we want to avoid the extra work of using an extremely conservative upper

limit *(and the risk of error if our notion of "extremely conservative" isn't
quite conservative enough)*, then we need another approach. We need

to iterate through successive integers, locating successive primes, and then

testing their strengths, until we're absolutely sure we have enough of each.

Which would look something like:

` # The various lists of primes are all initially empty...`

` my \p = [];`

` my \strong-p = [];`

` my \weak-p = [];`

` # The definitions of "strong" and "weak" (as before)...`

` sub strong (\n) { n > 0 && p[n] > p[n-1, n+1].sum/2 }`

` sub weak (\n) { n > 0 && p[n] < p[n-1, n+1].sum/2 }`

` # Try every integer i as a potential prime...`

` for 1..* -> \i {`

` # If it's actually prime...`

` if `

`is-``prime(i) {`

` # Add it to the list of known primes...`

` p.push(i);`

` # If there are enough known primes to test strengths...`

` if p.elems >= 3 {`

` # Can now test the second-last prime in the list...`

` my \n = p.end - 1;`

` # And add it to the appropriate list (if any)...`

` if strong(n) { strong-p.push( p[n] ) }`

` elsif weak(n) { weak-p.push( p[n] ) }`

` }`

` }`

` # Stop when we have at least 10 of each subspecies...`

` last if strong-p & weak-p >= 10;`

` }`

` # Print out the first ten of each...`

` say 'strong primes: ', strong-p[^10];`

` say 'weak primes: ', weak-p[^10];`

That works correctly, and does no unnecessary calculations.

But it was much harder to write and it will be much harder

to read (and to verify, and to maintain), compared with:

` # All the primes...`

` constant p = [ (1..∞).grep(&`

`is-``prime) ];`

` # The definitions of "strong" and "weak"...`

` sub strong (\n) { n > 0 && p[n] > p[n-1, n+1].sum/2 }`

` sub weak (\n) { n > 0 && p[n] < p[n-1, n+1].sum/2 }`

` # All the strong and weak primes...`

` constant strong-p = p.kv.map: ->\n,\pₙ {pₙ if strong n};`

` constant weak-p = p.kv.map: ->\n,\pₙ {pₙ if weak n};`

` # Print out the first ten...`

` say 'strong primes: ', strong-p[^10];`

` say 'weak primes: ', weak-p[^10];`

Oh, and this declarative version is also four times faster

than the iterative solution.

Which is why, in Perl 6, infinite work is often *less* work.

Damian

PS: Those of you who are already familiar with Perl might have noticed

the complete absence of sigiled variables (such as: `$n`

or `@p`

) in the

examples above. Of course, Perl 6 does have sigiled variables, but you

are not *required* to use them. You can use *sigilless variables* instead,

which are declared with a leading backslash:

` my `

**\p** = [];

` for 2..* -> `

**\i** {...}

` sub strong (`

**\n**) {...}

...and then used without any leading punctuation whatsoever:

` sub strong (\n) { `

**n** > 0 && **p**[**n**] >

**p**[**n**-1, **n**+1].sum/2 }

` if `

`is-``prime(`

**i**) {

` `

**p**.push(**i**);

` }`

So if the only thing that's been holding you back from

experimenting with this amazing new Perl dialect is your

~~pathological fear~~utterly rational dislike of punctuated variables,

maybe it's time to give Perl 6 a try after all?

## Leave a comment