SICP 2.60
(define (element-of-set? x set) ; 元の定義と同じ (if (null? set) #f (or (equal? x (car set)) (element-of-set? x (cdr set))))) (define (adjoin-set x set) (cons x set)) (define (union-set s1 s2) (append s1 s2)) (define (intersection-set s1 s2) ; 元の定義と同じ (cond ((null? s1) '()) ((null? s2) '()) ((element-of-set? (car s1) s2) (cons (car s1) (intersection-set (cdr s1) s2))) (else (intersection-set (cdr s1) s2)))) ; test (element-of-set? 3 '(1 2 3 2 4 5)) (element-of-set? 3 '(1 2 4 5 2)) (adjoin-set 3 '(1 2 3 4 5 3 2)) (adjoin-set 3 '(1 2 4 5 4)) (union-set '(1 2 3) '(1 2 3 4 1 2)) (union-set '(1 2 3) '(4 5 6 6 5 4)) (intersection-set '(1 2 3) '(4 5 6 4 5 6)) (intersection-set '(4 1 2 8 3 2 7) '(1 2 3 4 1 5 1 2 3))
効率
adjoin-setとunion-setは計算量のオーダーがO(1)になり、速くなった。他2つの関数には変化なし。ただし、同じ集合を表現するのに必要なリストの長さが長くなる。このため、adjoin-setとunion-setの使用頻度が高い場合にはこちらの表現を使うメリットがある。