Ex 2.32
これは以前悩んだことがあるから楽勝 (コードを書くのは)。
(define (subsets s) (if (null? s) (list s) (let ((rest (subsets (cdr s)))) (append rest (map (lambda (x) (cons (car s) x)) rest)))))
なぜこれでよいか、に対する明快な説明...ってのは難しいな。
リストの先頭要素を含むものと含まないものにわけて考える。
含まないものについて、再帰的に可能な部分集合をつくれると考える。
そしてその可能な部分集合に、先頭要素を加えた部分集合をつくる。
そして含むものと含まないもの、それぞれを結合すれば、すべての部分集合が得られる。