Coding with an even fuller toolset

Sigh. It's always the way, isn't it?

You no sooner get done writing about how having the right tools can make a particular coding task trivially easy...when you realize that, right next door, there was a much better example you could have used to make exactly the same point.

The "longest initial subpath" example I talked about in my previous post was challenge #2 of last week's Perl Weekly Challenge. But challenge #1 that week makes it even clearer how much the right tool can simplify a task.

Challenge #1 was to find the smallest Euclid number that isn't a prime. The Nth Euclid number is given by the product of the first N primes, plus one. So the sequence of Euclid numbers is:

(2)+1, (2*3)+1, (2*3*5)+1, (2*3*5*7)+1, (2*3*5*7*11)+1, ...

This sequence would be simple to compute, if only there was an easy way to build a sequence of the partial products of another list (e.g. the partial products of the prime numbers):

(2), (2*3), (2*3*5), (2*3*5*7), (2*3*5*7*11), ...

And, of course, Perl 6 has just such a tool...built right into the core language.
It's called the triangular reduction metaoperator.

An ordinary reduction operator in Perl 6 (such as [*]):

$product = [*] @nums;

inserts the bracketed operator between every two elements of the list,
as if it had been written:

$product = @nums[0] * @nums[1] * @nums[2] * ... * @nums[*-1];

In this example, that computes the product of all the numbers.

On the other hand, the triangular reduction metaoperator
(for example, the "triangular products" operator: [\*]):

@products = [\*] @n;

does more-or-less the same thing, but instead of returning only the final calculation,
it returns a progressive list of partial results from each successive multiplicative step,
just as if it had been written:

@products = (@n[0], @n[0]*@n[1], @n[0]*@n[1]*@n[2], ...);

That might seem like an arcane and useless feature but, of course, it's precisely the arcane and useless feature we actually need in order to build the list of Euclid numbers from a list of primes.

Remember that we're looking for the first non-prime Euclid number. That is: the first non-prime number from all numbers that are one greater than the sequence of cumulative partial products of all the prime numbers from 2 to infinity.

And, once again, that description translates directly into a single line of Perl 6:

say first !*.is-prime, # Print the first non-prime from
map *+1, # all numbers one greater than
[\*] # the cumulative products of
grep &is-prime, # all the prime numbers
2..Inf; # from 2 to infinity

Of course, if you're not yet familiar with Perl 6, that [\*] sandwiched in the middle of the statement might seem just too darn scary.

Happily, our solution also happens to be pure functional, so it's easy to factor out the offending line-noise and hide it away in some function with a more soothing name:

sub partial-products-of { [\*] @^list }

Then we could write:

say first !*.is-prime, # Print the first non-prime from
map *+1, # all numbers one greater than
partial-products-of # the cumulative products of
grep &is-prime, # all the prime numbers
2..Inf; # from 2 to infinity

Or, if that's still too arcane for comfort, we could go the whole hog and refactor the entire thing all the way out to plain English:

sub successor-of { @^*+1) }
sub the-primes { (2..Inf).grep(&is-prime) }
sub first-non-prime { @^list.first(!*.is-prime) }

Which gives us:

say first-non-prime successor-of partial-products-of the-primes;

Code doesn't get much more declarative or self-documenting than that!
Unless, of course, we also happen to know the definition of the Euclid numbers:

sub Euclid-number {successor-of partial-products-of the-primes}

In which case, our entire solution is now just the original description of our problem:

say first-non-prime Euclid-number;

"Perl 6: It's not your grandparent's executable line-noise."


Leave a comment

About Damian Conway

user-pic I blog about Perl.