「Scheme入門」（湯浅太一 著：岩波書店 1991年）をGaucheで読む（２）

2506 ワード
Scheme lisp Gauche Scheme テキストリンク

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.ボケとネタが足りないので後で編集したいです。