laurent_r

In this other blog post, I provided some answers to Week 15 of the Perl Weekly Challenge organized by Mohammad S. Anwar.

Here, I want to use the opportunity of this challenge to illustrate once more some possibilities of functional programming in Perl (both Perl 5 and Perl 6) using the example of the first challenge of this week. I have already covered some aspects of functional programming in Perl in a post related to Weekly Challenge 9.

The challenge was about displaying the first 10 strong and weak prime numbers. A strong prime is a prime number that is greater than the arithmetic mean of the nearest prime above and below (in other words, it's closer to the following than to the preceding prime). A weak prime is a prime number that is less than the arithmetic mean of the nearest prime above and below. Obviously, a prime number cannot both strong and weak, but some prime numbers, such as 5 or 53 (we'll see more of them later), are neither strong, nor weak (they're called balanced primes): 5 is equal to the arithmetic mean of 3 and 7. Therefore, the fact that a prime is not strong doesn't mean that it is weak.

The Functional Solutions of my Initial Blog Post

The solutions I suggested in the other post on this challenge are in fact largely functional in spirit. One of them in Perl 6:

my @p = grep { .is-prime }, 1..*;   # Lazy infinite list of primes
say "Strong primes: ", (map { @p[$_] }, 
    grep { @p[$_] > (@p[$_ - 1] + @p[$_ + 1]) / 2 }, 1..*)[0..9];
say "Weak primes: ", (map { @p[$_] }, 
    grep { @p[$_] < (@p[$_ - 1] + @p[$_ + 1]) / 2 }, 1..*)[0..9];

And more or less the same idea in Perl 5:

#!/usr/bin/perl
use strict;
use warnings;
use feature qw/say/;

sub is_prime{
    my $num = shift;
    for my $i (2 .. $num ** .5) {
        return 0 if $num % $i == 0;
    }
    return 1;
}
my @p = grep is_prime($_), 1..105;
my @strong = map $p[$_], 
    grep { $p[$_] - $p[$_-1] > $p[$_+1] - $p[$_] } 1..25;
my @weak = map $p[$_], 
    grep { $p[$_] - $p[$_-1] < $p[$_+1] - $p[$_] } 1..25;
say "Strong: @strong[0..9]";
say "Weak: @weak[0..9]";

In both cases, we're using a data pipeline programming model. The code lines with map and grep statements should be read from bottom to top (when they are formatted over more than one line) and from right to left. For example, to understand this code line:

my @strong = map $p[$_], 
    grep { $p[$_] - $p[$_-1] > $p[$_+1] - $p[$_] } 1..25;

one needs to start from the 1..25 range, which is fed to the grep statement, whose role is to filter the range values and keep those which satisfy the condition within the grep block. This means, in this case, to keep the indices of values in the @p array of prime numbers for which the current prime number is closer to the next prime than to the previous prime. These indices are then fed to the map statement in order to populate the @strong array with such primes.

Both Perl5 and Perl 6 implementations work fine, but there are a couple of weaknesses. One is that we're scanning the @p array of prime numbers twice. If we wanted to also identify the balanced primes, we probably would to traverse the list of primes a third time. The second weakness, at least for the Perl 5 implementation, is that is that it is not easy to figure out in advance the range of values on which we want to work. The Perl 6 implementation does not have this second problem because it uses a lazy infinite list of primes, meaning that Perl 6 will only generate the primes that we are requesting elsewhere in the rest of the program.

Note that these weaknesses don't matter very much, since we're dealing with small ranges anyway, but that's not really satisfactory to the mind, as we know that these programs wouldn't scale too well for larger ranges. Let's see whether we can improve these programs.

A Non Functional Implementation

An easy solution to both problems is to write a non (or less) functional solution using an infinite loop.

For example, in Perl 6, this could be something like this:

use v6;

my @p = grep { .is-prime }, 1..*;   # Lazy infinite list of primes
my (@strong, @weak, @balanced);
for 1..* -> $i {
    if @p[$i] > (@p[$i - 1] + @p[$i + 1])/2 { 
        push @strong, @p[$i];
    } 
    elsif @p[$i] < (@p[$i - 1] + @p[$i + 1])/2 {
        push @weak, @p[$i];
    } else {
        push @balanced, @p[$i];
    }
    last if @balanced.elems >= 10;
}
say "Strong primes: @strong[0..9]";
say "Weak primes: @weak[0..9]";
say "Balanced primes: @balanced[]";

This script produces the following output:

$ perl6 strong_primes.p6
Strong primes: 11 17 29 37 41 59 67 71 79 97
Weak primes: 3 7 13 19 23 31 43 47 61 73
Balanced primes: 5 53 157 173 211 257 263 373 563 593

Note that in the code above, we use the fact that we know from previous tests that balanced primes are much less frequent than either strong or weak primes, so that we can stop the for loop when we have 10 balanced primes. Also note that this works fine because, in Perl 6, a forloop is lazy. There may be some possible minor improvements, for example avoiding multiple dereferencing of the @p values (see e.g. the P5 script below), but I'm not really interested here with micro-optimizations.

From now on, we will drop the 4 boiler plate code lines at the P5 script's beginning (the use ... lines) to avoid repetition in each code example, but they are of course necessary in any Perl 5 script (except possibly some simple one-liners). This is the same idea in Perl 5 (with a slightly different algorithm):

sub is_prime{
    my $num = shift;
    for my $i (2 .. $num**.5) {
        return 0 if $num % $i == 0;
    }
    return 1;
}

my @p = grep is_prime($_), 2..600;
my (@strong, @weak, @balanced);
my $i = 0;
while (1) {
    $i++;
    my ($q, $r, $s) = @p[$i-1..$i+1]; 
    if ($r - $q > $s - $r) {
        push @strong, $r;
    } elsif ($r - $q < $s - $r) {
        push @weak, $r;
    } else {
        push @balanced, $r;
    }
    last if @balanced >= 10;
}
say "Strong primes: @strong[0..9]";
say "Weak primes: @weak[0..9]";
say "Balanced primes: @balanced";

These new P6 and P5 versions work fine, but that's really not the way I want to go: I would like to have a more functional version, not a less functional version. And, in the Perl 5 version, we still have to hard-code the range of the prime array.

Let's start with the specific Perl 5 problem, which is due to the fact that Perl 5 does not have built-in support for lazy infinite lists. As discussed in a post related to Weekly Challenge 9, we can still approach lazy infinite lists in Perl 5 with the help of iterators. I'll briefly explain again iterators here, but you might find more details about them by following the above link.

Anonymous Subroutines, Closures and Iterators In Perl 5

Rather than starting by populating an array of primes, we will use an iterator to produce the next wanted primes on demand.

Most programmers commonly use iterators, sometimes not knowing that it's called this way. For example, when you read a file line by line with a construct such as:

while (my $line = <$FH>) {
    # do something with $line
}

you're actually using an iterator.

An iterator is a function that returns values and keeps track of the last returned value to find out the next one. What we want here is a function that returns primes one by one, so that we don't need to compute values that are not needed. In our case, we would need a function that "remembers" the last prime it has found and "knows" how to find the next one.

In the program below, the generate_prime_iterator subroutine is a function generator that returns an anonymous subroutine; this anonymous subroutine acts as an iterator on successive primes. This anonymous subroutine is a closure that updates and keeps track of the last_val variable in the context of which the anonymous code reference is created.

The main code below calls the generate_prime_iterator subroutine once and stores the returned value (the anonymous code reference) into the $give_me_a_prime code reference. In the second line of the infinite while loop, the program calls the $give_me_a_prime code reference until it has enough primes (until $p[$i+1] is populated) for the current iteration. The first time through the while loop, the $give_me_a_prime code reference is called three times; in the following iterations, the program needs to call it only once, in order to get the next needed prime. The last statement near the end of the while loop breaks out of the infinite loop when there are enough items in the @balanced array.

sub is_prime{
    my $num = shift;
    for my $i (2 .. $num**.5) {
        return 0 if $num % $i == 0;
    }
    return 1;
}
sub generate_prime_iterator {
    my $last_val = shift // 1;
    return sub {
        do {
            $last_val ++;
        } until is_prime $last_val;
        return $last_val;
    }
}
my $give_me_a_prime = generate_prime_iterator 1;
my (@strong, @weak, @balanced, @p);
my $i = 0;
while (1) {
    $i++;
    push @p, $give_me_a_prime->() while not defined $p[$i+1];
    my ($q, $r, $s) = @p[$i-1..$i+1]; 
    if ($r - $q > $s - $r) {
        push @strong, $r;
    } elsif ($r - $q < $s - $r) {
        push @weak, $r;
    } else {
        push @balanced, $r;
        last if @balanced >= 10;
    } 
}
say "Strong primes: @strong[0..9]";
say "Weak primes: @weak[0..9]";
say "Balanced primes: @balanced";

This has become a bit more complicated than before, but we no longer need to estimate the number of primes we'll need, and we will not generate any useless prime. We've achieved more or less what we were doing in Perl 6 with a lazy infinite list. It just takes a bit more code to do that.

Categorizing or Classifying Primes In Perl 6

In the Perl 6 section of the initial blog post, we tried to use the categorize or classify built-in subroutines to avoid traversing several times the list of primes. The code was along these lines:

my @p = grep { .is-prime }, 1..*;   # Lazy infinite list of primes
sub mapper(UInt $i) {
    @p[$i] > (@p[$i - 1] + @p[$i + 1])/2 ?? 'Strong' !!
    @p[$i] < (@p[$i - 1] + @p[$i + 1])/2 ?? 'Weak'   !!
    'Balanced';
}
my %categories = classify &mapper, 1..120;
for sort keys %categories -> $key {
    say "$key primes:  ", map {@p[$_]}, %categories{$key}[0..9];
}

This worked fine, but we ran into the problem that the categorize and classify functions don't support infinite lists, so that we needed again to estimate the number of input values we would need to get the desired output.

Let's see if we can write our own version of classify which would have the same calling syntax and be able to handle infinite lists. Our version of the classify function will be called distribute.

my @p = grep { .is-prime }, 1..*;   # Lazy infinite list of primes
sub mapper(UInt $i) {
    @p[$i] > (@p[$i - 1] + @p[$i + 1])/2 ?? 'Strong' !!
    @p[$i] < (@p[$i - 1] + @p[$i + 1])/2 ?? 'Weak'   !!
    'Balanced';
}
sub distribute (&code, @primes) {
    my %distribution;
    for @primes.kv -> $key, $val {
        next if $key == 0;
        push %distribution{&code($key)}, $val;
        last if %distribution{'Balanced'}.elems >= 10;
    }
    return %distribution;
}
my %categories = distribute &mapper, @p;
for sort keys %categories -> $key {
    say "$key primes:  ", %categories{$key}[0..9];
}

Note that, contrary to the previous version, the %distribution and %categories hashes now contain the primes, not the prime indices in the prime array.

And we no longer need to estimate the number of input values to get the desired output.

I am not fully satisfied, though, because the stopping condition (last if ...) is hard-coded in the distribute subroutine, which is therefore very specific to the problem, whereas I would like the distribute subroutine to be more generic. Well, we can pass to distribute a third argument, another code block, to stop the iteration:

my @p = grep { .is-prime }, 1..*;   # Lazy infinite list of primes
sub mapper(UInt $i) {
    @p[$i] > (@p[$i - 1] + @p[$i + 1])/2 ?? 'Strong' !!
    @p[$i] < (@p[$i - 1] + @p[$i + 1])/2 ?? 'Weak'   !!
    'Balanced';
}
sub distribute (&code, @primes, &stopper) {
    my %distribution;
    for @primes.kv -> $key, $val {
        next if $key == 0;
        push %distribution{&code($key)}, $val;
        &stopper(%distribution);
    }
    return %distribution;
}
my $stopper = { last if %^a{'Balanced'}.elems >= 10 };
my %categories = distribute &mapper, @p, $stopper;
for sort keys %categories -> $key {
    say "$key primes:  ", %categories{$key}[0..9];
}

The only trick here if that the $stopper code block uses a self-declared positional parameter (or placeholder), %^a. And we pass the %distribution hash as a parameter to &stopper when we run it within the distribute subroutine. Thus, the calling code doesn't have to know the name of the hash within the distribute subroutine, which is now generic. To be frank, I wasn't convinced this would work until I ran it.

The output is what we want:

$ perl6 strong_primes.p6
Balanced primes:  (5 53 157 173 211 257 263 373 563 593)
Strong primes:  (11 17 29 37 41 59 67 71 79 97)
Weak primes:  (3 7 13 19 23 31 43 47 61 73)

Categorizing or Classifying Primes In Perl 5

Except for the last improvement made just above (using a self-declared parameter), we can do more or less the same in Perl 5:

my @p; # Array to store the primes
sub is_prime{
    my $num = shift;
    for my $i (2 .. $num**.5) {
        return 0 if $num % $i == 0;
    }
    return 1;
}
sub generate_prime_iterator {
    my $last_val = shift // 1;
    return sub {
        do {
            $last_val ++;
        } until is_prime $last_val;
        return $last_val;
    }
}
sub mapper {
    my $i = shift;
    $p[$i] > ($p[$i - 1] + $p[$i + 1])/2 ? 'Strong' :
    $p[$i] < ($p[$i - 1] + $p[$i + 1])/2 ? 'Weak'   :
    'Balanced';
}
sub distribute {
    my ($prime_generator, $mapper) = @_;
    my %distribution;
    my $k = 0;
    while (1) {
        $k++;
        push @p, $prime_generator->() while not defined $p[$k+1];
        push @{$distribution{$mapper->($k)}}, $p[$k];
        last if defined $distribution{Balanced} and 
            scalar @{$distribution{Balanced}} >= 10;
    }
    return %distribution;
}
my $give_me_a_prime = generate_prime_iterator 1;
my %categories = distribute $give_me_a_prime, \&mapper;
say "Strong primes: @{$categories{'Strong'}}[0..9]";
say "Weak primes: @{$categories{Weak}}[0..9]";
say "Balanced primes: @{$categories{Balanced}}[0..9]";

This works as intended. We cannot pass the stopper as a code block as in Perl 6, but there would be some work around if we wanted to. For example, the stopper block of Perl 6 could be passed as a string containing the code block and be evaled in the distribute subroutine. Another limitation is that the @p prime array is a global variable. This could be avoided if we wanted to, but I am not convinced that it makes sense to bend over backward and make the code significantly more complicated just for the sake of bureaucratic rules. In this case, the @p prime array is part of a caching strategy, it makes sense to have it a global variable.

Wrapping up

The next week Perl Weekly Challenge is due to start soon. If you want to participate in this challenge, please check https://perlweeklychallenge.org/ and make sure you answer the challenge before 23:59 BST (British summer time) on Sunday, July 14 (Bastille Day). And, please, also spread the word about the Perl Weekly Challenge if you can.