SICP 2.32 (冪集合) - ixixixixixixixixi..........

「集合のすべての部分集合の集合をリストのリストとして表現せよ」という問題．
冪集合という言葉は出てないけど，冪集合そのもの．
wikipedia:冪集合

P(X):=集合Xの部分集合の集合(冪集合)

と定義する．このとき

P(X)={Xから先頭の要素xを除いた集合の冪集合と、その各要素にxを加えた集合の和集合}

と再帰的に書けるので，これをそのまま適用してあげれば解答になる．
つまり、X={a,b,c}について
P(X)=P{b,c}∪(P{b,c}の全ての要素にaを加えたもの)
のような感じ．

私は最初に問題を見た時は，以下のように考えた．
集合の要素として含む/含まないをビットが立っているかで表すと、

P{b,c}は、以下のように書ける．

	b	c
	0	0
	0	1
	1	0
	1	1

P{a,b,c}は，以下のように書ける．

a	b	c
0	0	0
0	0	1
0	1	0
0	1	1
1	0	0
1	0	1
1	1	0
1	1	1

aが0と1の時のそれぞれについて，bとcについてはP{b,c}と同じ形．
このことから，P{b,c}に，aを加えてあげたものを足せばよいということが分かる．
なので，この場合，
rest=(subsets (cdr '(a b c))=(subset '(b c))と考えると
(subsets '(a b c))=(append rest (map (aをリストに加える手続き) rest)
とすれば良さそうということが分かり，
解答としては，
(lambda (x) (cons (car s) x))
を入れれば良いことが分かる．

また，上記のように，ビットのON/OFFで集合に含まれるかどうかを表すと，
二進数と各部分集合が1:1に対応するので，n個の要素を持つ集合に対して，
$2^{n}-1$ まで2進数をカウントアップしていけば $2^{n}$ 個の部分集合からなる冪集合を作ることができる．
この方法だと再帰的ではない書き方も可能．