今回は,2,3,5 のみを素因数として持つような数のみによって構成される,昇順かつ重複のない無限ストリームを構成します.ヒントとしては,以下のような無限ストリーム S を構成すれば良いとされていました.
- S は 1 から始まる
- (scale-stream S 2) は S の要素
- (scale-stream S 3), (scale-stream S 5) も S の要素
- S の要素は上記のものだけ
複数の無限ストリームを重複なく,かつ昇順に並べた無限ストリームを返す関数 merge は既に用意されています.
(define (merge s1 s2) (cond ((stream-null? s1) s2) ((stream-null? s2) s1) (else (let ((s1car (stream-car s1)) (s2car (stream-car s2))) (cond ((< s1car s2car) (cons-stream s1car (merge (stream-cdr s1) s2))) ((> s1car s2car) (cons-stream s2car (merge s1 (stream-cdr s2)))) (else (cons-stream s1car (merge (stream-cdr s1) (stream-cdr s2)))))))))
そこで,ぼくがしなければならないのは,S を定義することだけ.こんなの簡単じゃんと思って,以下のように S を定義すると,CPU 使用率が 100% になって返ってこなくなってしまいました.
(define S (cons-stream 1 (merge (scale-stream S 2) (merge (scale-stream S 3) (scale-stream S 5)))))
こちらの定義であればうまくいきます.まだ理由まで詰められていません.つかれた.
(define S (merge (cons-stream 1 (scale-stream S 2)) (merge (cons-stream 1 (scale-stream S 3)) (cons-stream 1 (scale-stream S 5)))))
実際にこの無限ストリームの先頭 50 要素をダンプしてみます.
(define (dump-stream s num) (define (dump-stream-n s idx) (if (< idx num) (begin (display (stream-ref s idx)) (display ", ") (dump-stream-n s (+ idx 1))) 'done)) (dump-stream-n s 0)) (dump-stream S 50) ; 1, 2, 3, 4, 5, 6, 9, 10, 12, 15, 18, 27, 30, 36, 45, 54, 81, 90, 108, 135, 162, 243, 270, 324, 405, 486, 729, 810, 972, 1215, 1458, 2187, 2430, 2916, 3645, 4374, 6561, 7290, 8748, 10935, 13122, 19683, 21870, 26244, 32805, 39366, 59049, 65610, 78732, 98415, done
うまくいってるみたいですね!