Scheme - データによる抽象の構築(階層データ構造と閉包性(並びの表現(リスト演算(両替の計算のプログラム))))

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

開発環境

• OS X Mavericks - Apple(OS)
• Emacs (CUI)、BBEdit - Bare Bones Software, Inc. (GUI) (Text Editor)
• Scheme (プログラミング言語)
• Gauche (処理系)

計算機プログラムの構造と解釈(Gerald Jay Sussman(原著)、Julie Sussman(原著)、Harold Abelson(原著)、和田 英一(翻訳)、ピアソンエデュケーション、原書: Structure and Interpretation of Computer Programs (MIT Electrical Engineering and Computer Science)(SICP))の2(データによる抽象の構築)、2.2(階層データ構造と閉包性)、2.2.1(並びの表現)、リスト演算、問題 2.19.を解いてみる。

その他参考書籍

• Instructor's Manual to Accompany Structure & Interpretation of Computer Programs
• プログラミングGauche (Kahuaプロジェクト (著), 川合 史朗 (監修), オライリージャパン)

問題 2.19.

コード(BBEdit, Emacs)

count_change.scm

#!/usr/bin/env gosh
;; -*- coding: utf-8 -*-

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

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

(define (count-change amount coin-values)
  (cc amount 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)))))

(define first-denomination car)

(define except-first-denomination cdr)

(define no-more? null?)

;; リストcoin-valuesの順はccの答えには影響は無い
(for-each print
          (map (lambda (coins)
                 (count-change 100 coins))
               (list us-coins
                     us-coins-1
                     us-coins-2
                     us-coins-3)))

(for-each print
          (map (lambda (coins)
                 (count-change 25 coins))
               (list uk-coins
                     uk-coins-1
                     uk-coins-2
                     uk-coins-3)))

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

$ ./count_change.scm 
292
292
292
292
571
571
571
571
$