SICP 問題 2.61（順序づけられた集合に対する adjoin-set を定義）

問題

順序づけられた表現を使った adjoin-set の実装を示せ。
element-of-set? の類推で、順序付けられない表現に比べ、約半分のステップ数を必要とする手続を作るのに、順序の利点をどう用いるか示せ。

解答

element-of-set? の類推でいいんだからこんな感じだよねぇ。

(define (adjoin-set x set)
  (cond ((null? set)
	 (cons x '()))
	((= x (car set))
	 (cons x set)) ;重複をゆるすとして x を追加する。
	((< x (car set))
	 (cons x set)) ;集合の先頭より小さかったら x を先頭に付加した集合を返す。
	(else
	 ;x が 集合の先頭より大きかったらまだ先頭を除いた集合で再帰処理。
	 (cons (car set) (adjoin-set x (cdr set))))))

こんな感じか。
では実験。

gosh> (adjoin-set 4 '(1 2 3 4 5 6 7))

(1 2 3 4 4 5 6 7)

gosh> (adjoin-set 4 '())

(4)

gosh> (adjoin-set 4 '(5 6 7))

(4 5 6 7)

gosh> (adjoin-set 4 '(1 2 3))

(1 2 3 4)

gosh> 

よぉ〜し、おっけい。