P114の[5.3.6]の「ゲーム木」の解答はP123とP124に二通りある。
前者
(define (nim n)
(case n
((0) (list 0))
((1) (list 1 (nim 0)))
((2) (list 2 (nim 1) (nim 0)))
(else (list n
(nim (- n 1))
(nim (- n 2))
(nim (- n 3))
)
)
)
)
(「Scheme入門」P123より引用)
ではたとえば
(nim 4)
を評価すると
gosh> (4 (3 (2 (1 (0)) (0)) (1 (0)) (0)) (2 (1 (0)) (0)) (1 (0)))
*書き直すと
(4 (3 (2 (1 (0))
(0))
(1 (0))
(0))
(2 (1 (0))
(0))
(1 (0)))
*こう。
返ってくるのだが
P124の、より効率的なコード
(define (nim2 n)
(case n
((0) (list 0))
((1) (list 1 (nim2 0)))
((2) (list 2 (nim2 1) (nim2 0)))
(else (let ((x (nim2 (- n 1))))
(list n
x
(cadr x)
(caddr x))
)
)
)
)
にすると(ただしnimをnim2に書き換えて引用)
gosh> (4 (3 #0=(2 #1=(1 (0)) #2=(0)) #1# #2#) #0# #1#)
と返ってくる。
前回の(1.5)で言及しているように、Gaucheでは同一のオブジェクトを使いまわす(言葉悪いな)場合は
#
を使って冗長を避けるので、上述のリストは
gosh> (4 (3 (2 (1 (0)) (0)) (1 (0)) (0)) (2 (1 (0)) (0)) (1 (0)))
と同一である。
試しに
(define y
'(3 (2 (1 (0))
(0))
(1 (0))
(0))
)
とリストを作った後(リストを作るというかリストをクオートした後)
(list (+ (car y) 1)
y
(cadr y)
(caddr y)
)
とすると同じく
gosh> (4 (3 #0=(2 (1 (0)) (0)) #1=(1 (0)) (0)) #0# #1#)
と返ってきます。
図で表すと
なので、結果
と同じことになるわけですな。
PS.ボケとネタが足りないので後で編集したいです。