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)))))

なぜこれでよいか、に対する明快な説明...ってのは難しいな。

リストの先頭要素を含むものと含まないものにわけて考える。

含まないものについて、再帰的に可能な部分集合をつくれると考える。
そしてその可能な部分集合に、先頭要素を加えた部分集合をつくる。

そして含むものと含まないもの、それぞれを結合すれば、すべての部分集合が得られる。