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.3(記号データ)、2.3.3(例: 集合の表現)、問題 2.59.を解いてみる。

その他参考書籍

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

問題 2.59.

コード(BBEdit, Emacs)

sample.scm

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

;; これまでに書いた手続き
(load "./procedures.scm")

(define (union-set set1 set2)
  (cond ((null? set1) set2)
        ((null? set2) set1)
        ((element-of-set? (car set1)
                          set2)
         (union-set (cdr set1)
                    set2))
        (else (cons (car set1)
                    (union-set (cdr set1)
                               set2)))))

(define s1 '(1 2 3 4 5))
(define s2 '(6 7 8 9 10))
(define s3 '(1 3 5 7 9))
(define s4 '(2 4 6 8 10))
(define s5 '(1 2 4 6 8))
(define s6 '())
(define s7 '(1))
(define sets (list s1 s2 s3 s4 s5 s6 s7))

(for-each (lambda (pair)
            (let ((set1 (car pair))
                  (set2 (cdr pair)))
              (print "(union-set " set1 " " set2 ") = "
                     (union-set set1 set2))))
          (flatmap (lambda (set1)
                     (map (lambda (set2)
                            (cons set1 set2))
                          sets))
                   sets))

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

$ ./sample.scm
(union-set (1 2 3 4 5) (1 2 3 4 5)) = (1 2 3 4 5)
(union-set (1 2 3 4 5) (6 7 8 9 10)) = (1 2 3 4 5 6 7 8 9 10)
(union-set (1 2 3 4 5) (1 3 5 7 9)) = (2 4 1 3 5 7 9)
(union-set (1 2 3 4 5) (2 4 6 8 10)) = (1 3 5 2 4 6 8 10)
(union-set (1 2 3 4 5) (1 2 4 6 8)) = (3 5 1 2 4 6 8)
(union-set (1 2 3 4 5) ()) = (1 2 3 4 5)
(union-set (1 2 3 4 5) (1)) = (2 3 4 5 1)
(union-set (6 7 8 9 10) (1 2 3 4 5)) = (6 7 8 9 10 1 2 3 4 5)
(union-set (6 7 8 9 10) (6 7 8 9 10)) = (6 7 8 9 10)
(union-set (6 7 8 9 10) (1 3 5 7 9)) = (6 8 10 1 3 5 7 9)
(union-set (6 7 8 9 10) (2 4 6 8 10)) = (7 9 2 4 6 8 10)
(union-set (6 7 8 9 10) (1 2 4 6 8)) = (7 9 10 1 2 4 6 8)
(union-set (6 7 8 9 10) ()) = (6 7 8 9 10)
(union-set (6 7 8 9 10) (1)) = (6 7 8 9 10 1)
(union-set (1 3 5 7 9) (1 2 3 4 5)) = (7 9 1 2 3 4 5)
(union-set (1 3 5 7 9) (6 7 8 9 10)) = (1 3 5 6 7 8 9 10)
(union-set (1 3 5 7 9) (1 3 5 7 9)) = (1 3 5 7 9)
(union-set (1 3 5 7 9) (2 4 6 8 10)) = (1 3 5 7 9 2 4 6 8 10)
(union-set (1 3 5 7 9) (1 2 4 6 8)) = (3 5 7 9 1 2 4 6 8)
(union-set (1 3 5 7 9) ()) = (1 3 5 7 9)
(union-set (1 3 5 7 9) (1)) = (3 5 7 9 1)
(union-set (2 4 6 8 10) (1 2 3 4 5)) = (6 8 10 1 2 3 4 5)
(union-set (2 4 6 8 10) (6 7 8 9 10)) = (2 4 6 7 8 9 10)
(union-set (2 4 6 8 10) (1 3 5 7 9)) = (2 4 6 8 10 1 3 5 7 9)
(union-set (2 4 6 8 10) (2 4 6 8 10)) = (2 4 6 8 10)
(union-set (2 4 6 8 10) (1 2 4 6 8)) = (10 1 2 4 6 8)
(union-set (2 4 6 8 10) ()) = (2 4 6 8 10)
(union-set (2 4 6 8 10) (1)) = (2 4 6 8 10 1)
(union-set (1 2 4 6 8) (1 2 3 4 5)) = (6 8 1 2 3 4 5)
(union-set (1 2 4 6 8) (6 7 8 9 10)) = (1 2 4 6 7 8 9 10)
(union-set (1 2 4 6 8) (1 3 5 7 9)) = (2 4 6 8 1 3 5 7 9)
(union-set (1 2 4 6 8) (2 4 6 8 10)) = (1 2 4 6 8 10)
(union-set (1 2 4 6 8) (1 2 4 6 8)) = (1 2 4 6 8)
(union-set (1 2 4 6 8) ()) = (1 2 4 6 8)
(union-set (1 2 4 6 8) (1)) = (2 4 6 8 1)
(union-set () (1 2 3 4 5)) = (1 2 3 4 5)
(union-set () (6 7 8 9 10)) = (6 7 8 9 10)
(union-set () (1 3 5 7 9)) = (1 3 5 7 9)
(union-set () (2 4 6 8 10)) = (2 4 6 8 10)
(union-set () (1 2 4 6 8)) = (1 2 4 6 8)
(union-set () ()) = ()
(union-set () (1)) = (1)
(union-set (1) (1 2 3 4 5)) = (1 2 3 4 5)
(union-set (1) (6 7 8 9 10)) = (1 6 7 8 9 10)
(union-set (1) (1 3 5 7 9)) = (1 3 5 7 9)
(union-set (1) (2 4 6 8 10)) = (1 2 4 6 8 10)
(union-set (1) (1 2 4 6 8)) = (1 2 4 6 8)
(union-set (1) ()) = (1)
(union-set (1) (1)) = (1)
$