3.3.1 Mutable List Structure

3.12

(define x (list 'a 'b))
(define y (list 'c 'd))
(define z (append x y))
z
; => (a b c d)
(cdr x)
; => (b)
(define w (append! x y))
w
; => (a b c d)
(cdr x)
; => (b c d)

3.13

(define (last-pair x)
  (if (null? (cdr x))
    x
    (last-pair (cdr x))))
(define (make-cycle! x)
  (set-cdr! (last-pair x) x)
  x)

3.14

これは何？という問題。

(define (mystery x)
  (define (loop x y)
    (if (null? x)
      y
      (let ((temp (cdr x)))
        (set-cdr! x y)
        (loop temp x))))
  (loop x '()))

reverse!的なことをするみたい。

3.15

省略。

3.16

データ構造中のペアの数を数える(はず)の次の関数が、正しい結果を返さない例を挙げる。

(define (count-pairs x)
  (if (not (pair? x))
    0
    (+ (count-pairs (car x))
       (count-pairs (cdr x))
       1)))

(define x '((a . b) . (c . d)))
(count-pairs x)
; => 3
(define y '((a . b) . (c . d)))
(set-car! (car y) (cdr y))
; y = ((#0=(c . d) . b) . #0#)
(count-pairs y)
; => 4
(define z '((a . b) . (c . d)))
(set-car! (car z) (cdr z))
(set-car! (cdr z) (car z))
; z = (#0=(#1=(#0# . d) . b) . #1#)
(count-pairs z)
; => 返ってこない

#n=... #n#というのはデータ構造がループしてるときにそのデータをwriteすると得られる。始めて見たときはまったく理解できなかった。
ついで。FirefoxのJavaScriptでもこうやったら出てくる。

var a = []; a.push(a);
a.toSource();
// => "#1=[#1#]"

3.17 (3.16のを正しく動作するように)

(define (count-pairs x)
  (define (has? set x)
    (cond ((null? set) #f)
          ((eq? (car set) x) #t)
          (else (has? (cdr set) x))))
  (define (count-distinct-pairs x seen)
    (if (not (pair? x))
      0
      (let ((car-item (car x))
            (cdr-item (cdr x)))
        (let ((updated-seen (cons car-item (cons cdr-item seen))))
          (+ (if (has? seen car-item)
               0
               (count-distinct-pairs car-item updated-seen))
             (if (has? seen cdr-item)
               0
               (count-distinct-pairs cdr-item updated-seen))
             1)))))
  (count-distinct-pairs x '()))

3.18 (データ構造が循環しているかどうか判定する関数)

(define (cycle-list? lis)
  (define (has? set x)
    (cond ((null? set) #f)
          ((eq? (car set) x) #t)
          (else (has? (cdr set) x))))
  (define (check-next l seen)
    (cond ((null? l) #f)
          ((has? seen l) #t)
          (else (check-next (cdr l) (cons l seen)))
          ))
  (check-next (cdr lis) (list lis)))

以下のデータを検証用に使った。

(define a* (make-cycle! '(a a a a)))
; a* = #0=(a a a a . #0#)
(define b* '(b b b b))
(make-cycle! (cdr b*))
; b* = (b . #0=(b b b . #0#))

3.19 (3.18を改変して、定数空間しか消費しないように)

(define (cycle-list? lis)
  (define (cycle-list-iter p i q j)
    (cond ((null? p) #f)
          ((eq? p q) (or (not (= i j))
                         (cycle-list-iter (cdr p) (+ i 1) lis 0)))
          (else      (cycle-list-iter p i (cdr q) (+ j 1)))))
  (cycle-list-iter lis 0 lis 0))

あんまり綺麗じゃないなぁ。
やっとここまで来た。(#scheme-jpにはじめて行ったとき、この問題が話題になってたようだったので)