MIT 6.001                                       Fall, 1997
Instructor: A. Meyer

                 Recitation #7, Notes for Fri., 10/17/97
           (and 5 min problem #11, sent by email 10/17 4:45pm)

We briefly discussed handling repeated occurrences of the same pattern
variable along the lines of PS5: initially by not allowing repeated
variables (since an equality constraint can be imposed on distinct
variables by a rule retriction), and then by allowing repeated variables
and building the "match the same value" constraint into the dictionary
constructors.

Then we had a reminder about "dotted-tail" notation for procedure
parameters and explained how APPLY works:
                     (apply proc (list a1 a2 ... an))
evaluates exactly the same as
                     (proc a1 a2 ... an).

So (apply append '((1 2) () (3 4 5) () (7))) acts like
   (append '(1 2) '() '(3 4 5) '() '(7)) ==> (1 2 3 4 5 7)

Then we noted the truth about MAP: it takes 2 OR MORE arguments.  If PROC
takes n args and l1 l2 ... ln are lists  of length k+1, then

(map proc l1 l2 ... ln) evaluates to the same value as

(list (proc (list-ref l1 0) (list-ref l2 0) ... (list-ref ln 0))
      (proc (list-ref l1 1) (list-ref l2 1) ... (list-ref ln 1))
                                 .
                                 .
                                 .
      (proc (list-ref l1 k) (list-ref l2 k) ... (list-ref ln k)))

For example

(map list '((1 2 3) (4 5 6) (a b c) (d e f))) ==>
                  ((1 4 a d) (2 5 b e) (3 6 c f))

so if we thought of R = ((1 2 3) (4 5 6) (a b c) (d e f)) as the rows of a
3 x 4 matrix, then (map list R) is the rows of the 4 x 3 matrix equal to
the "transpose" of R.

Note that when n=1, the above agrees with the simple definition of map
given in lecture.  Let's now call MAP1 this procedure with the simple
definition:

(define (map1 f l)
  (if (null? l)
      '()
      (cons (f (car l))
            (map1 f (cdr l)))))


IN CLASS EXERCISE: Complete the definition:

(define (map f l1 . l-of-ls)
  (if (null? l1)
      '()
       ...))

HINT: the definition will use MAP1 and APPLY.

There wasn't time to finish this exercise, so we left the solution as
5 MIN PRESENTATION PROBLEM #11 FOR WED 10/22.


SOLUTION:

(define (map proc lst1 . lsts)
  (if (null? lst1)
      '()
      (let ((cars (map1 car lsts))
            (cdrs (map1 cdr lsts)))
        (cons (apply proc (cons (car lst1) cars))
              (apply map
                     (cons proc
                          (cons (cdr lst1) cdrs)))))))

The definition comes out more elegantly if we allow MAP to work for ZERO
or more list arguments, instead of ONE OR MORE.  We define -- somewhat
arbitrarily --
                   (map proc)
to be the same as
                   (list (proc)).


(define (map proc . lsts)
  (cond ((null? lsts) (list (proc)))
        ((null? (car lsts)) '())
        (else (cons (apply proc (map1 car lsts))
                    (apply map 
                           (cons proc (map1 cdr lsts)))))))