Hatena::Groupsicp

SICP読書記

 | 

2009-11-22

問題3.14

問題3.14 - SICP読書記 を含むブックマーク はてなブックマーク - 問題3.14 - SICP読書記

(use slib)
(require 'trace)

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

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

(define w (mystery v))

(print w)

(trace loop)を入れてみた。

(mystery v)を評価したときのtraceは以下の通り

CALL loop (a b c d) ()
 CALL loop (b c d) (a)
  CALL loop (c d) (b a)
   CALL loop (d) (c b a)
    CALL loop () (d c b a)
    RETN loop (d c b a)
   RETN loop (d c b a)
  RETN loop (d c b a)
 RETN loop (d c b a)
RETN loop (d c b a)

つまり、最終的にreverseと同じ値を返す。

(set-cdr! x y)ってのは、要するにyの先頭にxをつけちゃってxとするっていう操作。それを末尾再帰でループしているのはreverse以外の何者でもない。

違うのは、最終的にmysteryの引数を壊しちゃうってこと。

最後で(print v)すると

(a)

になっちゃう。

 |