2.32

练习 2.32 我们可以将一个集合表示为一个元素互不相同的表，因此就可以将一个集合的所有子集表示为表的表。例如，假定集合为( 1 2 3 )，它的所有子集的集合就是(() (3) (2) (2 3) (1) (1 3) (1 2) (1 2 3))。请完成下面的过程定义，它生成出一个集合的所有子集的集合。请解释它为什么能完成这一工作。

(define (subsets s)
    (if (null? s)
        (list nil)
        (let ((rest (subsets (cdr s))))
            (append rest (map <??> rest))))
)

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

(subsets '())

(subsets (list 1 2 3))

首先，使用“按愿望思维”，假设当s的第一个元素从集合中拿掉后，剩下的元素组成的集合的子集合已经求出来了，就是 rest。然后，遍历 rest 中的每一个子集合，并将s的第一个元素，插入这些子集合中，就得到了当元素的个数再增加一个时，新增的子集合们。最后，将 rest 和这些新增的集合连在一起，就得到了最终结果。

将 (append rest (向 rest 中的每一个集合添加一个新的元素)) 翻译成语言就是：

集合拿掉一个元素后，得到的子集，其子集们也是原来的集合的子集。另外，向这些子集们都再增加那个被拿掉的元素，这些新的集合，也是原来的集合的子集。