問題 2.32

;(subsets (list 1 2 3))
;-> (() (3) (2) (2 3) (1) (1 3) (1 2) (1 2 3))

;となるものを作ればいいのか？
(define (append list1 list2)
  (if (null? list1)
      list2
      (cons (car list1) (append (cdr list1) list2))))

(define (subsets s)
  (if (null? s)
      (list null)
      (let ((rest (subsets (cdr s))))
        (append rest (map (lambda (item)
                            (cons (car s) item)) rest)))))

;できた。
;これでいいのか？？

(subsets (list 1 2 3))
;-> (() (3) (2) (2 3) (1) (1 3) (1 2) (1 2 3))

;ok!!

;明快に説明せよといわれても、この問題はなかなか難しい。
;わかったときの気持ちよさは結構大きかった。

;まず、((rest (subsets (cdr s))))
;の部分で再帰が最後までいくと、(list null) -> ()が帰る。
;次にappendで、(() (3))ができるのだが、
;ここで重要なのは、lambdaの中に、
;sをクロージャーにして入れているところである。
;これにより、(car s) -> 3となり、(cons 3 null) -> (3)となり、
;(append () (3)) -> (() (3))ができる。
;そしてこれが帰り、一つ上階層のrestに束縛される。
;ここでは、(car s) -> 2となる。restに対し(map)がかかるので、
;(() (3))それぞれに、(cons 2 item)がかかる。
;結果 ((2) (2 3))ができ、(() (3))とappendされるので、
;(() (3) (2) (2 3))が帰り一つ上階層のrestに束縛される。
;同じく、すべてに1が追加されたものができる。
;-> ((1) (1 3) (1 2) (1 2 3))
;これと、(() (3) (2) (2 3))がappendされ
;(() (3) (2) (2 3) (1) (1 3) (1 2) (1 2 3))となる。

;これはなかなか美しいプログラムだと思う。
;前の回までの全通りに自分を追加したものを、
;それにさらに追加していくことによって、
;確かに組み合わせは全て網羅できることになる。