読者です 読者をやめる 読者になる 読者になる

(wat-aro)

無職から有職者にランクアップしました

SICP 問題 2.32

scheme SICP
(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))