Exercise 2.32 of SICP

2009-08-17

sicp

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

In order for me to understand what is going on here, I understand how powersets are constructed first and then derive this function. This program wants to create what is called a powerset. If S is a set of {a1,a2,a3}

$$ \mathcal{P}(S) = \{\{\} \{a_3\} \{a_2\} \{a_2 a_3\} \{a_1\} \{a_1 a_3\} \{a_1 a_2\} \{a_1 a_2 a_3\}\} $$

The reasoning to construct a powerset is similar to the way the count change example is thought about. Create a powerset for the cdr elements without using the car element, cons the car element with powerset of cdr elements. To the result append powerset of cdr elements. When the arguments are an element and a set inject the element into every element of the set creating a new set. Append that result with the original powerset injected into.

P{$ \varnothing $} => { $ \varnothing $ }

P{a1} => (append (inject a1 P{ $ \varnothing $ }) P{ $ \varnothing $}) => {{a1} $ \varnothing $}

P{a1 a2} => (append (inject a1 P{a2}) P{a2}) => (append {{a1 a2} {a1}} P{a2}) => {{a1 a2} {a1} {a2} $ \varnothing $}

P{a1 a2 a3} =>

(append (inject a1 P{a2 a3}) P{a2 a3})

(append (inject a1 (append (inject a2 P{a3}) P{a3})) (append (inject a2 P{a3}) P{a3}))

(append (inject a1 (append (inject a2 {{a3} $ \varnothing $}) {{a3} $ \varnothing $})) (append (inject a2 {{a3} $ \varnothing $}) {{a3} $ \varnothing $}))

(append (inject a1 (append {{a3 a2} {a2}} {{a3} $ \varnothing $})) (append (inject a2 {{a3} $ \varnothing $}) {{a3} $ \varnothing $}))

(append (inject a1 {{a3 a2} {a2} {a3} $ \varnothing $}) (append {{a3 a2} {a2}} {{a3} $ \varnothing $}))

(append {{a3 a2 a1 } {a2 a1} {a3 a1} {a1}} (append {{a3 a2} {a2}} {{a3} $ \varnothing $}))

(append {{a3 a2 a1 } {a2 a1} {a3 a1} {a1}} {{a3 a2} {a2} {a3} $ \varnothing $})

{{a3 a2 a1} {a2 a1} {a3 a1} {a1} {a3 a2} {a2} {a3} $ \varnothing $}

Here is the process above in code:

(define (powerset ss)
  (if (null? ss)
    (list '())
    (append (inject (car ss) 
                    (powerset (cdr ss))) 
            (powerset (cdr ss)))))
(define (inject s ss)
  (map (lambda (elem)
           (cons s elem))
       ss))

Finally:

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

It’s worth noticing that because of the let expression (subsets (cdr s)) is only called once, as opposed to twice in my earlier derivation.

Contents