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

what's tricky about this problem: need to take elements from the middle of the list
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