exercise 3.63

こういう「説明せよ！」というタイプの問題は単純にコード書くより時間がかかる・・・orz

問題は

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

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

の違いを言ってみろ。ってことですな。

とりあえずimproveが何回呼ばれたかに着目してみる。
ということで、上のコードを変更して

(define count 0)
(define (sqrt-stream x)
  (cons-stream 1.0
               (stream-map (lambda (guess)
                             (set! count (+ count 1))
                             (sqrt-improve guess x))
                           (sqrt-stream x))))

(define (sqrt-stream x)
  (define guesses
    (cons-stream 1.0
                 (stream-map (lambda (guess)
                               (set! count (+ count 1))
                               (sqrt-improve guess x))
                             guesses)))
  guesses)

という代入を使った（大丈夫かな・・・）コードで試してみる。

で、結果だが。

1. メモ化あり＋guessesとか使ってる奴
　→n番目を参照するのにimproveが n 回呼ばれる。
2.他の3つ。(メモ化あり+guesses使ってないのと、メモ化無しでguesses使ってるのと使ってないのと二つ)
　→n番目を参照するのにimproveが n*(n+1)/2 回呼ばれる。

というのになった。（結果コピペするべきかな・・・）
ちなみにn番目ってのは0から数えて。要するにstream-refつかってるんですな。

1はメモ化してるので当たり前。
初期値(0番)からn回更新されているので、improveもn回呼ばれてるはず。また、それ以上はメモ化のおかげで呼び出されないはず。

2は、よーするにメモ化が行われていないので、
n番目までに呼ばれるimproveの回数をS(n)とでもすれば、
S(n+1) = S(n) + n +1(ただしS(0)=0)
みたいになってるので、結局
S(n) = n*(n+1)/2
ってことでいいのかな。

ちなみにguesses使ってない方は、
cons-streamのcdrの部分で毎回新しくストリームを作っているので、メモ化ありのdelayを用いても、実質的にはメモ化が行われてない・・・。と言う感じかな

しかし、なんつーか結構理解が曖昧だな。もう少し動きをじっくりと追いかけたほうが良いのかな？