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