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

1 2 3 4 5 |
(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}}

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.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
P{$latex \varnothing$} {$latex \varnothing$} P{a<sub>1</sub>} (append (inject a<sub>1</sub> P{$latex \varnothing$}) P{$latex \varnothing$}) {{a<sub>1</sub>} $latex \varnothing$} P{a<sub>1</sub> a<sub>2</sub>} (append (inject a<sub>1</sub> P{a<sub>2</sub>}) P{a<sub>2</sub>}) (append {{a<sub>1</sub> a<sub>2</sub>} {a<sub>1</sub>}} P{a<sub>2</sub>}) {{a<sub>1</sub> a<sub>2</sub>} {a<sub>1</sub>} {a<sub>2</sub>} $latex \varnothing$} P{a<sub>1</sub> a<sub>2</sub> a<sub>3</sub>} (append (inject a<sub>1</sub> P{a<sub>2</sub> a<sub>3</sub>}) P{a<sub>2</sub> a<sub>3</sub>}) (append (inject a<sub>1</sub> (apend (inject a<sub>2</sub> P{a<sub>3</sub>}) P{3})) (append (inject a<sub>2</sub> P{a<sub>3</sub>}) P{a<sub>3</sub>})) (append (inject a<sub>1</sub> (append (inject a<sub>2</sub> {{a<sub>3</sub>} $latex \varnothing$}) {{a<sub>3</sub>} $latex \varnothing$})) (append (inject a<sub>2</sub> {{a<sub>3</sub>} $latex \varnothing$}) {{a<sub>3</sub>} $latex \varnothing$})) (append (inject a<sub>1</sub> (append {{a<sub>3</sub> a<sub>2</sub>} {a<sub>2</sub>}} {{a<sub>3</sub>} $latex \varnothing$})) (append (inject a<sub>2</sub> {{a<sub>3</sub>} $latex \varnothing$}) {{a<sub>3</sub>} $latex \varnothing$})) (append (inject a<sub>1</sub> {{a<sub>3</sub> a<sub>2</sub>} {a<sub>2</sub>} {a<sub>3</sub>} $latex \varnothing$}) (append {{a<sub>3</sub> a<sub>2</sub>} {a<sub>2</sub>}} {{a<sub>3</sub>} $latex \varnothing$})) (append {{a<sub>3</sub> a<sub>2</sub> a<sub>1</sub> } {a<sub>2</sub> a<sub>1</sub>} {a<sub>3</sub> a<sub>1</sub>} {a<sub>1</sub>}} (append {{a<sub>3</sub> a<sub>2</sub>} {a<sub>2</sub>}} {{a<sub>3</sub>} $latex \varnothing$})) (append {{a<sub>3</sub> a<sub>2</sub> a<sub>1</sub> } {a<sub>2</sub> a<sub>1</sub>} {a<sub>3</sub> a<sub>1</sub>} {a<sub>1</sub>}} {{a<sub>3</sub> a<sub>2</sub>} {a<sub>2</sub>} {a<sub>3</sub>} $latex \varnothing$}) {{a<sub>3</sub> a<sub>2</sub> a<sub>1</sub>} {a<sub>2</sub> a<sub>1</sub>} {a<sub>3</sub> a<sub>1</sub>} {a<sub>1</sub>} {a<sub>3</sub> a<sub>2</sub>} {a<sub>2</sub>} {a<sub>3</sub>} $latex \varnothing$} |

Here is the process above in code:

1 2 3 4 5 6 7 8 9 10 |
(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:

1 2 3 4 5 6 |
(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.