# Recitation 7

Today's idea: Fun with list functionals: recursion with map

### Symbols and Quote Special Form

From yesterday's lecture:
•  '(a b c) evaluates to the list containing the symbols a, b, c
• (quote X ) evaluates to a value whose external representation is X
• ' is short for quote

### Exercise 0: Substitution

Replace every occurrence of a symbol in a list with another symbol.
For example:

(substitute 'w 'r '(r a s c a l l y   r a b b i t))
> (w a s c a l l y w a b b i t)

### Exercise 1: Cartesian Product

Cartesian product of two sets s and t is:
• set of all pairs
• with first element from s
• and second element from t
Represent set as a list without duplicates.
Now cartesian-product has type: list<A>, list<B> -> list <A x B>

Example

• (define p '(a b c))
• (define q '(d e f))
• (cartesian-product p q)
• evals to ((a . d) (a . e) (a . f) (b . d) (b . e) (b . f) (c . d) (c . e) (c . f))
Questions
• How big is the CP of p and q in terms of sizes of p and q?
Exercise
• complete the definition of cartesian product
• (define (cartesian-product p q) ...)
• hint: use map and a recursive call

### Exercise 2: Powerset

Powerset of a sets s is:
• set of all SETS that are subsets of s
Represent set as a list without duplicates.
Now powerset has type: list<A> -> list <list<A>>

Example

• (define p '(a b c))
• (powerset p)
• evals to  ((a b c) (a b) (a c) (a) (b c) (b) (c) ())
Questions
• How big is the PS of p in terms of size of p?
Exercise
• complete the definition of powerset
• (define (powerset p) ...)
• hint: for each element, there are two cases ...

### Exercise 3: Permutations

Permutation of a list p is:
• set of all lists that can be made by placing elements of p in any order
• assume that elements of p are distinct
Permutation function has type: list<A> -> list <list<A>>

Example

• (define p '(a b c))
• (permutation p)
• evals to  ((a b c) (a c b) (b a c) (b c a) (c a b) (c b a))
Questions
• How many permutations of p?
Exercise
• complete the definition of permutations
• (define (permutations p) ...)
Hints
• think about removing one element, and combining with permutations of the rest?
• do this for all elements now

### Definitions Used

(define (accumulate f base p)
(cond
((null? p) base)
(else (f (car p) (accumulate f base (cdr p))))))

(define remove (lambda (item x) ... (hidden for now: part of PS3)

### Definitions We Developed

(define (subs p from to)
(if (null? p)
p
(let ((e (if (equal? (car p) from)
to
(car p))))
(cons e
(subs (cdr p) from to)))))

(define (subs p from to)
(map (lambda (x) (if (equal? x from) to x)) p))

(define (cartesian-product p q)
(cond ((null? p) '())
(else (append
(map (lambda (x) (cons (car p) x)) q)
(cartesian-product (cdr p) q)))))

(define (powerset s)
(if (null? s)
(list '())
(let ((ps (powerset (cdr s))))
(append
(map
(lambda (x) (cons (car s) x))
ps)
ps))))

(define (permutations p)
(if (null? p)
'(())
(accumulate append '()
(map (lambda (first-item)
(map (lambda (perm) (cons first-item perm))
(permutations (remove first-item p))))
p))))

Daniel Jackson
September 28, 1999