SICP 2.59

例題のテーマ選びが秀逸だ。

(define (element-of-set? x set)
  (if (null? set)
      #f
      (or (equal? x (car set))
          (element-of-set? x (cdr set)))))

(define (union-set s1 s2)
  (cond ((null? s1) s2)
        ((null? s2) s1)
        ((element-of-set? (car s1) s2) (union-set (cdr s1) s2))
        (else (cons (car s1) (union-set (cdr s1) s2)))))

; test
(union-set '(2 3 5) '(1 2 3 4))
(union-set '() '(1 2))
(union-set '(1 2 3) '())
(union-set '(1 2 3) '(1 2 3))