2005/06/09

情報処理学会誌2005年4月号の『関数プログラミングの妙味』(PDF)という記事を読んでいたら、素数を求めるこんな Haskell スクリプトが紹介されていた。

primes = sieve [2..]
where sieve (s:ss) = s:sieve (filter (\x -> x `mod` s > 0) ss)

Main> take 25 pimes
[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97]

日本語はおかしな和田さんだけど、これはなんだかかっこいい。Scheme でも同じことがしたい。

(let prime-list ((ls '(2 3 4 5 6 7 8 9 10 11 12)))
(if (null? ls)
()
(cons (car ls)
(prime-list (filter (lambda (x) (> (modulo x (car ls)) 0))
(cdr ls))))))

=>(2 3 5 7 11)

遅延評価が当たり前の Haskell と違って無限リストを自然に扱えないのがつらいところ。というわけで delay を使ってみる。とりあえず自然数全体の集合(リスト)はこんな感じかな。

(define int-inf
(let mkls ((x 0))
(delay (cons x (mkls (+ x 1))))))

『Gauche リファレンスマニュアル』の遅延評価の例にある "ltake" を使わせてもらえば、ゼロから始まる任意の長さの自然数列が得られる。

gosh> (ltake int-inf 20)
(0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19)

でも、これを最初の prime-list に組み込むのはめんどくさいな。そもそも、自然数列を得るだけなら遅延評価を使わなくてもいいような気がしてきた。というわけで

(define (primes-under num)
(let prime-list ((ls (let mkls ((x 2))
(if (<= num x) '() (cons x (mkls (+ x 1)))))))
(if (null? ls)
()
(cons (car ls)
(prime-list (filter (lambda (x) (> (modulo x (car ls)) 0))
(cdr ls)))))))

=>(primes-under 100)
(2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97)

うーむ。かっこよさとしてはちゅうくらいか。遅延評価のサポート具合もプログラムの抽象化に大きく影響するらしい。

No comments :