CS107 Handout 32
Spring 2008 May 19, 2008
Advanced Mapping, Apply, and Lambda
This lambda idea is really big—so big, actually, that it deserves its own handout. It’s not
until you see a good set of examples that you realize how expressive the inner function
is.
Generating Power Sets
Consider the problem of generating the power set of the set
!
1, 2, 3
{ }
. The power set is
the set of all subsets, and an arbitrary subset can elect to include or exclude each
element. Here are the 8 sets making up the power set of
!
1, 2, 3
{ }
.
!
{ }
,
!
1
{ }
,
!
2
{ }
,
!
3
{ }
,
!
1, 2
{ }
,
!
1, 3
{ }
,
!
2, 3
{ }
,
!
1, 2, 3
{ }
They’re topologically sorted from small to large, but this presentation doesn’t illustrate
the inductive structure of power sets. This one does:
!
{ }
,
!
2
{ }
,
!
3
{ }
,
!
2, 3
{ }
!
1
{ }
,
!
1, 2
{ }
,
!
1, 3
{ }
,
!
1, 2, 3
{ }
Note the first of the two rows is the power set of
!
2, 3
{ }
. The second row is the power set
of
!
2, 3
{ }
all over again, except that a 1 has been included in each one. There’s the
recursive structure for you: the power set of
!
1, 2, 3
{ }
is really two copies of
!
2, 3
{ }
’s
power set chained together, except that the second copy prepends a 1 onto the front of
each entry.
Here’s a power-set implementation:
;;
;; Function: power-set
;; ------------------
;; The power set of a set is the set of all its subsets.
;; The key recursive breakdown is:
;;
;; The power set of {} is {{}}. That's because the empty
;; set is a subset of itself.
;; The power set of a non-empty set A with first element a is
;; equal to the concatenation of two sets:
;; - the first set is the power set of A - {a}. This
;; recursively gives us all those subsets of A that
;; exclude a.
;; - the second set is once again the power set of A - {a},
;; except that a has been prepended aka consed to the
;; front of every subset.
;;
