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.62.を解いてみる。

その他参考書籍

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

問題 2.62.

コード(BBEdit, Emacs)

sample.scm

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

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

(define (union-set set1 set2)
  (cond ((null? set1) set2)
        ((null? set2) set1)
        ((= (car set1)
            (car set2))
         (union-set set1 (cdr set2)))
        ((< (car set1)
            (car set2))
         (cons (car set1)
               (union-set (cdr set1)
                          set2)))
        (else
         (cons (car set2)
               (union-set set1
                          (cdr set2))))))

(define set0 '())
(define set1 '(1))
(define set2 '(1 2 3 4 5))
(define set3 '(6 7 8 9 10))
(define set4 '(2 4 6 8 10))
(define set5 '(1 3 5 7 9))
(define sets (list set0 set1 set2 set3 set4 set5))

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

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

$ ./sample.scm
(union-set () ()) = ()
(union-set () (1)) = (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 () (2 4 6 8 10)) = (2 4 6 8 10)
(union-set () (1 3 5 7 9)) = (1 3 5 7 9)
(union-set (1) ()) = (1)
(union-set (1) (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) (2 4 6 8 10)) = (1 2 4 6 8 10)
(union-set (1) (1 3 5 7 9)) = (1 3 5 7 9)
(union-set (1 2 3 4 5) ()) = (1 2 3 4 5)
(union-set (1 2 3 4 5) (1)) = (1 2 3 4 5)
(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) (2 4 6 8 10)) = (1 2 3 4 5 6 8 10)
(union-set (1 2 3 4 5) (1 3 5 7 9)) = (1 2 3 4 5 7 9)
(union-set (6 7 8 9 10) ()) = (6 7 8 9 10)
(union-set (6 7 8 9 10) (1)) = (1 6 7 8 9 10)
(union-set (6 7 8 9 10) (1 2 3 4 5)) = (1 2 3 4 5 6 7 8 9 10)
(union-set (6 7 8 9 10) (6 7 8 9 10)) = (6 7 8 9 10)
(union-set (6 7 8 9 10) (2 4 6 8 10)) = (2 4 6 7 8 9 10)
(union-set (6 7 8 9 10) (1 3 5 7 9)) = (1 3 5 6 7 8 9 10)
(union-set (2 4 6 8 10) ()) = (2 4 6 8 10)
(union-set (2 4 6 8 10) (1)) = (1 2 4 6 8 10)
(union-set (2 4 6 8 10) (1 2 3 4 5)) = (1 2 3 4 5 6 8 10)
(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) (2 4 6 8 10)) = (2 4 6 8 10)
(union-set (2 4 6 8 10) (1 3 5 7 9)) = (1 2 3 4 5 6 7 8 9 10)
(union-set (1 3 5 7 9) ()) = (1 3 5 7 9)
(union-set (1 3 5 7 9) (1)) = (1 3 5 7 9)
(union-set (1 3 5 7 9) (1 2 3 4 5)) = (1 2 3 4 5 7 9)
(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) (2 4 6 8 10)) = (1 2 3 4 5 6 7 8 9 10)
(union-set (1 3 5 7 9) (1 3 5 7 9)) = (1 3 5 7 9)
$