SICP問題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 '()))

この手続きが一般に何をするのか、'(a b c d)を使って考えてみる

(mystery x)
loop呼び出し
x (a b c d) y () temp (b c d)
(set-cdr! x y)
x (a)
loop呼び出し(引数 temp, x)
x (b c d) y (a) temp (c d)
(set-cdr! x y)
x (b a)
loop呼び出し(引数 temp, x)
x (c d) y (b a) temp (d)
(set-cdr! x y)
x (c b a)
loop呼び出し(引数 temp, x)
x (d) y (c b a) temp ()
(set-cdr! x y)
x (d c b a)
loop呼び出し(引数 temp, x)
x () y (d c b a)
→ 終了yを返す。

上で見たようにこれは反転したリストを返す手続きである。
以下に箱とポインタ図を示す
vの定義

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

この時点での箱とポインタ図

v→□□→□□→□□→□■
 　↓　　↓　　↓　　↓
 　a 　　b 　　c 　　d

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

この時点での箱とポインタ図

 　　　　　　　　　　v
 　　　　　　　　　　↓
w→□□→□□→□□→□■
 　↓　　↓　　↓　　↓
 　d 　　c 　　b 　　a