理系学生日記

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

問題 3-63 (3.5.3 Exploiting the Stream Paradigm)

次に示す,無限ストリームを使って平方根を計算する sqrt-stream の二つの実装は何が違うのか,という問題.後者の方がわりと直感的だけど,実際に SICP の本文で用いられているのは前者である.

(define (sqrt-stream x)
  (define guesses
    (cons-stream 1.0
                 (stream-map (lambda (guess)
                               (sqrt-improve guess x))
                             guesses)))
  guesses)

(define (sqrt-stream x)
  (cons-stream 1.0
               (stream-map (lambda (guess)
                             (sqrt-improve guess x))
                           (sqrt-stream x))))

前者は無限ストリームの中で一度計算した部分を guesses によって保持している.これはメモ化の効果でもあって,例えば

(define sqrt2 (sqrt-stream 2))
(print (stream-ref sqrt2 20))
(print (stream-ref sqrt2 10))

上で (stream-ref sqrt2 10) のときは,(stream-ref sqrt2 20) で計算した結果が単に使われ,再計算は生じない(はず).

後者の場合だと,毎回無限ストリームが生成されることになる.つまり,

(define sqrt2 (sqrt-stream 2))
(print (stream-ref sqrt2 20))
(print (stream-ref sqrt2 10))

は 2 回無限ストリームが生成され,時間のムダ.ただし (delay ) の実装でメモ化が使われない場合は,前者でも計算結果が保持されないので,毎回の計算が生じてしまう.