sieve.rb
「そうねえ。素数を遅延評価で求めたりしてるわね」
30分シリーズ、その10。今回は、遅延評価で素数を求めてみる。
$ ruby sieve.rb [2, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49, 51, 53, 55, 57, 59, 61, 63, 65, 67, 69, 71, 73, 75, 77, 79, 81, 83, 85, 87, 89, 91, 93, 95, 97, 99, 101, 103, 105, 107, 109, 111, 113, 115, 117, 119, 121, 123, 125, 127, 129, 131, 133, 135, 137, 139, 141, 143, 145, 147, 149, 151, 153, 155, 157, 159, 161, 163, 165, 167, 169, 171, 173, 175, 177, 179, 181, 183, 185, 187, 189, 191, 193, 195, 197, 199]
遅延評価は、SICPのストリームと同じ方法を使っている。
まず、Rubyで単方向リストを実現してみる。
Cons = Struct.new 'Cons',:car,:cdr # [1,2] Cons.new(1,Cons.new(2,nil))
次に、これを遅延ストリームにする。遅延ストリームは、cdr部分を関数にする。そして、値が必要になったときに、その関数を評価すると実現できる。
class Cons def initialize(car,cdr) @car = car @cdr = cdr end def car @car end def cdr @cdr.call end end # [1,2] Cons.new(1, lambda{ Cons.new(2, lambda{nil })})
あとは、このConsやcar、cdrをつかって適宜mapやfilterを作れば、遅延ストリームでプログラムができる。(今回はfilterだけ)
あと、素数の計算はエラトステネスの篩(ふるい)を使って求めている。
class Cons attr_reader :car def initialize(car,null=false,&cdr) @car = car @cdr = cdr @null = null end def null? @null end def cdr @cdr.call end def get(n) if n == 0 then car else self.cdr.get(n-1) end end def filter(&f) if null? then self elsif f.call car then Cons.new(car){ cdr.filter(&f) } else cdr.filter(&f) end end def to_a if null? then [] else [@car] + cdr.to_a end end def slice(from,to) if from == to [] elsif from > 0 cdr.slice(from-1,to-1) else [@car] + cdr.slice(0,to-1) end end end # null要素を作る $null = Cons.new nil,true # 範囲を指定して、整数のリストを生成 def range(from,to) if from > to then $null else Cons.new(from){ range(from+1,to) } end end # 無限の整数リストの生成 def range_infty(from) Cons.new(from){ range_infty(from+1) } end # エラトステネスの篩 def sieve(list) Cons.new(list.car){ list.cdr.filter{|x| x % list.car != 0 } } end p sieve(range_infty(2)).slice(0,100)
