集合的 regression test

因为之后需要使用不同的方法来实现集合，我们先写好 regression test 避免之后的错误。下面是我们的 regression test:

;; regression test for Set, sicp 2.3.3

(load "../testframe.scm")

; element-of-set?
(asserttrue (element-of-set? 1 '(1 2 3)))

(asserttrue (element-of-set? 1 '(2 1 3)))

(asserttrue (element-of-set? 1 '(2 3 1)))

; adjoin-set
(assertequal? (sort (adjoin-set 1 '(2 3 4)) <)
              '(1 2 3 4))

(assertequal? (sort (adjoin-set 1 '(1 2 3)) <)
              '(1 2 3))

; intersection-set
(assertequal? (sort (intersection-set '(1 2 3) '(4 5 6)) <)
              '())

(assertequal? (sort (intersection-set '(1 2 3) '(2 3 4)) <)
              '(2 3))

(assertequal? (sort (intersection-set '(1 2 3) '(1 2 3 4)) <)
              '(1 2 3))

(assertequal? (sort (intersection-set '(1 2 3 4) '(1 2)) <)
              '(1 2))

; union-set
(assertequal? (sort (union-set '(1 2 3) '(3 4 5)) <)
              '(1 2 3 4 5))

(assertequal? (sort (union-set '(1 2 3) '(1 2 3 4)) <)
              '(1 2 3 4))

(assertequal? (sort (union-set '(1 2 3 4) '(1 2 3)) <)
              '(1 2 3 4))

(assertequal? (sort (union-set '(1 2 3) '(4 5 6)) <)
              '(1 2 3 4 5 6))

求集合的并集

(define (element-of-set? x set)
  (cond ((null? set) false)
        ((equal? x (car set)) true)
        (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))))

(define (union-set set1 set2)
  (cond ((null? set1) set2)
        ((element-of-set? (car set1) set2)
         (union-set (cdr set1) set2))
        (else
         (cons (car set1)
               (union-set (cdr set1) set2)))))


(load "set-regression-tests.scm")

high-order one

求交集与求并集都只需要在递归时固定查看某一个集合的元素是否在另外一个集中，并做相应操作即可。

交集：当 element-of-set? 为真时，收集该类元素。

并集：当 element-of-set? 为假时，收集该类元素。

所以我们可以把这两个操作写为高阶函数：

(define (intersection-set set1 set2)
  (filter (lambda (x)
            (element-of-set? x set2))
          set1))

(define (union-set set1 set2)
  (append (filter (lambda (x)
                    (not (element-of-set? x set2)))
                  set1)
          set2))

(load "set-regression-tests.scm")