SICP Exercise 2.32

Question

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

Answer

To figure this out, it helps to look at what the code that we already have does by itself. Looks like the code gets the cdr of the list and recursively calls subsets on this sublist. If we trust the authors that this procedure actually does what it says it does, then this rest variable should be equivalent to (subsets (cdr (1 2 3))) or, in other words, (subsets (2 3)), so all the subsets of the list (2 3).

And now if we think about what we expect the total result of the procedure to be, this starts to make sense. Because the total result is nothing other than the subsets of (2 3) plus all these same sublists with a 1 in them, we can guess that the part which is appended to (sublists (2 3)) (aka rest) must be each element of rest with a 1 (nothing other than (car s)) cons’d to it. So the lambda function within map must be (λ (x) (cons (car s) x)). This is what the code looks like:

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

(subsets (list 1 2 3))

Results:

(() (3) (2) (2 3) (1) (1 3) (1 2) (1 2 3))