問題3-12〜14

｢3.3 可変データでのモデル化｣の節に入りました。
問題3-12で、append!の動きを確認します。

(define (append! x y)
  (set-cdr! (last-pair x) y)
  x)

(define (last-pair x)
  (if (null? (cdr x))
      x
      (last-pair (cdr x))))

(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)

このような結果になることを、実際に実行するまで気づくことができませんでしたが、結果を見て納得しました。appendの方は、xとyの構造自体は変更せず、新しい対を生成しながら二つのリストを合成しています。そのため、append前後において、(cdr x)が指す内容に変化はありません。しかし、append!の方は、xの最後の対のcdrが指す内容を、nullからyに変更しています。そのため、append!実行後は、(cdr x)が指す内容にyのリストも含まれてしまいます。
問題3-13です。下記のようにmake-cycle手続きを定義して、それを利用してみます。

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

(define a (make-cycle (list 'a 'b 'c)))

a  ;=>#0=(a b c . #0#)
(cdr a)  ;=>#0=(b c a . #0#)
(cdr (cdr a))  ;=>#0=(c a b . #0#)
(cdr (cdr (cdr a)))  ;=>#0=(a b c . #0#)

渡されたリストの最後尾の対で、cdrがnullではなく、先頭の対を指すように変更したため、並びが循環するようなデータができました。(last-pair z)を実行すると無限ループに陥ってしまいますが、その原因としては最終判定をcdrがnullとしているからだと思われます。
問題3-14のmysteryを使うと、渡されたリストの並びを反転させることができます。

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

(define v (list 'a 'b 'c 'd))
v  ;=>(a b c d)

(define w (mystery v))
w  ;=>(d c b a)
v  ;=>(a)

最後のvの結果が(a)になってしまう件についてですが、これは、mystery内のloopの最初の(set-car! x y)で、xのcdrがnullに書き替えられてしまうからです。その後、このx自体を指すようなリストが出来上がってくるので、wのリストの最後尾の対と、vが指す対は同一なのではと推察することができます。