Chapter 2, Building Abstractions with Data

Section - 2.2 - Hierarchical Data and the Closure Property

Exercise 2.32


To find power set of a set, $S$, we can proceed as:

Power set of $S$ is:

  • if $S = \phi$, then $\mathcal P(S) = \{ \phi \}$.
  • if $S \ne \phi$, then choose any element $x \in S$, then:
    $\mathcal P(S) = \mathcal P(S \setminus \{ x \}) \; \cup \; \{ X \cup \{x\} \, \vert \; X \in \mathcal P(S \setminus \{ x \}) \}$.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#lang sicp

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