Scheme - 記号データ(例: 集合の表現(順序づけられたリストとしての集合))

計算機プログラムの構造と解釈
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.3(記号データ)、2.3.3(例: 集合の表現)、順序づけられたリストとしての集合の問題 2.61、問題 2.62を解いてみる。

その他参考書籍

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

問題 2.61、問題 2.62

コード

sample.scm

(define (element-of-set? x set)
  (cond ((null? set) false)
        ((= x (car set)) true)
        ((< x (car set)) false)
        (else (element-of-set? x (cdr set)))))

; 順序づけられてリストとしての集合の場合は、
; 集合の先頭の要素より小さかったら、残りの集合は先頭より大きいので、
; 加えたい要素は残りの集合に存在しない(残りの要素と重複しないか確認しないでいい)ので、
; その時点で集合に加えることができるという利点がある
(define (adjoin-set x set)
  (if (null? set)
      (cons x '())
      (let ((a (car set)))
        (cond ((= x a) set)
              ((< x a) (cons x set))
              (else (cons a (adjoin-set x (cdr set))))))))

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

(define empty-set '())

(define set '(1 2 3 4 5 6 7 8 9 10))

(define even-set '(2 4 6 8 10))

(define odd-set '(1 3 5 7 9))

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

1 ]=> (union-set set0 set1)

;Value 2: (1 2 3 4 5)

1 ]=>  (union-set set0 set2)

;Value 3: (4 5 6 7 8 9 10)

1 ]=>  (union-set set1 set0)

;Value 4: (1 2 3 4 5)

1 ]=>  (union-set set1 set2)

;Value 5: (1 2 3 4 5 6 7 8 9 10)

1 ]=>  (union-set set2 set0)

;Value 6: (4 5 6 7 8 9 10)

1 ]=>  (union-set set2 set1)

;Value 7: (6 7 8 9 10 1 2 3 4 5)

1 ]=> (union-set set1 set2)

;Value 8: (1 2 3 4 5 6 7 8 9 10)

1 ]=>  (union-set set2 set2)

;Value 3: (4 5 6 7 8 9 10)

1 ]=>  (union-set set1 set1)

;Value 2: (1 2 3 4 5)

1 ]=>  (union-set set0 set0)

;Value: ()