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

その他参考書籍

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

問題 2.60.

コード(BBEdit, Emacs)

set2.scm

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

(load "./procedures.scm")

;; 要素の重複を許す集合の表現
;; 重複がある場合は、調べる要素数が多くなり非効率になる場合がある
(define (element-of-set? x set)
  (cond ((null? set) false)
        ((equal? x
                 (car set))
         true)
        (else
         (element-of-set? x
                          (cdr set)))))

;; 重複の確認の必要がなくなるので効率よくなる
(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 s0 '())
(define s1 '(1))
(define s2 '(1 2))
(define s2 '(1 2 1 2))
(define s3 '(1 3 5 7 9 1 3))
(define s4 '(2 4 6 2 4))
(define s5 '(1 2 3 4 5))
(define sets (list s1 s2 s3 s4 s5))

(for-each (lambda (pair)
            (let ((set1 (car pair))
                  (set2 (cdr pair)))
              (print "(element-of-set? 5 " set1 ") = "
                     (element-of-set? 5 set1)
                     "\n(adjoin-set 100 " set1 ") = "
                     (adjoin-set 100 set1)
                     "\n(union-set " set1 " " set2 ") = "
                     (union-set set1 set2)
                     "\n(intersection-set " set1 " " set2 ") = "
                     (intersection-set set1 set2))))
          (flatmap (lambda (set1)
                     (map (lambda (set2)
                            (cons set1 set2))
                          sets))
                   sets))

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

$ ./set2.scm 
(element-of-set? 5 (1)) = #f
(adjoin-set 100 (1)) = (100 1)
(union-set (1) (1)) = (1 1)
(intersection-set (1) (1)) = (1)
(element-of-set? 5 (1)) = #f
(adjoin-set 100 (1)) = (100 1)
(union-set (1) (1 2 1 2)) = (1 1 2 1 2)
(intersection-set (1) (1 2 1 2)) = (1)
(element-of-set? 5 (1)) = #f
(adjoin-set 100 (1)) = (100 1)
(union-set (1) (1 3 5 7 9 1 3)) = (1 1 3 5 7 9 1 3)
(intersection-set (1) (1 3 5 7 9 1 3)) = (1)
(element-of-set? 5 (1)) = #f
(adjoin-set 100 (1)) = (100 1)
(union-set (1) (2 4 6 2 4)) = (1 2 4 6 2 4)
(intersection-set (1) (2 4 6 2 4)) = ()
(element-of-set? 5 (1)) = #f
(adjoin-set 100 (1)) = (100 1)
(union-set (1) (1 2 3 4 5)) = (1 1 2 3 4 5)
(intersection-set (1) (1 2 3 4 5)) = (1)
(element-of-set? 5 (1 2 1 2)) = #f
(adjoin-set 100 (1 2 1 2)) = (100 1 2 1 2)
(union-set (1 2 1 2) (1)) = (1 2 1 2 1)
(intersection-set (1 2 1 2) (1)) = (1 1)
(element-of-set? 5 (1 2 1 2)) = #f
(adjoin-set 100 (1 2 1 2)) = (100 1 2 1 2)
(union-set (1 2 1 2) (1 2 1 2)) = (1 2 1 2 1 2 1 2)
(intersection-set (1 2 1 2) (1 2 1 2)) = (1 2 1 2)
(element-of-set? 5 (1 2 1 2)) = #f
(adjoin-set 100 (1 2 1 2)) = (100 1 2 1 2)
(union-set (1 2 1 2) (1 3 5 7 9 1 3)) = (1 2 1 2 1 3 5 7 9 1 3)
(intersection-set (1 2 1 2) (1 3 5 7 9 1 3)) = (1 1)
(element-of-set? 5 (1 2 1 2)) = #f
(adjoin-set 100 (1 2 1 2)) = (100 1 2 1 2)
(union-set (1 2 1 2) (2 4 6 2 4)) = (1 2 1 2 2 4 6 2 4)
(intersection-set (1 2 1 2) (2 4 6 2 4)) = (2 2)
(element-of-set? 5 (1 2 1 2)) = #f
(adjoin-set 100 (1 2 1 2)) = (100 1 2 1 2)
(union-set (1 2 1 2) (1 2 3 4 5)) = (1 2 1 2 1 2 3 4 5)
(intersection-set (1 2 1 2) (1 2 3 4 5)) = (1 2 1 2)
(element-of-set? 5 (1 3 5 7 9 1 3)) = #t
(adjoin-set 100 (1 3 5 7 9 1 3)) = (100 1 3 5 7 9 1 3)
(union-set (1 3 5 7 9 1 3) (1)) = (1 3 5 7 9 1 3 1)
(intersection-set (1 3 5 7 9 1 3) (1)) = (1 1)
(element-of-set? 5 (1 3 5 7 9 1 3)) = #t
(adjoin-set 100 (1 3 5 7 9 1 3)) = (100 1 3 5 7 9 1 3)
(union-set (1 3 5 7 9 1 3) (1 2 1 2)) = (1 3 5 7 9 1 3 1 2 1 2)
(intersection-set (1 3 5 7 9 1 3) (1 2 1 2)) = (1 1)
(element-of-set? 5 (1 3 5 7 9 1 3)) = #t
(adjoin-set 100 (1 3 5 7 9 1 3)) = (100 1 3 5 7 9 1 3)
(union-set (1 3 5 7 9 1 3) (1 3 5 7 9 1 3)) = (1 3 5 7 9 1 3 1 3 5 7 9 1 3)
(intersection-set (1 3 5 7 9 1 3) (1 3 5 7 9 1 3)) = (1 3 5 7 9 1 3)
(element-of-set? 5 (1 3 5 7 9 1 3)) = #t
(adjoin-set 100 (1 3 5 7 9 1 3)) = (100 1 3 5 7 9 1 3)
(union-set (1 3 5 7 9 1 3) (2 4 6 2 4)) = (1 3 5 7 9 1 3 2 4 6 2 4)
(intersection-set (1 3 5 7 9 1 3) (2 4 6 2 4)) = ()
(element-of-set? 5 (1 3 5 7 9 1 3)) = #t
(adjoin-set 100 (1 3 5 7 9 1 3)) = (100 1 3 5 7 9 1 3)
(union-set (1 3 5 7 9 1 3) (1 2 3 4 5)) = (1 3 5 7 9 1 3 1 2 3 4 5)
(intersection-set (1 3 5 7 9 1 3) (1 2 3 4 5)) = (1 3 5 1 3)
(element-of-set? 5 (2 4 6 2 4)) = #f
(adjoin-set 100 (2 4 6 2 4)) = (100 2 4 6 2 4)
(union-set (2 4 6 2 4) (1)) = (2 4 6 2 4 1)
(intersection-set (2 4 6 2 4) (1)) = ()
(element-of-set? 5 (2 4 6 2 4)) = #f
(adjoin-set 100 (2 4 6 2 4)) = (100 2 4 6 2 4)
(union-set (2 4 6 2 4) (1 2 1 2)) = (2 4 6 2 4 1 2 1 2)
(intersection-set (2 4 6 2 4) (1 2 1 2)) = (2 2)
(element-of-set? 5 (2 4 6 2 4)) = #f
(adjoin-set 100 (2 4 6 2 4)) = (100 2 4 6 2 4)
(union-set (2 4 6 2 4) (1 3 5 7 9 1 3)) = (2 4 6 2 4 1 3 5 7 9 1 3)
(intersection-set (2 4 6 2 4) (1 3 5 7 9 1 3)) = ()
(element-of-set? 5 (2 4 6 2 4)) = #f
(adjoin-set 100 (2 4 6 2 4)) = (100 2 4 6 2 4)
(union-set (2 4 6 2 4) (2 4 6 2 4)) = (2 4 6 2 4 2 4 6 2 4)
(intersection-set (2 4 6 2 4) (2 4 6 2 4)) = (2 4 6 2 4)
(element-of-set? 5 (2 4 6 2 4)) = #f
(adjoin-set 100 (2 4 6 2 4)) = (100 2 4 6 2 4)
(union-set (2 4 6 2 4) (1 2 3 4 5)) = (2 4 6 2 4 1 2 3 4 5)
(intersection-set (2 4 6 2 4) (1 2 3 4 5)) = (2 4 2 4)
(element-of-set? 5 (1 2 3 4 5)) = #t
(adjoin-set 100 (1 2 3 4 5)) = (100 1 2 3 4 5)
(union-set (1 2 3 4 5) (1)) = (1 2 3 4 5 1)
(intersection-set (1 2 3 4 5) (1)) = (1)
(element-of-set? 5 (1 2 3 4 5)) = #t
(adjoin-set 100 (1 2 3 4 5)) = (100 1 2 3 4 5)
(union-set (1 2 3 4 5) (1 2 1 2)) = (1 2 3 4 5 1 2 1 2)
(intersection-set (1 2 3 4 5) (1 2 1 2)) = (1 2)
(element-of-set? 5 (1 2 3 4 5)) = #t
(adjoin-set 100 (1 2 3 4 5)) = (100 1 2 3 4 5)
(union-set (1 2 3 4 5) (1 3 5 7 9 1 3)) = (1 2 3 4 5 1 3 5 7 9 1 3)
(intersection-set (1 2 3 4 5) (1 3 5 7 9 1 3)) = (1 3 5)
(element-of-set? 5 (1 2 3 4 5)) = #t
(adjoin-set 100 (1 2 3 4 5)) = (100 1 2 3 4 5)
(union-set (1 2 3 4 5) (2 4 6 2 4)) = (1 2 3 4 5 2 4 6 2 4)
(intersection-set (1 2 3 4 5) (2 4 6 2 4)) = (2 4)
(element-of-set? 5 (1 2 3 4 5)) = #t
(adjoin-set 100 (1 2 3 4 5)) = (100 1 2 3 4 5)
(union-set (1 2 3 4 5) (1 2 3 4 5)) = (1 2 3 4 5 1 2 3 4 5)
(intersection-set (1 2 3 4 5) (1 2 3 4 5)) = (1 2 3 4 5)
$