SICP問題2.61

順序づけられた表現を使ったadjoin-set の実装

(define (adjoin-set x set)
  (cond ((null? set) (list x))
        ((= x (car set) (set))
        ((< x (car set) (cons x set))
        (else (cons (car set) (adjoin-set x (cdr set))))))))

順序の利点は検索対象と同じか、検索対象より大きい値を見つけた時点で検索を終了することが出来ることにある。このため検索に必要なステップ数は平均すると集合の大きさの約半分のステップ数となる。