2015/10/20

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

© 2022 wat-aro