SICP §2.3.3（集合の表現 その１ [順序づけられないリストとしての集合]）

さて、ここから先は集合の話になるぞと。
ざーっと読んでみたら結構なボリュームがあるし、内容的にもヘビーな感じを受ける。
なので、ペインタの二の舞にならんよう、セクションの内容をきっちり追っていきたいと思う。

最初は、「順序なし」「重複なし」の集合の表現について。
集合のオブジェクトはまんまリストを使うようですよ。
つまり、こういう性質の集合なら構成子は不要？（まぁ作ってもいいんだろう。。）
あ、ちなみに空集合は空リストだそうです。

じゃ、選択子や述語等で必要なものは何か。。こんな感じになるみたい。

union-set	和集合（２つの集合のうち、どちらかの集合に現れる要素を含んでいる集合）を計算する。
intersection-set	積集合（両方の集合に現れる要素だけを含む集合）を計算する。
element-of-set?	与えられた要素が集合の構成要素であるかという述語。
adjoin-set	引数としてオブジェクトと集合をとり、元の集合の要素と追加する要素を含む集合を返す。

さて、では各種手続きを実装してみましょうか。

(define (element-of-set? x set)
  (cond ((null? set)
	 #f)
	((equal? x (car set))
	 #t)
	(else
	 (element-of-set? x (cdr set)))))

(define (adjoin-set x set)
  (if (element-of-set? x set) ;重複する場合はまんまsetを返却
      set
      (cons x set)))

(define (intersection-set set1 set2)
  (cond ((or (null? set1) (null? set2))
	 '())
	((element-of-set? (car set1) set2) ;共通要素があったら返却用リストに追加。
	 (cons (car set1)                  ;そして被追加側は再帰。
	       (intersection-set (cdr set1) set2)))
	(else
	 (intersection-set (cdr set1) set2))))

;なんとなく反復で定義してみる。
(define (intersection-set set1 set2)
  (let loop ((ans '())
	     (s1 set1)
	     (s2 set2))
    (cond ((or (null? s1) (null? s2))
	   (reverse ans)) ;順序関係ないから reverse しなくてもいいけど、見やすいから。。
	  ((element-of-set? (car s1) s2)
	   (loop (cons (car s1) ans)
		 (cdr s1)
		 set2))
	  (else
	   (loop ans (cdr s1) s2)))))

残ってる union-set 手続きだけど、問題2.59で定義しろって書いてあるので次のエントリで。