Sharing and identity (pp.257-260)

SICP

「同じ」ということの定義。schemeのeq?は単純明快で、ポインタが同じアドレス（実体）を指している物は同じ、、、というコンピュータ的には非常に素直な実装になっています（ポインタ恐怖症の人からしたらいやな表現なんだろうか？）。

(define x (list 'a 'b))
(define z1 (cons x x))

とすると

z1 -> |＋|＋|
       ↓ ↓
x  -> |'a|＋|-> |'b|／|

とz1の car cdr はどちらも同じ物を指すのに対して

(define z2 (cons (list 'a 'b) (list 'a 'b)))

とすると car cdr は内容同じだけど実体（アドレス）の違うものを指すことになります。
この節ではそのことを、与えられたリストのcaarを'wowに書き換える（粋な授業だな）

(define (set-to-wow! x)
  (set-car! (car x) 'wow)
  x)

つうのを定義してz1,z2に適用してます。z1はxの示す同じ実体（アドレス）を共有してますのでcar,cdrのリストの先頭が共に wow!になってしまうが、z2は前だけ、というお話。

追加：

Ex 3.15

略

Ex 3.16

共有または循環があった場合、同じpairなのに何度も数えてしまう、という問題が起こる。例えば 上の例で z1, z2 はそれぞれ 3, 5のペアを持ちますが、この関数だと 両方とも 5になってしまいます(z1の car, cdr それぞれに 2あると数えて 2+2 + (元のcons) 1 = 5)。

Ex 3.17

(define (count-pairs x)
  (let ((trav '()))
    (define (search x)
      (search-symbol x trav))
    (define (inner x)
      (begin (cond ((not (pair? x)) 0)
		   ((search x) 0)
		   (else (begin
			   (set! trav (cons x trav))
			   (+ (inner (car x))
			      (inner (cdr x))
			      1))))))
    (inner x)))

Ex3.19

3.18をこっちで書いてしまった。。。
足の速い人と遅い人でスタートして、足の速い人がゴールにつかずに（循環の場合無いので・・・）ぐるっと回って遅い人に追いついてしまったら循環、という考え方です。

(define (cyclic-check xs) 
  (define (inner fp sp)
    (cond ((null? fp) #f)
	  ((null? (cdr fp)) #f)
	  ((eq? fp sp) #t)
	  (else (inner (cddr fp) (cdr sp)))))
  (inner (cdr xs) xs))

いまいち自身がねーので実験。

(define (make-cyclic xs)
  (begin (set-cdr! (last-cell xs) xs)
	 xs))

gosh> (loop-check '(a b c)) ; サイクル無し
#f
gosh> (loop-check (make-cyclic '(a b c))) ; サイクル
#t
gosh> (loop-check (append '(1 2 3) (make-cyclic '(a b c))))　; 後がサイクル
#t

実は何度か循環リストを「表示」してしまってscheme-bufferを殺すことになったヨ　(　´∀｀)σ)Д｀)