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.59、問題 2.60を解いてみる。

その他参考書籍

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

問題 2.59

コード

sample.scm

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

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

(define set0 '())

(define set1 (list 1 2 3 4 5))

(define set2 (list 4 5 6 7 8 9 10))

入出力結果(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: ()

問題 2.60.

集合を重複を許す表現にした場合、adjoin-setやunion-setの手続きは、element-of-set?によってリストにあるか無いか調べずに良くなるので、効率が良くなる。intersection-setについては、リストset1とset2の長さが重複の無い場合よりも長くなり、element-of-set?で調べるステップ数が増えるので、非効率になる。

重複無し表現より、重複も許可する表現の方が使いたくなる応用は、重複無し表現の場合にelement-of-set?でリストに要素があるかないか調べる必要がある手続きを沢山定義する必要がある場合。

コード

sample.scm

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


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

(define (adjoin-set x set) (cons x set))

(define (union-set set1 set2) (append set1 set2))

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

(define set0 '())

(define set1 (list 2 3 2 2 3 2 1))

(define set2 (list 3 4 3 3 4 3 2))

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

1 ]=> (intersection-set set0 set1)

;Value: ()

1 ]=> (intersection-set set0 set2)

;Value: ()

1 ]=> (intersection-set set0 set0)

;Value: ()

1 ]=> (intersection-set set1 set0)

;Value: ()

1 ]=> (intersection-set set1 set1)

;Value 2: (2 3 2 2 3 2 1)

1 ]=> (intersection-set set1 set2)

;Value 3: (2 3 2 2 3 2)

1 ]=> (intersection-set set2 set0)

;Value: ()

1 ]=> (intersection-set set2 set1)

;Value 4: (3 3 3 3 2)

1 ]=> (intersection-set set2 set2)

;Value 5: (3 4 3 3 4 3 2)

1 ]=> (union-set set0 set0)

;Value: ()

1 ]=> (union-set set0 set1)

;Value 6: (2 3 2 2 3 2 1)

1 ]=> (union-set set0 set2)

;Value 7: (3 4 3 3 4 3 2)

1 ]=> (union-set set1 set0)

;Value 8: (2 3 2 2 3 2 1)

1 ]=>  (union-set set2 set1)

;Value 9: (3 4 3 3 4 3 2 2 3 2 2 3 2 1)

1 ]=> (union-set set2 set2)

;Value 10: (3 4 3 3 4 3 2 3 4 3 3 4 3 2)

1 ]=> (union-set set1 set2)

;Value 11: (2 3 2 2 3 2 1 3 4 3 3 4 3 2)

1 ]=> (union-set set2 set0)

;Value 12: (3 4 3 3 4 3 2)

1 ]=> (union-set set1 set1)

;Value 13: (2 3 2 2 3 2 1 2 3 2 2 3 2 1)