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の使用頻度が高い場合にはこちらの表現を使うメリットがある。