HOPの6章は無限ストリームを扱っているのだけれど、SICPの無限ストリームの章にあるエラトステネスの篩が出てこないので書いてみた。
HOPだとcar,cdr,consがそれぞれhead,tail,nodeとなってるのでそれにあわせてある。promiseは計算を遅延させるためのクロージャ。
use strict;
use warnings;
no warnings 'recursion';
sub promise (&) { $_[0] }
sub node{
my ($h, $t) = @_;
[$h, $t];
}
sub head {
my ($ls) = @_;
$ls->[0];
}
sub tail {
my ($ls) = @_;
if(is_promise($ls->[1])){
$ls->[1] = $ls->[1]->();
}
$ls->[1];
}
sub is_promise {
UNIVERSAL::isa($_[0],'CODE');
}
sub drop {
my $h = head($_[0]);
$_[0] = tail($_[0]);
return $h;
}
sub filter (&$) {
my $f = shift;
my $s = shift;
until(! $s || $f->(head($s))){
drop($s);
}
return if ! $s;
node(head($s),promise {filter($f, tail($s))});
}
sub sieve {
my $s = shift;
node(head($s),
promise {sieve(filter {$_[0] % head($s)} tail($s))});
}
sub upfrom {
my ($m) = @_;
node($m, promise{ upfrom($m+1)});
}
sub show {
my ($s,$n) = @_;
while($s && (! defined $n || $n-- > 0)){
print head($s), $";
$s = tail($s);
}
print $/;
}
my $primes = sieve(upfrom(2));
show($primes,300);
これで、素数のストリームが生成される。
計算機プログラムの構造と解釈
Higher-order Perl: A Guide To Program TransformationMark Jason Dominus
Morgan Kaufmann Pub / ￥ 7,608 (2005-05-30)
通常24時間以内に発送
無限ストリームは楽しい
