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. ;;2 (define (power-set set) (if (null? set) '(()) (let ((power-set-of-rest (power-set (cdr set)))) (append power-set-of-rest (map (lambda (subset) (cons (car set) subset)) power-set-of-rest))))) #|kawa:2|# (power-set '(1 2 3 4)) (() (4) (3) (3 4) (2) (2 4) (2 3) (2 3 4) (1) (1 4) (1 3) (1 3 4) (1 2) (1 2 4) (1 2 3) (1 2 3 4)) #|kawa:3|# (power-set '("Nils" "Nolan" "Eric")) (() (Eric) (Nolan) (Nolan Eric) (Nils) (Nils Eric) (Nils Nolan) (Nils Nolan Eric)) #|kawa:4|# (power-set '(#\a #\e #\i #\o #\u)) (() (u) (o) (o u) (i) (i u) (i o) (i o u) (e) (e u) (e o) (e o u) (e i) (e i u) (e i o) (e i o u) (a) (a u) (a o) (a o u) (a i) (a i u) (a i o) (a i o u) (a e) (a e u) (a e o) (a e o u) (a e i) (a e i u) (a e i o) (a e i o u)) You know an algorithm is dense when the function comment is twice as long as the implementation.  Note the use of a single let binding to preserve the value of the recursively generated power set. It’s because of the let statement that we reduce a doubly recursive implementation to a singly recursive one. That actually reduced the running time of the algorithm quite a bit. Of course, the algorithm is cool in its own right. But it’s particularly cool in Scheme, because Scheme allows the on-the-fly lambda to be implemented in terms of the car that was excluded from the recursive call. That’s how the second half is transformed from a set that excludes the first element to one that embraces it. Embraces. How dramatic. You’re rolling your eyes, I know. Moving on. Contrast this implementation to the version implemented in C or C++. They’re both compile time languages where there size of everything needs to be decided ahead of time. In C, you work around the language and use the void *auxData of VectorMap (and you also make all of the copies yourself.) In C++, you use the function object to embed the first element inside so that operator() has access to it when it’s executed (and you also make all of the copies yourself.)3 Permutations Now consider the problem of generating all of the permutations of a list. Let’s start with a simple illustration by considering the permutations of 1, 2, 3, 4. They’re listed here in four columns: Notice that the first column includes all of those permutations that start off with a 1, and that there are six of them. The second column includes the permutations starting out with a 2, similarly for columns three and four. Each column has 3! = 6 permutations, because each places some number at the front of every permutation of the other three. What’s been said so far can be framed in terms of mapping. One significant component of the map is the transformation of each element into the set of those permutations that begin with it. The mapping routine, whatever it is, needs to take an element and generate a list of permutations. Let’s diagram it. (1 2 3 4) ((<1-permutations>) (<2-permutations>) (<3-permutations>) (<4-permutations>)) If there are four elements in the original list, there are four elements in the final list generated by any call to map. We can concatenate the four lists by applying append just prior to exit. That means we have a partial implementation, and it looks like this: (define (permutations items) (if (null? items) '(()) (apply append (map function-to-be-determined items)))) This mapping function isn’t exactly trivial. It needs to transform an isolated element into a list of permutations, where every permutation in that list begins with said element. We can write it as a lambda function, which recognizes that its incoming argument is the element that needs to be at the front of all the permutations it generates. In order to generate those permutations, it must