Exercise 2.32. We can represent a set as a list of distinct elements, and we can represent the set of all subsets of the set as a list of lists. For example, if the set is (1 2 3), then the set of all subsets is (() (3) (2) (2 3) (1) (1 3) (1 2) (1 2 3)). Complete the following definition of a procedure that generates the set of subsets of a set and give a clear explanation of why it works:
(define (subsets s)
(if (null? s)
(list nil)
(let ((rest (subsets (cdr s))))
(append rest (map <??> rest)))))
这个练习要生成集合的全部子集。
看到示例程序：
(define (subsets s)
(if (null? s)
(list nil)
(let ((rest (subsets (cdr s))))
(append rest (map <??> rest)))))
可以这样来理解：以 (1 2 3) 为例，第一次进入过程的时候，得到的 rest 将是 (2 3) 的所有子集。最终的 append 将会把这些子集，连同 (map <??> rest) 作为解。
所以 (map <??> rest) 部分是 (1 2 3) 中还没有出现的第一个元素 1 与 (2 3) 的子集的某种结合，就马上可以想到将 1 与这些子集进行 cons ，即得到解答。
这种思路在练习 2.XX 中也有体现。
(define (subsets s)
(if (null? s)
(list '())
(let ((rest (subsets (cdr s))))
(append rest (map (lambda (x) (cons (car s) x)) rest)))))
;;; tests begin
(load "../testframe.scm")
;; fixme: assertequal? is not a right assertion for set
(assertequal? (subsets '(1 2 3))
'(() (3) (2) (2 3) (1) (1 3) (1 2) (1 2 3)))