Scheme - 階層データ構造と閉包(両替の計算プログラム(通貨を簡単に変えられる版)、ドット末尾記法(dotted-tail notation))

計算機プログラムの構造と解釈
Gerald Jay Sussman, Julie Sussman
Harold Abelson (原著) 和田 英一 (翻訳)

開発環境

• OS X Lion - Apple(OS)
• Emacs、BBEdit - Bare Bones Software, Inc. (Text Editor)
• プログラミング言語: MIT/GNU Scheme

計算機プログラムの構造と解釈(Gerald Jay Sussman(原著)、Julie Sussman(原著)、Harold Abelson(原著)、和田 英一(翻訳)、ピアソンエデュケーション)の2(データによる抽象の構築)、2.2(階層データ構造と閉包)、2.2.1(並びの表現)の問題 2.19、問題 2.20を解いてみる。

その他参考書籍

• Instructor's Manual to Accompany Structure & Interpretation of Computer Programs

問題 2.19

コード

sample.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 (first-denomination coin-values)
  (car coin-values))

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

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

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

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

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

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

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

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

リスト coin-valuesの順を入れ替えても、計算の順序が変わるだけであって、再帰によって全ての場合が計算されるのには変わらないから、ccの答えに影響はない。

確認。

入出力結果(Terminal, REPL(Read, Eval, Print, Loop))

1 ]=> (cc 100 us-coins)

;Value: 292

1 ]=> (cc 100 us-coins-1)

;Value: 292

1 ]=> (cc 100 us-coins-2)

;Value: 292

1 ]=> (cc 50 uk-coins)

;Value: 5127

1 ]=> (cc 50 uk-coins-1)

;Value: 5127

1 ]=> (cc 50 uk-coins-2)

;Value: 5127

問題 2.20

コード

sample.scm

(define (same-parity a . z)
  (define filter (if (even? a)
                     (lambda (x) (even? x))
                     (lambda (x) (not (even? x)))))
  (define (inner items result)
    (if (null? items)
        result
        (if (filter (car items))
            (inner (cdr items) (append result (list (car items))))
            (inner (cdr items) result))))
  (inner z (list a)))

入出力結果(Terminal, REPL(Read, Eval, Print, Loop))

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

;Value 2: (1 3 5 7)

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

;Value 3: (2 4 6)