SICP問題3.56

SICP

R.Hammingが提起した2, 3, 5以外の素数の因子を持たない整数の数え上げ

  • 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)))))))))

scale-stream手続き(教科書で定義)

(define (scale-stream stream factor)
  (stream-map (lambda (x) (* x factor)) stream))

Sの定義

(define S (cons-stream 1 (merge (scale-stream S 2)
                                (merge (scale-stream S 3)
                                       (scale-stream S 5)))))

テスト

(stream-ref S 0)
; 1
(stream-ref S 1)
; 2
(stream-ref S 2)
; 3
(stream-ref S 3)
; 4
(stream-ref S 4)
; 5
(stream-ref S 5)
; 6
(stream-ref S 6)
; 8
(stream-ref S 7)
; 9
(stream-ref S 8)
; 10
(stream-ref S 9)
; 12
(stream-ref S 10)
; 15
(stream-ref S 11)
; 16
(stream-ref S 12)
; 18

OK