SICP 読み (129) 3.5.1 ストリームは遅延リスト

問題 3.52 のつづき

もうひとつ、メモ化な手続き (memo-proc) で wrap しなかった場合どうなるか、という問い。これは sum に重複して加算されていくのだろうと類推。
まず

(define seq (stream-map accum (stream-enumerate-interval 1 20)))

な時点では sum は 1 になるのは前と同じ。戻ってくるのは (1 . #) か。で次の

(define y (stream-filter even? seq))

でどんな状態になるか、というと stream-cdr から出てくるナニは (2 . #) なので加算すると 3 になってこれは filter には引っ掛からない。次に stream-cdr から出てくるソレは (3 . #) で、加算すると sum は 6 になって filter にカカってきます。で、y に束縛されているリストは (6 . #) になる、と。おそらくこのあたりまでは memo-proc 使うものと同様な動作のはず。
問題は次の

(define z (stream-filter (lambda (x) (= (remainder x 5) 0)) seq)

ですが、seq は (1 . #) で stream-cdr から出てくるのが (8 . #) になるはず。sum はこの時点で 6 になっちゃってるので。リストにすると

(1 8 11 15 20 26)

みたいなカンジのリストになるんでしょうか。最初に filter にカカるソレは 15 なんで z が束縛されるのは (15 . #) になりますか。stream-cdr なナニが中で持っている次に出てくる値 (って言い方微妙) は 5 になりますか。y の場合は 4 で良いのかな。
で、次に出てくる

(stream-ref y 7)

がまたまた厄介。ってかめんどい。ちなみに z を定義した時点で sum の値は 15 になっているので、y が順に評価していく seq の stream-cdr の値はこの時点では

(19 24 30 37 45 54 64 75 87 100 114 129 145 162 180 199 219)

になるのか。フィルタをかけると以下。

(24 30 54 64 100 114 162 180)

ちなみにリストの最初には 6 がいるので正しくはこう。

(6 24 30 54 64 100 114 162 180)

7 番目は 162 ですね。sum の値は 219 になっているはず。次は

(display-stream z)

ですが z が持っている seq の stream-cdr はこうなりますか。

(225 232 240 249 259 270 282 295 309 324 340 357 375 394 414)

出力されるのは

(15 225 240 270 295 340 375)

sum は最終的に 414 になっている模様。

そろそろ動作を確認

確認したいのですが、もう少し。memo-proc を使わないと y や z を操作する度にリストの内容が変わる事になるのかなぁ。例えば

(stream-ref y 7)

を二回評価すると出てくる値が違うのだろうか。これも含め、動作を見てみます。まず、delay を以下のように修正。

(define-syntax delay
 (syntax-rules ()
;   ((_ p) (memo-proc (lambda () p)))))
   ((_ p) (lambda () p))))

で、以下。

gosh> (define sum 0)
sum
gosh> (define (accum x) (set! sum (+ sum x)) sum)
accum
gosh> (define seq (stream-map accum (stream-enumerate-interval 1 20)))
seq
gosh> seq
(1 . #<closure (stream-map stream-map)>)
gosh> sum
1
gosh> (define y (stream-filter even? seq))
y
gosh> y
(6 . #<closure (stream-filter stream-filter)>)
gosh> sum
6
gosh> (define z (stream-filter (lambda (x) (= (remainder x 5) 0)) seq))
z
gosh> z
(15 . #<closure (stream-filter stream-filter)>)
gosh> sum
15
gosh> (stream-ref y 7)
162
gosh> sum
162

げ。違うし。よく考えたら stream-ref は途中で処理を止めるんだったし。てコトは display-stream が出すのと sum の最終値は違ってくるな。

もいちど display-stream

ええと、z が持ってる seq の stream-cdr は (6 . #) なのでリストにすると

(168 175 183 192 202 213 225 238 252 267 283 300 318 337)

で、5 でわり切れるのは

(175 225 300)

display-stream で出てくるのは

(15 175 225 300)

で、sum は 337 になっているはず。で、確認。

gosh> (display-stream z)
15
180
230
305
done
gosh> sum
362
gosh>

む。微妙に違うな。どこでボケてるんだろうか。5 違うとゆーのが何とも言えない風味を醸しだしておりますが。

とほほ

おかしいな、と思いつつ自分で書いてることを遡って見てみると z が持ってる seq の stream-cdr は (6 . #) ではなくて (5 . #) ですね。4 を car から引っ張りだした時点で 15 になって停止している状態でした。やれやれ。
次節以降は書いてある事はとても楽しげなんですが、理解できるんだろうか。(何