SICP 問題 2.32

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

;;この式はまず最後まで再帰し，そこでrestに空リストを持って返ってくる．
;;mapでcarとrestをconsして新しいリストを作りそれが返ったところでrestに入る．
;;その繰り返しですべての部分集合が返される．

s = nil
()

s = (3)
rest = ()
(cons (car s) x) = (3)

s = (2 3)
rest = (() (3))
(cons (car s) x) = (2) (2 3)

s = (1 2 3)
rest = (() (3) (2) (2 3))
(cons (car s) x) = (1) (1 3) (1 2) (1 2 3)

(() (3) (2) (2 3) (1) (1 3) (1 2) (1 2 3))