やろーじだい

ブログです

Aizu SICP 第 15 回 part 1

時間が空いてしまいましたが 9/4~6 に合宿として旅館に泊まってやりました。現在は11月下旬で会津は雪が降っており嫌になっています。

 合宿での範囲は P103 2.2 階層データと閉包性 ~ P 121 2.2.3 標準インターフェイスとしての例 前までです。 やった範囲が広く練習問題が多かったため記事が長るのと一気に書くとつらいので分けて書きます。合宿自体については別記事に書きました。

lhcpr.hatenablog.com

2.2 階層データと閉包性

ここからはツリーの操作という Lisp において基本となることをやっていく。この辺りの問題は Lisp の本の入門書などにあるような話題や演習が多い。この本の序盤で少し触れたことも多く出てくるが、時間が空いているので少し細かく見ていきたい。

2.2.1 列の表現

プログラムでは変数 nil という値として表されます。

(Page 106).

Gauche では (Racket では未確認) nil が定義されていないので代わりに '() を使うか、またはファイルの先頭で (define nil '()) と宣言しておくと SICP の本のコードをそのまま利用できるので楽だった。 後々出てくると思うが ' によって任意の S 式をデータとして扱うことができる。 '(+ 1 2) の評価値は (+ 1 2) であり、(+ 1 2) の評価値は 3 であるという違いがある。詳細は後程本の中で出てくると思う。

8 この本では、リスト (list) という言葉はリスト終端マーカーで終わるペアのチェーンという意味で使います。それに対して、リスト構造 (list structure) という用語は、リストに限らず、ペアによって作られた任意のデータ構造を指します。

(Page 106).

