理系学生日記

おまえはいつまで学生気分なのか

問題3-56 (3.5.2 Infinite Streams)

今回は,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

うまくいってるみたいですね!