**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 {a_{1},a_{2},a_{3}}

$$ \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{a_{1}} => (append (inject a_{1} P{ \( \varnothing \) }) P{ \( \varnothing \)}) =>
{{a_{1}} \( \varnothing \)}

P{a_{1} a_{2}} =>
(append (inject a1 P{a_{2}}) P{a_{2}}) =>
(append {{a_{1} a_{2}} {a_{1}}} P{a_{2}}) =>
{{a_{1} a_{2}} {a_{1}} {a_{2}} \( \varnothing \)}

P{a_{1} a_{2} a_{3}} =>

(append (inject a_{1} P{a_{2} a_{3}}) P{a_{2} a_{3}})

(append (inject a_{1} (append (inject a_{2} P{a_{3}}) P{a_{3}})) (append (inject a_{2} P{a_{3}}) P{a_{3}}))

(append (inject a_{1} (append (inject a_{2} {{a_{3}} \( \varnothing \)}) {{a_{3}} \( \varnothing \)})) (append (inject a_{2} {{a_{3}} \( \varnothing \)}) {{a_{3}} \( \varnothing \)}))

(append (inject a_{1} (append {{a_{3} a_{2}} {a_{2}}} {{a_{3}} \( \varnothing \)})) (append (inject a_{2} {{a_{3}} \( \varnothing \)}) {{a_{3}} \( \varnothing \)}))

(append (inject a_{1} {{a_{3} a_{2}} {a_{2}} {a_{3}} \( \varnothing \)}) (append {{a_{3} a_{2}} {a_{2}}} {{a_{3}} \( \varnothing \)}))

(append {{a_{3} a_{2} a_{1} } {a_{2} a_{1}} {a_{3} a_{1}} {a_{1}}} (append {{a_{3} a_{2}} {a_{2}}} {{a_{3}} \( \varnothing \)}))

(append {{a_{3} a_{2} a_{1} } {a_{2} a_{1}} {a_{3} a_{1}} {a_{1}}} {{a_{3} a_{2}} {a_{2}} {a_{3}} \( \varnothing \)})

{{a_{3} a_{2} a_{1}} {a_{2} a_{1}} {a_{3} a_{1}} {a_{1}} {a_{3} a_{2}} {a_{2}} {a_{3}} \( \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.