Re: Functional perl please

[ariels]

in reply to Functional perl please

Here's one example. The Hamming sequence is the sequence of numbers whose prime factors are only 2, 3 and 5, in ascending order. Writing a program to print out the sequence is non-trivial (we exclude "solutions" which must store the entire sequence in a large array and the like). It used to be the poster example of co-routines, but current style more likely favours a functional program using streams and (somewhat) lazy evaluation.

Read about streams in this chapter of Structure and Interpretation of Computer Programs. The program below is a translation to Perl of a streams-based program to print out the Hamming sequence.

#!/usr/local/bin/perl -w
# Output the Hamming sequence
use strict;

package Stream;

sub new {
  my ($class, $hd, $tl) = @_;
  $class = ref $class || $class;
  bless { _hd => $hd, _tl => $tl }, $class
}

sub head {
  my $self=shift;
  $self->{_hd}
}

sub tail {
  my $self = shift;
  $self->{_tl} = $self->{_tl}->()
    if ref $self->{_tl} eq 'CODE';
  $self->{_tl}
}

sub exec {
  my ($self, $code, $n) = @_;
  for my $i (1..$n) {
    $code->($self->head);
    $self = $self->tail
  }
}


package main;

sub merge {
  my ($a, $b) = @_;
  return ($a->head == $b->head) ?
    new Stream($a->head, sub { merge($a->tail, $b->tail) }) :
      ($a->head < $b->head) ?
    new Stream($a->head, sub { merge($a->tail, $b) }) :
      new Stream($b->head, sub { merge($a, $b->tail) });
}

sub mult {
  my ($a, $s) = @_;
  return new Stream($a*$s->head, sub { mult($a,$s->tail) });
}


my $hamming;
$hamming = new Stream(1,
                      sub {
                        merge( mult(2, $hamming),
                               merge(mult(3, $hamming),
                               mult(5, $hamming)))
              }
             );

my @x;
$hamming->exec(sub { push @x, shift }, 1000);

print "@x\n";

---

EDIT (20020506): fix indentation (Perlmonks does horrible things to tabs; glad it's not Pythonmonks).