LoginSignup
2

More than 5 years have passed since last update.

「Scheme入門」(湯浅太一 著:岩波書店 1991年)をGaucheで読む(2)

Last updated at Posted at 2016-04-26

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#)
と返ってきます。

図で表すと

nim-3.png

なので、結果

nim-1.png

と同じことになるわけですな。

PS.ボケとネタが足りないので後で編集したいです。

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
2