**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.