SICP読書録 #21 2.2 階層データと閉包性 - 練習問題 2.20

hiroshi-manabe様の日本語訳を使わせてもらいます。
練習問題等はGaucheで実行。

前回はこちら

2.2 階層データと閉包性

cons手続きによりペアを作れる。ペアの要素はペアであってもいい。

_.scm

gosh> (cons (cons 1 2) (cons 3 4))
((1 . 2) 3 . 4)
gosh> (cons (cons 1 (cons 2 3)) 4)
((1 2 . 3) . 4)
gosh>

こうした性質を閉包性という。閉包性によって階層的なデータ構造が表現できるようになるのだ。

2.2.1 列の表現

consにより、値をいくつも繋げられる。そして、終端の要素として nil を繋げてみる。

_.scm

gosh> (define nil ())
gosh> (cons 1 (cons 2 (cons 3 (cons 4 nil))))
(1 2 3 4)

Schemeでは、これをリストという。

リストを作りたいなら list 手続きを使うほうが便利だ。さらに言うと、car と cdr はそれぞれ、リストの最初の要素と残りの要素を取り出す手続きと見ることができる。

_.scm

gosh> (define one-through-four (list 1 2 3 4))
gosh> (car one-through-four)
1
gosh> (cdr one-through-four)
(2 3 4)
gosh> (car (cdr one-through-four))
2
gosh> (cons 10 one-through-four)
(10 1 2 3 4)
gosh> (cons 5 one-through-four)
(5 1 2 3 4)
gosh>

リスト演算

リストに対する操作を行う手続きをいくつか。

_.scm

; リストからn番目の要素を取り出す
(define (list-ref items n)
  (if (= n 0)
    (car items)
    (list-ref (cdr items) (- n 1))))

; リストの長さを得る（再起プロセス版）
(define (length1 items)
  (if (null? items)
    0
    (+ 1 (length (cdr items )))))

; リストの長さを得る（反復プロセス版）
(define (length2 items)
  (define (length-iter a count)
    (if (null? a)
      count
      (length-iter (cdr a) (+ 1 count ))))

; 2つのリストを結合する
(define (append list1 list2)
  (if (null? list1)
    list2
    (cons (car list1) (append (cdr list1) list2 ))))

練習問題 2.17

リストの最後の要素を返す手続きlast-pairを実装する。

_.scm

(define (last-pair items)
  (if (null? (cdr items))
    (car items)
    (last-pair (cdr items))))

実行結果

_.scm

gosh> (last-pair (list 1 2 3 4))
4

練習問題 2.18

リストの内容を逆順にする手続きreverse。再帰プロセス版と反復プロセス版の両方作ってみよう。

_.scm

; 再帰プロセス
(define (reverse1 items)
  (if (null? items)
    items
    (append (reverse1 (cdr items)) (list (car items)))))

;反復プロセス
(define (reverse2 items)
  (define (reverse-iter i r)
    (if (null? i)
      r
      (reverse-iter (cdr i) (cons (car i) r))))
  (reverse-iter items ()))

練習問題 2.19

前に、与えられた金額がコインの組み合わせ何通りで表現できるかを計算する手続きを作った。この時は、米国の通貨に対応させたが・・・

どんなコインが存在するかは、通貨によって異なる。

_.scm

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

これを引数に渡せるようにしよう。

_.scm

(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)))))

(define (no-more? coin-values) (null? coin-values))
(define (first-denomination coin-values) (car coin-values))
(define (except-first-denomination coin-values) (cdr coin-values))

実行結果。

_.scm

gosh> (cc 100 us-coins)
292
gosh> (cc 100 uk-coins)
104561

練習問題 2.20

ドット記法により可変個引数の手続きを作れる。

_.scm

gosh> (define (f . x) x)
f
gosh> (f 1 2 3)
(1 2 3)

リストの先頭要素と同じ偶奇性を持つ要素を含むリストを返す手続き same-parity を実装する。

_.scm

(define (same-parity . items)
  (define (parity i) (remainder (car i) 2))
  (define (same-parity-rec i p)
    (if (null? i)
      i
      (if (= (parity i) p)
        (cons (car i) (same-parity-rec (cdr i) p))
        (same-parity-rec (cdr i) p))))
  (same-parity-rec items (parity items)))

実行結果。

_.scm

gosh> (same-parity 1 2 3 4 5 6 7)
(1 3 5 7)
gosh> (same-parity 2 3 4 5 6 7)
(2 4 6)