SICP問題2.32

集合の部分集合を作り出す手続きの次の定義

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

実験

(subsets (list 1 2 3))
; (() #0=(3) #1=(2) #2=(2 . #0#) (1) (1 . #0#) (1 . #1#) (1 . #2#))

うまくいかない…。何で?
ということで、Google先生に聞いてみるとsubsetsの定義はこれでOKで、subsets の結果に display とか print とかを適用すればよいらしい。
再実験

(display (subsets (list 1 2 3)))
; (() (3) (2) (2 3) (1) (1 3) (1 2) (1 2 3))#<undef>

まだ # が気持ち悪いけど、OK っぽい。

次は何故うまくいくかの説明。
まず全ての部分集合は「sの最初の要素を含む部分集合の集合」＋「sの最初の要素を含まない部分集合の集合」である。
letでrestに設定されるのはsの最初の要素以外を引数としてsubsetsに渡した結果であり、これは最初の要素以外の部分集合、すなわち「sの最初の要素を含まない部分集合の集合」となる。
ここでsの最初の要素を「sの最初の要素を含まない部分集合の集合」にそれぞれ加えたものが「sの最初の要素を含む部分集合の集合」となるが、これは「sの最初の要素」=(car s)を加える操作をmapでrestの各要素に適用することで得られる。
よって、上記の結果とrestをappendした結果が「sの最初の要素を含む部分集合の集合」＋「sの最初の要素を含まない部分集合の集合」となり、すべての部分集合を得ることが出来る。