## 2014年4月27日日曜日

### Scheme - データによる抽象の構築(記号データ(重複ありとなしの集合表現と各演算の効率))

その他参考書籍

コード(BBEdit, Emacs)

set2.scm

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

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

```\$ ./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)
\$
```