問題2-32

集合のべき集合を求めます。

(define (map proc items)
  (if (null? items)
      ()
      (cons (proc (car items))
	    (map proc (cdr items)))))

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

あんまし意味ないけど、こうやってもできるよ。

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

結果。

gosh> (print (subsets (list 1 2 3)))
(() (3) (2) (2 3) (1) (1 3) (1 2) (1 2 3))