データの集合をいろいろな方法で表現しましょう。
(define (element-of-set? x set)
(cond ((null? set) #f)
((equal? x (car set)) #t)
(else (element-of-set? x (cdr set)))))
(define (adjoin-set x set)
(if (element-of-set? x set)
set
(cons x set)))
(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))))
2.59
(define (union-set set1 set2)
(cond ((or (null? set1) (null? set2)) (append set1 set2))
((element-of-set? (car set1) set2)
(union-set (cdr set1) set2))
(else (cons (car set1) (union-set (cdr set1) set2)))))
2.60
(define adjoin-set cons)
(define union-set append)
;; Sets as ordered lists
(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 (intersection-set set1 set2)
(if (or (null? set1) (null? set2))
'()
(let ((x1 (car set1)) (x2 (car set2)))
(cond ((= x1 x2)
(cons x1
(intersection-set (cdr set1)
(cdr set2))))
((< x1 x2)
(intersection-set (cdr set1) set2))
((< x2 x1)
(intersection-set set1 (cdr set2)))))))
2.61
(define (adjoin-set set1 set2)
(cond ((or (null? set1) (null? set2)) (append set1 set2))
((< (car set1) (car set2)) (cons (car set1) (adjoin-set (cdr set1) set2)))
((> (car set1) (car set2)) (cons (car set2) (adjoin-set set1 (cdr set2))))
(else (cons (car set1) (adjoin-set (cdr set1) (cdr set2))))))
2.62
(define (union-set set1 set2)
(cond ((or (null? set1) (null? set2)) '())
((< (car set1) (car set2)) (union-set (cdr set1) set2))
((> (car set1) (car set2)) (union-set set1 (cdr set2)))
(else (cons (car set1) (union-set (cdr set1) (cdr set2))))))
;; Sets as binary trees
(define (entry tree) (car tree))
(define (left-branch tree) (cadr tree))
(define (right-branch tree) (caddr tree))
(define (make-tree entry left right)
(list entry left right))
(define (element-of-set? x set)
(cond ((null? set) false)
((= x (entry set)) true)
((< x (entry set))
(element-of-set? x (left-branch set)))
((> x (entry set))
(element-of-set? x (right-branch set)))))
(define (adjoin-set x set)
(cond ((null? set) (make-tree x '() '()))
((= x (entry set)) set)
((< x (entry set))
(make-tree (entry set)
(adjoin-set x (left-branch set))
(right-branch set)))
((> x (entry set))
(make-tree (entry set)
(left-branch set)
(adjoin-set x (right-branch set))))))
2.63
(define (tree->list-1 tree)
(if (null? tree)
'()
(append (tree->list-1 (left-branch tree))
(cons (entry tree)
(tree->list-1 (right-branch tree))))))
(define (tree->list-2 tree)
(define (copy-to-list tree result-list)
(if (null? tree)
result-list
(copy-to-list (left-branch tree)
(cons (entry tree)
(copy-to-list (right-branch tree)
result-list)))))
(copy-to-list tree '()))オーダは同じに見える。(よくわかんない)
2.64
O(log n)くらい？
2.65
うーん、こんなのしか思いつかなかったんだけど…。あやしい。
(define tree->list tree->list-2)
(define (union-set set1 set2)
(define (%union-set set1 set2)
(cond ((or (null? set1) (null? set2)) '())
((< (car set1) (car set2)) (%union-set (cdr set1) set2))
((> (car set1) (car set2)) (%union-set set1 (cdr set2)))
(else (cons (car set1) (%union-set (cdr set1) (cdr set2))))))
(let ((set1 (tree->list set1))
(set2 (tree->list set2)))
(list->tree (%union-set set1 set2))
))
(define (union-set set1 set2)
(define (%union-set set1 set2)
(cond ((or (null? set1) (null? set2)) '())
((< (car set1) (car set2)) (%union-set (cdr set1) set2))
((> (car set1) (car set2)) (%union-set set1 (cdr set2)))
(else (cons (car set1) (%union-set (cdr set1) (cdr set2))))))
(let ((set1 (tree->list set1))
(set2 (tree->list set2)))
(list->tree (%union-set set1 set2))
))
(define (adjoin-set set1 set2)
(define (%adjoin-set set1 set2)
(cond ((or (null? set1) (null? set2)) (append set1 set2))
((< (car set1) (car set2)) (cons (car set1) (%adjoin-set (cdr set1) set2)))
((> (car set1) (car set2)) (cons (car set2) (%adjoin-set set1 (cdr set2))))
(else (cons (car set1) (%adjoin-set (cdr set1) (cdr set2))))))
(let ((set1 (tree->list set1))
(set2 (tree->list set2)))
(list->tree (%adjoin-set set1 set2))
))
2.66
(define (lookup given-key set-of-records)
(cond ((null? set-of-records) #f)
((< given-key (entry set-of-records)) (lookup given-key (left-branch set-of-records)))
((> given-key (entry set-of-records)) (lookup given-key (right-branch set-of-records)))
(else (entry set-of-records))))以上ほとんど試してない。
