2006/04/06

かと思うと、exercise 3.19 のように、(This requires a very clever idea) と補足されているような「とんち問題」もある。問題は、巡回リストかどうか判定するプロシージャを set! とか使わないで書け、というもの。

clever idea がなくても、無限集合の重要な性質を知っていればすぐに思い付く方法がある。その性質というのは、「無限集合は、その部分集合と濃度が等しい」というもの。集合の濃度っていうのは、要素の個数くらいの意味。「無限の個数ってなんだよ」って開き直ったら負けで、「一部分だけ取り出してきたのに元と同じくらいたくさん詰まっているのを無限っていうことにしようぜ、逆に」というのが数学なんだと思う(適当)。なんにせよ、clever idea があるとしたら、それは集合論を思い付いた Cantor のものだ。

とにかく、巡回リストも無限集合みたいなもんなので、その一部分が元のリストと同じだけの要素を持っているっていう性質がある。とくに巡回リストの場合は、cdr を取っていくと、そのうち元のリストと同一(eq? の意味で)になる。必ず。

そこで、こう書ける。
;; ex. 3.19
(define (cycle? x)
(if (null? (cdr x))
#f
(let R ((y (cdr x)))
(cond ((null? y) #f)
((eq? x y) #t)
(else (R (cdr y)))))))

gosh> x
#0=(a b c . #0#)
gosh> (cycle? x)
#t


昨日も今日も定時で帰ってきたので、なんかハイだ。

1 comment :

Anonymous said...

gosh> (define x '(1 2 3))
x
gosh> (set! (cddr x) x)
#<undef>
gosh> (define x (cons 0 x))
x
gosh> x
(0 . #0=(1 2 . #0#))
gosh> (cycle? x)
...