2006/07/25

Gauche のストリームと MIT Scheme のストリームがじゃっかん違う?
SICP の Ex. 3.56 は、「2,3,5以外の素因数を持たない整数全体の集合を以下の stream-scale と merge を使って求めろ」という問題。
(define (stream-scale stream factor)
(stream-map (lambda (x) (* x factor)) stream))

(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)
(stream-cons s1car
(merge (stream-cdr s1) s2)))
((> s1car s2car)
(stream-cons s2car
(merge s1 (stream-cdr s2))))
(else
(stream-cons s1car
(merge (stream-cdr s1)
(stream-cdr s2)))))))))

素直に解答すると、こうなる。
(define S (stream-cons 
1
(merge (stream-scale S 2)
(merge (stream-scale S 3)
(stream-scale S 5)))))

ところが Gauche(0.8.6)だと、この S を見に行くと止まってしまうようだ。先頭の 1つしか決まっていないストリームを merge にぶちこんで再帰することに問題があるらしい。深さに応じてストリームの先頭付近を具体的にしてやると、意図したストリームに近いものを求めてくれる。
(define S (stream-cons 
1
(merge (stream-scale (stream-cons 0 S) 2)
(merge (stream-scale (stream-cons 0 (stream-cons 0 S)) 3)
(stream-scale (stream-cons 0 (stream-cons 0 S)) 5)))))

gosh> (stream->list (stream-take S 100))
(1 0 0 2 0 0 3 0 0 4 0 0 5 0 0 6 0 0 8 0 0 9 0 0 10 0 0 12 0 0 15 0
0 16 0 0 18 0 0 20 0 0 24 0 0 25 0 0 27 0 0 30 0 0 32 0 0 36 0 0 40
0 0 45 0 0 48 0 0 50 0 0 54 0 0 60 0 0 64 0 0 72 0 0 75 0 0 80 0 0
81 0 0 90 0 0 96 0 0 100)

0を無視すれば正しい集合が求まっている。
しっかし、こういうひっかけがあるときはヒントが書いてありそうなもんだ。つまりたぶんこれはなにかおかしい。そこで MIT Scheme で試してみると、あっさり普通に求まった。
1 ]=> 
(define S (cons-stream
1
(merge (stream-scale S 2)
(merge (stream-scale S 3)
(stream-scale S 5)))))

;Value: s

1 ]=> (stream-ref S 1)

;Value: 2

1 ]=> (stream-ref S 4)

;Value: 5

1 ]=> (stream-ref S 100)

;Value: 1600

なんでだろう。考えられるのは、Gauche と MIT Scheme の stream-cdr が違いそうだってことだろうなあ。また何か勘違いしている可能性もあるので、もっとよく考えること。

No comments :