問題3.63 – SICP(計算機プログラムの構造と解釈)その154

問題3.63

リーダーマクロを使って sqrt-stream 手続きを調べる。

guesses を使わない場合は、繰り返し sqrt-stream が呼び出されてストリームが生成される。

;; stream の最初の n 個の要素を印字する手続き
(define (stream-head s n)
  (define (iter s n)
    (if (<= n 0)
      'done
      (begin
        (display (stream-car s))
        (newline)
        (iter (stream-cdr s) (- n 1)))))
  (iter s n))

;; guesses を使う場合 (メモライズあり)
(define (sqrt-stream x)
  (define guesses
    (cons-stream 1.0
                 #?=(stream-map (lambda (guess)
                                     (sqrt-improve guess x))
                             guesses)))
  guesses)

(stream-head (sqrt-stream 2) 5)
gosh> #?="(stdin)":60:(stream-map (lambda (guess) (sqrt-improve guess x)) guesses)
#?-    (1.5 . #<closure (memo-proc memo-proc)>)
1.0
1.5
1.4166666666666665
1.4142156862745097
1.4142135623746899
done

;; guesses を使わない場合 (メモライズあり)
(define (sqrt-stream x)
  (cons-stream 1.0
               #?=(stream-map (lambda (guess)
                                   (sqrt-improve guess x))
                           (sqrt-stream x))))

(stream-head (sqrt-stream 2) 5)
gosh> #?="(stdin)":78:(stream-map (lambda (guess) (sqrt-improve guess x)) (sqrt-str ...
#?-    (1.5 . #<closure (memo-proc memo-proc)>)
#?="(stdin)":78:(stream-map (lambda (guess) (sqrt-improve guess x)) (sqrt-str ...
#?-    (1.5 . #<closure (memo-proc memo-proc)>)
#?="(stdin)":78:(stream-map (lambda (guess) (sqrt-improve guess x)) (sqrt-str ...
#?-    (1.5 . #<closure (memo-proc memo-proc)>)
#?="(stdin)":78:(stream-map (lambda (guess) (sqrt-improve guess x)) (sqrt-str ...
#?-    (1.5 . #<closure (memo-proc memo-proc)>)
#?="(stdin)":78:(stream-map (lambda (guess) (sqrt-improve guess x)) (sqrt-str ...
#?-    (1.5 . #<closure (memo-proc memo-proc)>)
1.0
1.5
1.4166666666666665
1.4142156862745097
1.4142135623746899
done

メモライズしなかった場合は、guesses を使う版でも繰り返しストリームが生成されるために二つの版の効率に違いはない。

;; guesses を使う場合 (メモライズなし)
(stream-head (sqrt-stream 2) 5)
gosh> #?="(stdin)":60:(stream-map (lambda (guess) (sqrt-improve guess x)) guesses)
#?-    (1.5 . #<closure (stream-map stream-map)>)
#?="(stdin)":60:(stream-map (lambda (guess) (sqrt-improve guess x)) guesses)
#?-    (1.5 . #<closure (stream-map stream-map)>)
#?="(stdin)":60:(stream-map (lambda (guess) (sqrt-improve guess x)) guesses)
#?-    (1.5 . #<closure (stream-map stream-map)>)
#?="(stdin)":60:(stream-map (lambda (guess) (sqrt-improve guess x)) guesses)
#?-    (1.5 . #<closure (stream-map stream-map)>)
#?="(stdin)":60:(stream-map (lambda (guess) (sqrt-improve guess x)) guesses)
#?-    (1.5 . #<closure (stream-map stream-map)>)
1.0
1.5
1.4166666666666665
1.4142156862745097
1.4142135623746899
done

;; guesses を使わない場合 (メモライズなし)
(stream-head (sqrt-stream 2) 5)
gosh> #?="(stdin)":78:(stream-map (lambda (guess) (sqrt-improve guess x)) (sqrt-str ...
#?-    (1.5 . #<closure (stream-map stream-map)>)
#?="(stdin)":78:(stream-map (lambda (guess) (sqrt-improve guess x)) (sqrt-str ...
#?-    (1.5 . #<closure (stream-map stream-map)>)
#?="(stdin)":78:(stream-map (lambda (guess) (sqrt-improve guess x)) (sqrt-str ...
#?-    (1.5 . #<closure (stream-map stream-map)>)
#?="(stdin)":78:(stream-map (lambda (guess) (sqrt-improve guess x)) (sqrt-str ...
#?-    (1.5 . #<closure (stream-map stream-map)>)
#?="(stdin)":78:(stream-map (lambda (guess) (sqrt-improve guess x)) (sqrt-str ...
#?-    (1.5 . #<closure (stream-map stream-map)>)
1.0
1.5
1.4166666666666665
1.4142156862745097
1.4142135623746899
done
計算機プログラムの構造と解釈
ジェラルド・ジェイ サスマン ジュリー サスマン ハロルド エイブルソン
ピアソンエデュケーション
売り上げランキング: 6542
«
»