note
ariels
<p>
Here's one example. The <a href="http://www.everything2.com/?node=hamming%20sequence">Hamming sequence</a> 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.
</p>
<p>
Read about streams in <a href="http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-24.html#%_sec_3.5">this chapter</a> of <a href="http://mitpress.mit.edu/sicp">Structure and Interpretation of Computer Programs</a>. The program below is a translation to Perl of a streams-based program to print out the Hamming sequence.
</p>
<blockquote><code>
#!/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";
</code></blockquote>
<hr />
<b>EDIT</b> (20020506): fix indentation (Perlmonks does horrible things to tabs; glad it's not Pythonmonks).
136017
136017