「ストリーム (stream)」はデータの流れを抽象化したデータ構造です。たとえば、ファイル入出力はストリームと考えることができます。また、リストを使ってストリームを表すこともできます。ただし、単純なリストでは有限個のデータの流れしか表すことができません。ところが、遅延評価を用いると擬似的に無限個のデータを表すことができるようになります。これを「遅延ストリーム」とか「遅延リスト」と呼びます。今回は遅延ストリームについて説明します。
なお、Gauche には SRFI-40 に相当する遅延ストリームライブラリ util.stream と、独自の遅延シーケンスユーティリティ gauche.lazy が用意されているので、私たちが遅延ストリームを作る必要はまったくありませんが、Scheme のお勉強ということで、あえてプログラムを作ってみましょう。
遅延ストリームの基本的な考え方は、必要になったときに新しいデータを生成することです。このときに遅延評価を用います。具体的にはデータを生成する関数を用意し、それを遅延評価してストリームに格納しておきます。そして、必要になった時点で遅延評価しておいた関数を呼び出して値を求めればよいわけです。
今回は遅延ストリームをコンスセルで表すことにします。コンスセルの CAR が現時点での先頭データを表し、CDR が遅延ストリームを生成する関数を格納するプロミスです。次のリストを見てください。
リスト : 遅延ストリーム
(use srfi-1)
;; 遅延ストリームの生成
(define-syntax stream-cons
(syntax-rules ()
((_ a b) (cons a (delay b)))))
;; 先頭要素を参照
(define (stream-car s) (car s))
;; 先頭要素を取り除く
(define (stream-cdr s) (force (cdr s)))
;; ストリームの終端
(define nil '())
(define empty? null?)
マクロ stream-cons はコンスセルの CAR にストリームの要素 a を格納し、CDR にプロミスを格納します。プロミスにはストリームを生成する関数 b を格納します。プロミスを force することで、次の要素を格納した遅延ストリームを生成します。ストリームの終端は nil で表すことにします。nil は空リスト () で表し、遅延ストリームの終端を判定する述語 empty? を用意します。empty? は null? と同じです。
関数 stream-car は遅延ストリーム s から要素を取り出して返します。関数 stream-cdr は s のプロミスを force して、次の要素を格納した遅延ストリームを生成して返します。ようするに、これらのマクロと関数はリスト操作の cons, car, cdr に対応しているわけです。
それでは、遅延ストリームを生成する関数を作りましょう。たとえば、low から high までの整数列を生成するストリームは次のようにプログラムすることができます。
リスト : 整数列を生成するストリーム
(define (range low high)
(if (> low high)
nil
(stream-cons low
(range (+ 1 low) high))))
関数 range は遅延ストリームを生成して返します。stream-cons の第 1 引数がストリームの初期値になります。そして、プロミスを force すると、(range (+ 1 low) high) が評価されて次のデータを格納した遅延ストリームが返されます。そして、その中のプロミスを force すると、その次のデータを得ることができます。
簡単な例を示しましょう。
gosh> (define a (range 1 10)) a gosh> (stream-car a) 1 gosh> (stream-car (stream-cdr a)) 2 gosh> (stream-car (stream-cdr (stream-cdr a))) 3 gosh> (stream-car (stream-cdr (stream-cdr (stream-cdr a)))) 4
このように、CDR 部のプロミスを force することで、次々とデータを生成することができます。
もう一つ、簡単な例を示しましょう。フィボナッチ数列を生成する遅延ストリームを作ります。次のリストを見てください。
リスト : フィボナッチ数列を生成する遅延ストリーム (define (fibonacci a b) (stream-cons a (fibonacci b (+ a b))))
関数 fibonacci の引数 a がフィボナッチ数列の最初の項で、b が次の項です。したがって、プロミスに (fibonacci b (+ a b)) を格納しておけば、force することでフィボナッチ数列を生成することができます。Scheme は多倍長整数をサポートしているので、メモリの許す限りフィボナッチ数列を生成することができます。
gosh> (define b (fibonacci 0 1)) b gosh> (stream-car b) 0 gosh> (stream-car (stream-cdr b)) 1 gosh> (stream-car (stream-cdr (stream-cdr b))) 1 gosh> (stream-car (stream-cdr (stream-cdr (stream-cdr b)))) 2
これらの関数の動作を一般化すると、次のような関数を定義することができます。
リスト : 無限ストリームの生成 (define (iterate proc a) (stream-cons a (iterate proc (proc a))))
関数 iterate は初項 a を受け取り、次項を関数 proc で生成します。stream-cons の第 1 引数に a を渡して、第 2 引数で iterate を呼び出すときに (proc a) の返り値を渡します。これで、無限のストリームを生成することができます。
簡単な実行例を示します。
gosh> (define c (iterate (lambda (x) (+ x 1)) 1)) c gosh> (stream-car c) 1 gosh> (stream-car (stream-cdr c)) 2 gosh> (stream-car (stream-cdr (stream-cdr c))) 3 gosh> (stream-car (stream-cdr (stream-cdr (stream-cdr c)))) 4 gosh> (define d (iterate (lambda (xs) (list (second xs) (apply + xs))) '(0 1))) d gosh> (stream-car d) (0 1) gosh> (stream-car (stream-cdr d)) (1 1) gosh> (stream-car (stream-cdr (stream-cdr d))) (1 2) gosh> (stream-car (stream-cdr (stream-cdr (stream-cdr d)))) (2 3)
リストを遅延ストリームに変換することも簡単にできます。次のリストを見てください。
リスト : リストを遅延ストリームに変換
(define (list->stream xs)
(if (null? xs)
nil
(stream-cons (car xs) (list->stream (cdr xs)))))
関数 list->stream はリスト xs の先頭から要素を順番に取り出して、遅延ストリームに格納して返すだけです。
簡単な実行例を示します。
gosh> (define e (list->stream '(1 2 3 4 5)))
e
gosh> (stream-car e)
1
gosh> (stream-car (stream-cdr e))
2
gosh> (stream-car (stream-cdr (stream-cdr e)))
3
gosh> (define f (list->stream '("foo" "bar" "baz" "oops")))
f
gosh> (stream-car f)
"foo"
gosh> (stream-car (stream-cdr f))
"bar"
gosh> (stream-car (stream-cdr (stream-cdr f)))
"baz"
次は遅延ストリームを操作する関数を作りましょう。最初は n 番目の要素を求める関数 stream-ref です。本稿では Scheme のリストに合わせて先頭の要素を 0 番目とします。
リスト : n 番目の要素を求める
(define (stream-ref s n)
(if (zero? n)
(stream-car s)
(stream-ref (stream-cdr s) (- n 1))))
stream-ref は stream-cdr でデータを生成し、それを n 回繰り返すことで n 番目の要素を求めます。stream-cdr は遅延ストリームを返すことに注意してください。あとは、stream-ref を再帰呼び出しして、n が 0 になったら stream-car でストリームの要素を取り出せばいいわけです。
ストリームから n 個の要素を取り出してリストに格納して返す関数 stream-take と、n 個の要素を取り除く関数 stream-drop も同様にプログラムすることができます。
リスト : 先頭から n 個の要素を取り出す
(define (stream-take s n)
(let loop ((s s) (n n) (a nil))
(if (or (empty? s) (zero? n))
(reverse! a)
(loop (stream-cdr s) (- n 1) (cons (stream-car s) a)))))
リスト : 先頭から n 個の要素を取り除く
(define (stream-drop s n)
(if (or (empty? s) (zero? n))
s
(stream-drop (stream-cdr s) (- n 1))))
引数 s が遅延ストリームで、引数 n が取り出す要素の個数です。s が空になるか、n が 0 になるまで処理を繰り返します。stream-take は stream-car で要素を取り出しで、それを累積変数 a に追加します。最後に reverse! でリスト a を反転して返します。stream-drop は stream-cdr を n 回繰り返すだけです。
簡単な実行例を示します。
gosh> (define fibo (fibonacci 0 1)) fibo gosh> (dotimes (x 10) (print (stream-ref fibo x))) 0 1 1 2 3 5 8 13 21 34 #<undef> gosh> (stream-take fibo 10) (0 1 1 2 3 5 8 13 21 34) gosh> (stream-take (stream-drop fibo 40) 10) (102334155 165580141 267914296 433494437 701408733 1134903170 1836311903 2971215073 4807526976 7778742049)
変数 fibo にフィボナッチ数列を生成するストリームをセットします。stream-ref で順番に要素を 10 個求めると、その値はフィボナッチ数列になっていますね。同様に、stream-take で 10 個の要素を取り出すと、リストの要素はフィボナッチ数列になります。stream-drop で 40 個の要素を取り除き、そのあと stream-take で 10 個の要素を取り出すと、41 番目以降のフィボナッチ数列を求めることができます。
次は、2 つの遅延ストリームを受け取って 1 つの遅延ストリームを返す関数を考えます。一番簡単な操作は 2 つの遅延ストリームを結合することです。次のリストを見てください。
リスト : 遅延ストリームの結合
(define (stream-append s1 s2)
(if (empty? s1)
s2
(stream-cons (stream-car s1)
(stream-append (stream-cdr s1) s2))))
関数 stream-append はストリーム s1 と s2 を結合したストリームを返します。処理は簡単で、s1 の要素を順番に取り出していき、s1 が空になったら s2 を返すだけです。
簡単な実行例を示しましょう。
gosh> (define s1 (range 1 4)) s1 gosh> (define s2 (range 5 8)) s2 gosh> (define s3 (stream-append s1 s2)) s3 gosh> (stream-take s3 8) (1 2 3 4 5 6 7 8)
次は遅延ストリーム s1 と s2 の要素を交互に出力するストリームを作ります。次のリストを見てください。
リスト : 遅延ストリームの要素を交互に出力
(define (interleave s1 s2)
(if (empty? s1)
s2
(stream-cons (stream-car s1)
(interleave s2 (stream-cdr s1)))))
関数 interleave はストリーム s1 と s2 を受け取ります。そして、s1 の要素を新しい遅延ストリームに格納したら、次は s2 の要素を新しい遅延ストリームに格納します。これはプロミスで interleave を呼び出すとき、引数 s1 と s2 の順番を交換するだけです。このとき、s1 は stream-cdr で次の要素を求めます。これで s1 と s2 の要素を交互に出力することができます。
簡単な実行例を示しましょう。
gosh> (define s4 (interleave s1 s2)) s4 gosh> (stream-take s4 8) (1 5 2 6 3 7 4 8)
stream-append の場合、無限ストリームを結合することはできませんが、interleave ならば無限ストリームにも対応することができます。簡単な例を示しましょう。
gosh> (define ones (stream-cons 1 ones)) ones gosh> (stream-take ones 10) (1 1 1 1 1 1 1 1 1 1) gosh> (define twos (stream-cons 2 twos)) twos gosh> (stream-take twos 10) (2 2 2 2 2 2 2 2 2 2) gosh> (stream-take (interleave ones twos) 10) (1 2 1 2 1 2 1 2 1 2)
ones は 1 を無限に出力するストリームで、twos は 2 を無限に出力するストリームです。stream-append で ones と twos を結合しても無限に 1 を出力するだけですが、interleave で ones と twos を結合すれば、1 と 2 を交互に出力することができます。これで無限ストリームの要素を混ぜ合わせることができます。
次は遅延ストリーム用の高階関数を作りましょう。
リスト : 高階関数
;; マッピング
(define (stream-map proc . s)
(if (any empty? s)
nil
(stream-cons (apply proc (map stream-car s))
(apply stream-map proc (map stream-cdr s)))))
;; フィルター
(define (stream-filter pred s)
(cond ((empty? s) nil)
((pred (stream-car s))
(stream-cons (stream-car s)
(stream-filter pred (stream-cdr s))))
(else
(stream-filter pred (stream-cdr s)))))
;; 畳み込み
(define (stream-fold-left proc a s)
(if (empty? s)
a
(stream-fold-left proc (proc a (stream-car s)) (stream-cdr s))))
(define (stream-fold-right proc a s)
(if (empty? s)
a
(proc (stream-car s) (stream-fold-right proc a (stream-cdr s)))))
;; 巡回
(define (stream-for-each proc s)
(cond ((not (empty? s))
(proc (stream-car s))
(stream-for-each proc (stream-cdr s)))))
stream-map は引数のストリームの要素に関数 proc を適用した結果を新しいストリームに格納して返します。stream-map は複数の遅延ストリームを受け取ることができます。stream-filter は述語 pred が真を返す要素だけを新しいストリームに格納して返します。
stream-fold-left と stream-fold-right は遅延ストリームに対して畳み込み処理を行います。stream-for-each は遅延ストリームの要素に関数 proc を適用します。無限ストリームの場合、これらの関数は処理が終了しないので注意してください。
簡単な実行例を示しましょう。
gosh> (define s1 (iterate (lambda (x) (+ x 1)) 1)) s1 gosh> (define s2 (stream-map (lambda (x) (* x x)) s1)) s2 gosh> (stream-take s1 10) (1 2 3 4 5 6 7 8 9 10) gosh> (stream-take s2 10) (1 4 9 16 25 36 49 64 81 100) gosh> (define s3 (stream-filter even? s1)) s3 gosh> (stream-take s3 10) (2 4 6 8 10 12 14 16 18 20) gosh> (stream-fold-left + 0 (range 1 100)) 5050 gosh> (stream-fold-right + 0 (range 1 100)) 5050 gosh> (stream-for-each print (range 1 10)) 1 2 3 4 5 6 7 8 9 10 #<undef>
変数 s1 に 1 から始まる整数列を生成する遅延ストリームをセットします。次に、s1 の要素を 2 乗する遅延ストリームを stream-map で生成して変数 s2 にセットします。stream-take で s2 から要素を 10 個取り出すと、s1 の要素を 2 乗した値になります。
s1 から偶数列の遅延ストリームを得るには、引数が偶数のときに真を返す述語を stream-filter に渡します。その返り値を変数 s3 にセットして、stream-take で 10 個の要素を取り出すと、リストの要素は 2 から 20 までの値になります。
range で有限個の遅延ストリームを生成すると畳み込みを行うことができます。stream-fold-left と stream-fold-right で要素の合計値を求めると 5050 になります。もちろん、stream-for-each も正常に動作します。
stream-map は複数の遅延ストリームを受け取ることができるので、それらの遅延ストリームに対していろいろな処理を定義することができます。次の例を見てください。
gosh> (define (add-stream s1 s2) (stream-map + s1 s2)) add-stream gosh> (define s1 (range 1 4)) s1 gosh> (define s2 (range 11 14)) s2 gosh> (define s5 (add-stream s1 s2)) s5 gosh> (stream-take s5 4) (12 14 16 18)
add-stream は s1 と s2 の要素を加算した遅延ストリームを返します。この add-stream を使うと、整数を生成する遅延ストリームは次のように定義することができます。
gosh> (define ones (stream-cons 1 ones)) ones gosh> (define ints (stream-cons 1 (add-stream ones ints))) ints gosh> (stream-take ints 10) (1 2 3 4 5 6 7 8 9 10)
ストリーム ints は、現在の ints に 1 を足し算することで整数を生成しています。これで整数が生成できるとは不思議ですね。ints の動作を図に示すと、次のようになります。
ones = Cons(1, delay ones)
= Cons(1, lazy_obj1)
ints = Cons(1, delay (add_stream ones ints))
= Cons(1, lazy_obj2)
lazy_obj2 = Cons(1 + 1, delay (add_stream (force lazy_obj1) (force lazy_obj2)))
=> Cons(2, delay (add_stream (force lazy_obj1) (force lazy_obj2)))
=> Cons(2, lazy_obj3)
lazy_obj3 => Cons(3, lazy (add_stream (force lazy_obj1) (force lazy_obj3)))
=> Cons(3, lazy_obj4)
図 : ストリーム ints の動作
ones を Cons(1, lazy_obj1) と表し、ints を Cons(1, lazy_obj2) と表します。lazy_obj はプロミスを表します。ints で次の要素を生成するとき、lazy_obj2 を force します。すると、add_stream (stream_map2) に ones と ints が適用され、ストリームの要素 2 とプロミス lazy_obj3 が生成されます。このとき、lazy_obj3 の内容は add_stream (force lazy_obj1) (force lazy_obj2) になります。
次の要素を生成するときは、lazy_obj3 を force します。lazy_obj1 は Cons(1, lazy_obj1) に、lazy_obj2 は Cons(2, lazy_obj3) に評価されるので、ストリームの要素は 1 + 2 = 3 になり、プロミス lazy_obj4 の内容は add_stream (force lazy_obj1) (force lazy_obj3) になります。そして、このプロミスを force することで次の要素を求めることができます。
このように、プロミスの中に現時点の整数を保持しておき、そこに 1 を足し算することで整数列を生成しているわけです。ここで、プロミスは評価結果をキャッシュしているので、整数 n の次の値を簡単に計算できることに注意してください。もしも、プロミスを単純なクロージャで実装した場合、整数 n を求めるため再計算が行われるので、効率はとても悪くなります。
同様の方法でフィボナッチ数列を生成するストリームを定義することができます。
リスト : フィボナッチ数列の生成 (define fibs (stream-cons 0 (stream-cons 1 (add-stream (stream-cdr fibs) fibs))))
fibs が現在のフィボナッチ数列を表していて、(stream-cdr fibs) で次の要素を求めます。そして、それらを足し算することで、その次の要素を求めています。この場合、ストリームの初期値として 2 つの要素が必要になることに注意してください。
それでは実行してみましょう。
gosh> (stream-take fibs 10) (0 1 1 2 3 5 8 13 21 34)
このように、2 つのストリームを使ってフィボナッチ数列を生成することができます。
次は高階関数 stream-flatmap を作りましょう。flatmap は map の結果を平坦化する関数で、具体的には map が返すリストの要素を append で連結する動作になります。引数がリストの場合、次のように定義することができます。
リスト : マッピングした結果を平坦化する (define (flatmap proc xs) (apply append (map proc xs)))
拙作のページ 継続と継続渡しスタイル で作成した関数 flatten を使うと、すべてのリストに対して平坦化を行いますが、apply を使ってリストの要素を append でつなげば、リストを一段階だけ平坦化することができます。
簡単な実行例を示します。
gosh> (define (flatmap proc xs) (apply append (map proc xs))) flatmap gosh> (flatmap (lambda (x) (make-list x x)) (iota 10 1)) (1 2 2 3 3 3 4 4 4 4 5 5 5 5 5 6 6 6 6 6 6 7 7 7 7 7 7 7 8 8 8 8 8 8 8 8 9 9 9 9 9 9 9 9 9 10 10 10 10 10 10 10 10 10 10)
stream-flatmap を定義する場合、次のように stream-append を使うと問題が発生します。
リスト : stream-flatmap の定義 (間違い)
(define (stream-flatmap proc s)
(if (empty? s)
nil
(stream-append (proc (stream-car s))
(stream-flatmap proc (stream-cdr s)))))
Scheme の関数は正格評価なので、stream-append を実行する前に引数が評価されます。つまり、stream-flatmap の評価は遅延されるのではなく、遅延ストリームが空になるまで stream-flatmap が再帰呼び出しされるのです。これでは無限ストリームに対応することができません。
そこで、引数を遅延評価する関数 stream-append-delay を作ることにします。プログラムは次のようになります。
リスト : stream-append-delay と stream-flatmap
;; 遅延ストリームの連結 (遅延評価版)
(define (stream-append-delay s1 s2)
(if (empty? s1)
(force s2)
(stream-cons (stream-car s1)
(stream-append-delay (stream-cdr s1) s2))))
;; マッピングの結果を平坦化する
(define (stream-flatmap proc s)
(if (empty? s)
nil
(stream-append-delay (proc (stream-car s))
(delay (stream-flatmap proc (stream-cdr s))))))
stream-append-delay は stream-append とほぼ同じですが、遅延ストリーム s1 が空になったらプロミス s2 を force で評価するところが異なります。stream-flatmap では、stream-appned のかわりに stream-append-delay を使います。このとき、delay で生成したプロミスを引数に渡します。
それでは実行してみましょう。
gosh> (define s1 (iterate (lambda (x) (+ x 1)) 1)) s1 gosh> (define s2 (stream-flatmap (lambda (x) (list->stream (make-list x x))) s1)) s2 gosh> (stream-take s2 55) (1 2 2 3 3 3 4 4 4 4 5 5 5 5 5 6 6 6 6 6 6 7 7 7 7 7 7 7 8 8 8 8 8 8 8 8 9 9 9 9 9 9 9 9 9 10 10 10 10 10 10 10 10 10 10)
s1 は無限ストリームになりますが、stream-flatmap は正常に動作していますね。
次は、遅延ストリームの先頭から述語が真を返す要素を取り出す stream-take-while と要素を取り除く stream-drop-while を作ります。
リスト : stream-take-while と stream-drop-while
(define (stream-take-while pred s)
(let loop ((s s) (a '()))
(if (or (empty? s) (not (pred (stream-car s))))
(reverse! a)
(loop (stream-cdr s) (cons (stream-car s) a)))))
(define (stream-drop-while pred s)
(if (or (empty? s) (not (pred (stream-car s))))
s
(stream-drop-while pred (stream-cdr s))))
どちらの関数も難しいところはないと思います。簡単な実行例を示しましょう。
gosh> (define s1 (iterate (lambda (x) (+ x 1)) 1)) s1 gosh> (stream-take-while (lambda (x) (< x 10)) s1) (1 2 3 4 5 6 7 8 9) gosh> (define s2 (stream-drop-while (lambda (x) (< x 10)) s1)) s2 gosh> (stream-take s2 10) (10 11 12 13 14 15 16 17 18 19)
最後に簡単な例題として、ストリームを使って素数を求めるプログラムを作ってみましょう。なお、Gauche には素数を取り扱うライブラリ math.prime が用意されているので、私たちがプログラムを作る必要はありませんが、Scheme のお勉強ということで、あえてプログラムを作ることにします。
考え方は簡単です。最初に、2 から始まる整数列を生成するストリームを用意します。2 は素数なので、素数ストリームの要素になります。次に、この整数列から 2 で割り切れる整数を取り除き除きます。これは stream-filter を使うと簡単です。2 で割り切れる整数が取り除かれたので、次の要素は 3 になります。今度は 3 で割り切れる整数を取り除けばいいのです。これも stream-filter を使えば簡単です。このとき、入力用のストリームは 2 で割り切れる整数が取り除かれています。したがって、このストリームに対して 3 で割り切れる整数を取り除くように stream-filter を設定すればいいわけです。
このように、素数を見つけたらそれで割り切れる整数を取り除いていくアルゴリズムを「エラトステネスの篩」といいます。ようするに、2 から始まる整数ストリームに対して、見つけた素数 2, 3, 5, 7, 11, ... を順番に stream-fiter で設定して素数でない整数をふるい落としていくわけです。
プログラムは次のようになります。
リスト : 素数の生成
(define (sieve s)
(stream-cons (stream-car s)
(sieve (stream-filter
(lambda (x) (not (zero? (modulo x (stream-car s)))))
(stream-cdr s)))))
sieve には 2 から始まる整数列を生成するストリームを渡します。stream-cdr でプロミスを force すると、stream-filter により整数列から 2 で割り切れる整数を取り除いたストリームが返されます。次の要素 3 を取り出すとき、このストリームに対して 3 で割り切れる整数を取り除くことになるので、2 と 3 で割り切れる整数が取り除かれることになります。次の要素は 5 になりますが、そのストリームからさらに 5 で割り切れる整数が stream-filter で取り除かれることになります。
このように stream-filter を重ねて設定していくことで、素数でない整数をふるい落としていくことができるわけです。それでは実行してみましょう。
gosh> (define primes (sieve (iterate (lambda (x) (+ x 1)) 2))) primes gosh> (stream-take primes 25) (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) gosh> (stream-take primes 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 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439 443 449 457 461 463 467 479 487 491 499 503 509 521 523 541)
iterate で 2 から始まる整数列を sieve に渡します。100 以下の素数は全部で 25 個あります。
関数 sieve は簡単にプログラムできますが、生成する素数の個数が多くなると、その実行速度はかなり遅くなります。実をいうと、sieve なみに簡単で sieve よりも高速な方法があります。
整数 n が素数か確かめる簡単な方法は、√n 以下の素数で割り切れるか試してみることです。割り切れる素数 m があれば、n は素数ではありません。そうでなければ、n は素数であることがわかります。
これをそのままプログラムすると次のようになります。
リスト : 素数列の生成
(define primes (stream-cons 2 (stream-cons 3 (stream-cons 5 (primes-from 7)))))
(define (primes-from n)
(if (prime? n)
(stream-cons n (primes-from (+ n 2)))
(primes-from (+ n 2))))
(define (prime? n)
(every (lambda (p) (not (zero? (modulo n p))))
(stream-take-while (lambda (p) (<= (* p p) n)) primes)))
変数 primes は無限の素数列を表します。実際に素数を生成する処理は関数 primes-from で行います。primes-from は関数 prime? を呼び出して n が素数かチェックします。そうであれば、stream-cons で n を遅延ストリームに追加します。そうでなければ primes-from を再帰呼び出しするだけです。偶数は素数ではないので、引数 n には奇数を与えていることに注意してください。
prime? も簡単です。stream-take-while で primes から √n 以下の素数列を取り出します。√n 以下の素数は生成済みなので、primes から stream-take-while で取り出すことが可能です。ここでは√n のかわりに条件を x * x <= n としています。あとは、関数 every を使って、取り出した素数で n が割り切れないことを確認するだけです。
それでは実行してみましょう。
gosh> (stream-take primes 25) (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) gosh> (stream-ref primes 99) 541 gosh> (stream-ref primes 500) 3581
100 以下の素数は全部で 25 個あります。また、100 番目の素数は 541 になります。Scheme のリストは 0 から数えるので、(stream-ref primes 99) で 100 番目の素数になります。
実行時間ですが、stream-ref で 1001 番目の素数を求めてみました。実行環境は Windows 7, Core i7-2670QM 2.20GHz, Gauche version 0.9.5 です。
gosh> (define ps (sieve (iterate (lambda (x) (+ x 1)) 2))) ps gosh> (time (stream-ref ps 1000)) ;(time (stream-ref ps 1000)) ; real 2.390 ; user 1.762 ; sys 1.170 7927 gosh> (time (stream-ref primes 1000)) ;(time (stream-ref primes 1000)) ; real 0.034 ; user 0.047 ; sys 0.000 7927
sieve よりも primes のほうが高速になりました。興味のある方はいろいろ試してみてください。