ex 2.61, 2.62 順序つけられたリストとしての集合

;; 順序づけられたリストとしての集合
(define (element-of-set? x set)
  (cond ((null? set) #f)
        ((= x (car set)) #t)
        ((< x (car set)) #f)
        (else (element-of-set x (cdr set)))))

(define (intersection-set set1 set2)
  (if (or (null? set1) (null? set1))
      '()
      (let ((x1 (car set1))
            (x2 (car set2)))
        (cond ((= x1 x2)
               (cons x1
                     (intersection-set (cdr set1)
                                       (cdr set2))))
              ((< x1 x2)
               (intersection-set (cdr set1) set2))
              ((< x2 x1)
               (intersection-set set1 (cdr set2)))))))

以下、問題。

;; sicp ex 2.61
(define (adjoin-set x set)
  (define (iter item rest ahead)
    (cond ((null? rest) ahead)
          ((= item (car rest)) (append ahead rest))
          ((< item (car rest)) (append ahead (cons item rest)))
          (else (iter item (cdr rest) (append ahead (list (car rest)))))))
  (iter x set '()))
;; 順序の利点を、追加する要素が走査している値と等しい、もしくは小さくなった時点で
;; 処理を終了するようにしている

;; sicp ex 2.62
;; intersection-setを参考に
(define (union-set set1 set2)
  (cond ((null? set1) set2)
        ((null? set2) set1)
        (else (let ((x1 (car set1))
                    (x2 (car set2)))
                (cond ((< x1 x2)
                       (cons x1 (union-set (cdr set1) set2)))
                      ((< x2 x1)
                       (cons x2 (union-set set1 (cdr set2))))
                      ((= x1 x2)
                       (union-set (cdr set1) set2)))))))

特に問題なし。