SICP §2.3.4（Haffman 符号化木 その５ [重み付き要素の集合]）

う〜ん、このセクション何を言いたいのかいまいち確信が持てない。。
とりあえずコードを写経してコメントを付加していってみよう。

(define (adjoin-set x set)
  (cond (;母体となるリストが空なら新規生成する。
	 (null? set)
	 (list x))
	(;「挿入したい枝の重み」＜「リストの先頭の枝の重み」なら挿入したい枝を先頭に連結。
	 (< (weight x) (weight (car set)))
	 (cons x set))
	(else
	 ;「リストの先頭の葉の重み」≦「挿入したい葉の重み」なら再帰処理。
	 (cons (car set)
	       (adjoin-set x (cdr set))))))

x、及び set の要素は「葉」または「枝」だ。で、x と set の先頭の枝（または葉）の重みを比較して、x の方が小さければ先頭に挿入する、ということをやっているだけ。
これだけだとまだちょっとよく分からない。
枝で確認するのは大変だから、とりあえず葉だけで実験。

gosh> (define leafs '())

leafs

gosh> leafs

()

gosh> (define leafs (adjoin-set (make-leaf 'A 4) leafs))

leafs

gosh> leafs

( (leaf A 4))

gosh> (define leafs (adjoin-set (make-leaf 'B 2) leafs))

leafs

gosh> leafs

( (leaf B 2) (leaf A 4))

gosh> (define leafs (adjoin-set (make-leaf 'C 5) leafs))

leafs

gosh> leafs

( (leaf B 2) (leaf A 4) (leaf C 5))

gosh> (define leafs (adjoin-set (make-leaf 'D 3) leafs))

leafs

gosh> leafs

( (leaf B 2) (leaf D 3) (leaf A 4) (leaf C 5))

gosh> 

うむ。ちゃんと昇順になっとるね。

その次に記載されているサンプルコードが、adjoin-set 手続きを使って何やらやっている。
この手続は、こんなリストを第１引数として受け取るらしい。（あくまでもサンプルね。）

( (A 4) (B 2) (C 1) (D 1))

こちらも写経してみよう。

(define (make-leaf-set pairs)
  (if (null? pairs)
      ;入力されたリストが空リストなら空リストを返却。
      '()
      ;何かしら要素が存在した場合は、先頭要素を pair として取り出して、
      (let ((pair (car pairs)))
	;pair から leaf を生成、それを残りの pairs を使用して生成される枝の母集団に挿入する。
	(adjoin-set (make-leaf (car pair)   ;記号
			       (cadr pair)) ;頻度
		    (make-leaf-set (cdr pairs))))))

これ、ただ単純にサンプルデータを元にして leaf を作りながら、重みの低いものから高いものに整列しているだけか。Huffman木を生成する為の手続じゃないんだなぁ。
一応実験して確認しておこう。

gosh> (make-leaf-set '((A 4) (B 2) (C 1) (D 1)))

( (leaf D 1) (leaf C 1) (leaf B 2) (leaf A 4))

gosh> (make-leaf-set '((B 2) (C 1) (A 4) (D 1)))

( (leaf D 1) (leaf C 1) (leaf B 2) (leaf A 4))

gosh> (make-leaf-set '((C 1) (B 2) (A 4) (D 1)))

( (leaf D 1) (leaf C 1) (leaf B 2) (leaf A 4))

gosh> 

順番を変化させてもちゃんと重みの低いもの→高いものの順序づけられたリストになってるね。

なんつーか、このサンプルデータを受け取ったらHuffman木を生成してくれる手続とかはこれ以降の「問題」で出てくるのかな。