2.62

练习 2.62 请给出在集合的排序表示上 union-set 的一个 $\Theta(n)$ 实现。

看到这个问题，陷入了片刻的深思。因为首先进入脑海的还是命令式思维，觉得烦琐不堪。

突然又想到了屡试不爽的“按愿望思维”大法，假设更小一点的子问题已经得到了解决，于是只需要考虑再多加一个元素的这个场景了。

(define (union-set set1 set2)
    (cond
        ((null? set1) set2)
        ((null? set2) set1)
        (
            (< (car set1) (car set2))
            (cons 
                (car set1)
                (union-set (cdr set1) set2)
            ) 
        )
        (
            (= (car set1) (car set2))
            (union-set (cdr set1) set2)
        )
        (
            else
            (cons
                (car set2)
                (union-set set1 (cdr set2))
            )
        )
    ) 
)

(union-set (list 1 2 3 4) (list 5 6 7 8))

(union-set (list 1 3 5 7) (list 2 4 6 8))

(union-set (list 5 6 7 8) (list 1 2 3 4))

(union-set (list 2 4 6 8) (list 1 3 5 7))