SICPを読む(72) 問題2.61 - 2.62 順序づけられたリストとしての集合

まだまだ集合が続きます。今回は順序づけられたリスト。つまり、

(1 3 5 7) ; OK
(8 6 4 2) ; NG

順番は守ろう〜。というリスト。

問題 2.61

あ、前回、スペルミスしてたっぽい。ajoinだと思ったら、adjoinだった。

英語の弱さも直さねば。

(define (adjoin-set x set)
  (if (null? set)
      (cons x '())
      (let ((y (car set)))
        (cond ((= x y) set)
              ((< x y) (cons x set))
              (else
                (cons y
                      (adjoin-set x (cdr set))))))))

前回はただ突っ込んでいけばなんとかなった。

今回は「順番を守らなければならない」ので、挿入する場所を決める必要がある。ステップ数は1からnに増えてしまった。順序があると挿入にかかるコストが増えるというのがポイント。

問題 2.62

和集合の問題。

adjoin-setを使うとn^2ステップかかってしまうので、真面目にpushする。

(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) (cdr set2))))
                  ((< x1 x2)
                   (cons x1
                         (union-set (cdr set1) set2)))
                  ((> x1 x2)
                   (cons x2
                         (union-set set1 (cdr set2)))))))))

2つのリストをマージすればいいので、積集合の逆をやればいい。

小さい方をpop。どっちかが空っぽになったら、残りを突っ込む。

単調な部分を除いてみる。

(define (union-set set1 set2)
  (cond ((null? set1) set2)
        ((null? set2) set1)
        (else
          (let ((x1 (car set1))
                (x2 (car set2))
                (push-next
                  (lambda (p s1 s2)
                    (cons p (union-set s1 s2)))))
            (cond ((= x1 x2) (push-next x1 (cdr set1) (cdr set2)))
                  ((< x1 x2) (push-next x1 (cdr set1) set2))
                  ((> x1 x2) (push-next x2 set1 (cdr set2))))))))

ちょっとすっきり。再帰しないなら、letrecを使わなくてもいいっぽい。