つまり、終端が nil ('()) で終わるもののみを指してリストと呼ぶ。このこと (構造) は以降の練習問題などでも重要であるので注意したい。

式 (list 1 2 3 4) と、その式を評価した結果として得られるリスト (1 2 3 4) を混同しないように気をつけてください。式 (1 2 3 4) を評価しようとすると、インタプリタは手続き 1 を引数 2, 3, 4 に適用しようとして、 エラーを起こします。

(Page 107).

Lisp のプログラムにおいて括弧を評価する時は、要素の先頭は関数であることが必須であることに注意すること。

length は、反復スタイルで計算することもできます。

(define (length items) (define (length-iter a count) (if (null? a) count (length-iter (cdr a) (+ 1 count)))) (length-iter items 0))

(Page 109).

反復スタイルというのは、 P33 1.2.1 線形再帰と反復で出てきた反復プロセスを指す。反復プロセスの特徴は遅延演算が無いので、後で実行する処理を保存しておく必要がないため効率が良い (この辺りの用語が不安な人は P33~36 を読みなおしておくと良いかもしれません)。

練習問題 2.17

帰り値は一要素のリストであるので注意する。

(define (last-pair lis)
  (let ([cdr-lis (cdr lis)])
    (if (null? cdr-lis)
        lis
        (last-pair cdr-lis))))

(test-section "last-pair")

(test* "" (list 1) (last-pair (list 1)))
(test* "" (list 3) (last-pair (list 1 2 3)))

練習問題 2.18

(define (my-reverse lis)
  (define (%reverse lis acm)
    (if (null? lis)
        acm
        (%reverse (cdr lis) (cons (car lis) acm))))
  (%reverse lis nil))

(test-section "my-reverse")

(test* "" (list 3 2 1) (my-reverse (list 1 2 3)))
(test* "" (list 1) (my-reverse (list 1)))
(test* "" nil (my-reverse nil))

練習問題 2.19

ここでは一度 1.2.2 節に戻りどういう仕様の問題であったかを確認する必要があった。プログラムは以下のようなものだった。

;; 1.2.2 両替パターンの計算 ( cc を cc-old, first-denomination を first-denomination-old という名前に変更している )
(define (count-change amount)
  (cc-old amount 5))

(define (first-denomination-old kinds-of-coins)
  (cond ((= kinds-of-coins 1) 1)
        ((= kinds-of-coins 2) 5)
        ((= kinds-of-coins 3) 10)
        ((= kinds-of-coins 4) 25)
        ((= kinds-of-coins 5) 50)))

(define (cc-old amount kinds-of-coins)
  (cond ((= amount 0) 1)
        ((or (< amount 0) (= kinds-of-coins 0)) 0)
        (else (+ (cc-old amount (- kinds-of-coins 1))
                 (cc-old (- amount (first-denomination-old kinds-of-coins))
                         kinds-of-coins)))))

(test-section "cc-old")

(test* "" 292 (count-change 100))

このプログラムはお金の値を入れたときに、その値になるようなコインの組み合わせが何種類あるかを表示するものだった。上の test の例では 100 セントの場合のコインの組み合わせの数は 292 種類あるという意味になる。

 練習問題に戻ると以下のように既に変更した後のプログラムが書かれている。

(define (cc amount coin-values)
  (cond ((= amount 0) 1)
        ((or (< amount 0) (no-more? coin-values)) 0)
        (else
         (+ (cc amount (except-first-denomination coin-values))
            (cc (- amount
                   (first-denomination coin-values))
                coin-values)))))

問題としては上記のプログラムの中にある未定義の手続きを実装することである。 kinds-of-coins がコインの種類の番号、coin-values がリストであることを考慮して、1.2.2 章のプログラムとの対応を考えていくとわかりやすい。

(= kinds-of-coins 0)                 (no-more? coin-values)
(first-denomination kinds-of-coins)  (first-denomination coin-values)
(- kinds-of-coins 1)                 (except-first-denomination coin-values)

以下は解答。

(define uk-coins (list 100 50 20 10 5 2 1 0.5))

(define (no-more? coin-values)
  (null? coin-values))

(define (except-first-denomination coin-values)
  (cdr coin-values))

(define (first-denomination coin-values)
  (car coin-values))

(define (cc amount coin-values)
  (cond ((= amount 0) 1)
        ((or (< amount 0) (no-more? coin-values)) 0)
        (else
         (+ (cc amount (except-first-denomination coin-values))
            (cc (- amount
                   (first-denomination coin-values))
                coin-values)))))

(test-section "cc")

(test* "" 292 (cc 100 us-coins))

リスト coin-values の順序は、cc によって返される解答に影響を与えるだろうか、それとも与えないだろうか。それはどうしてだろうか。

(Page 111).

元は以下のような順番で定義されている。

(define us-coins (list 50 25 10 5 1))

いくつか試してみる。

gosh> (cc 100 us-coins)
292
gosh> (cc 100 (reverse us-coins))
292
gosh> (cc 100 (list 5 10 50 25 1))
292

変わらないようだが、全てにおいて成り立つのかどうかわからないので、単純に全通り試してみる。Gauche のライブラリ util.cominationspermutations という、リストを受けとって全ての順列を返してくれる関数があるのでこれを利用する。

gosh> (use util.combinations)
gosh> (permutations '(1 2 3))
((1 2 3) (1 3 2) (2 1 3) (2 3 1) (3 1 2) (3 2 1))

gosh> (every (^[x] (= x 292)) (map (^[coins] (cc 100 coins)) (permutations us-coins)))
#t

(permutations us-coins) でコインの種類の全ての順列を生成し、(map (^(coins) (cc 100 coins)) ...) で全ての順列に対して cc を適用して、(every (^(x) (= x 292)) ...) で全ての cc の結果が 292 であるかどうかを調べている。その結果が #t であるのでどんな順番であっても cc の返り値に影響は無いということである。

 任意の順番でも問題にならないことは確認できたが、なぜそうなるのについてが気になるところである。  順序に応じてツリーの構造と葉の数が大きく変わることを確認したので、計算量は違っているはず。だが、どのようにして形式的にこれを表現できるのかがわからなかった。インターネットを探してみたが、基本的に何個か展開して結果を見ると同じになります、ぐらいの確認のみで、証明らしいものはみつからなかった。

誰かわかる人がいましたら教えて下さい。

練習問題 2.20

いまいち意図にあった実装なのかわからないが、リストではなく直接任意の値を渡せることの確認であると理解して実装した。 nums に任意の長さのリストが入ることだけ意識すれば良いだけ?

(define (same-parity . nums)
  (define (get-evens l)
    (cond [(null? l)
           nil]
          [(even? (car l))
           (cons (car l) (get-evens (cdr l)))]
          [else
           (get-evens (cdr l))]))
  (define (get-odds l)
    (cond [(null? l)
           nil]
          [(odd? (car l))
           (cons (car l) (get-odds (cdr l)))]
          [else
           (get-odds (cdr l))]))
  (if (even? (car nums))
      (get-evens nums)
      (get-odds nums)))

(test-section "ex 2.20")

(test* "same-parity1" (list 1) (same-parity 1))
(test* "same-parity2" (list 2) (same-parity 2))
(test* "same-parity3" (list 2 4 6) (same-parity 2 3 4 5 6))
(test* "same-parity4" (list 1 3 5) (same-parity 1 2 3 4 5 6))