問題2-61〜62

集合を扱う問題の続きです。こんどは、集合を構成しているリストが順序付けらていたら、処理をどれだけ効率化することができるかを調べます。例題として、element-of-set?とintersection-setは以下のように表現されていました。

(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? set2))
      '()
      (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)))))))

(element-of-set? 3 (list 1 2 3 4 5))  ;=>#t
(element-of-set? 3 (list 2 4 6 8 10))  ;=>#f

(intersection-set (list 1 3 5) (list 2 4 6))  ;=>()
(intersection-set (list 1 3 5) (list 3 5 7))  ;=>(3 5)

順序づけられているから全てを探索する必要がありません。問題2-61のadjoin-setは以下のように実装しました。

(define (adjoin-set x set)
  (define (iter result prev rest)
    (cond ((null? rest) result)
          ((and (< x (car rest)) (> x prev))
           (cons x 
                 (cons (car rest)
                       (iter result (car rest) (cdr rest)))))
          (else (cons (car rest)
                      (iter result (car rest) (cdr rest))))))
  (if (element-of-set? x set)
      set
      (iter '() 0 set)))

(adjoin-set 5 (list 1 3 5 7))  ;=>(1 3 5 7)
(adjoin-set 5 (list 1 3 7))  ;=>(1 3 5 7)

最初に、追加する要素が既に存在するかどうかを調べ、存在していたら集合をそのまま返します。存在していなければ、追加するべき場所を調べる内部手続きを呼び出します。集合の要素間を調べていくような手続きを書きました。と、ここまで書いたところで、これでは集合の全ての要素に対して内部手続きが呼ばれていることに気づきました。以下のようにすれば、追加すべき場所が見つかった後で、内部手続きを呼ばずにすませることができます。

(define (adjoin-set x set)
  (define (iter result prev rest)
    (cond ((null? rest) result)
          ((and (< x (car rest)) (> x prev))
           (cons x rest))
          (else (cons (car rest)
                      (iter result (car rest) (cdr rest))))))
  (if (element-of-set? x set)
      set
      (iter '() 0 set)))

次の問題2-62では、union-setを実装します。以下のように書きました。

(define (union-set set1 set2)
  (cond ((and (null? set1) (null? set2)) '())
        ((null? set1)
               (cons (car set2)
                     (union-set set1 (cdr set2))))
        ((null? set2)
               (cons (car set1)
                     (union-set (cdr set1) set2)))
        (else (let ((x1 (car set1)) (x2 (car set2)))
                (cond ((= x1 x2)
                       (cons x1
                             (union-set (cdr set1)
                                        (cdr set2))))
                      ((< x1 x2)
                       (cons x1
                             (union-set (cdr set1) set2)))
                      ((< x2 x1)
                       (cons x2
                             (union-set set1 (cdr set2)))))))))

(union-set (list 1 3 5) (list 2 4 6))  ;=>(1 2 3 4 5 6)
(union-set (list 1 3 5) (list 3 5 7))  ;=>(1 3 5 7)

これなら、集合の要素数だけステップを踏むだけで、和集合を求めることができます。