6.001 Recitation #7                             Fall 1997
Prof. Albert R. Meyer

                5-minute-problem #7: Tail-Recursive Append
                      (posed in email Sun, 9/28/97)


APPEND is the operation of putting the elements in two (or more) lists
next to each other to form one longer list.  We use the notation "." for
APPEND, so x.y is the list formed by appending the list x to the list y.
For example, if x is the list whose output representation is (1 2), and y
is (a b c), then
                  x.y =  (1 2).(a b c) = (1 2 a b c)
Since the empty list NIL has no elements, putting its elements next to
those of any list z has no effect:
                         z.NIL =  z  =  NIL.z

The standard recursive definition of APPEND is based on one more obvious
USEFUL FACT:
        (e1 e2 - - -).z =  CONS(e1, (e2 - - -).z)


(define (append l1 l2)
  (if (null? l1)
      l2
      (cons (car l1) (append (cdr l1) l2))))

Question 1. Draw a box-and-pointer diagram illustrating the results of
        (define x (list 1 2))
        (define y (list 'a 'b 'c))
        (define z (append x y))

Question 2. Give a tail-recursive definition of APPEND.  (Hint: Try
defining a tail-recursive REVERSE procedure first, where, for example,
        (reverse (list 1 2 3 4)) ==> (4 3 2 1)


----------------------------------------

                           SOLUTION (presented 10/01)

       _______     _______ 
x --> | 1 |  -|-->| 2 | / |
       -------     -------

       _______     _______     _______ 
y --> | a |  -|-->| b |  -|-->| c | / |
       -------     -------     -------
         ^
         |____________________
                              |
                              ^
       _______     _______    |
z --> | 1 |  -|-->| 2 |  -|-->
       -------     -------    

NOTE: The result of (APPEND L1 L2) is a list consisting of a copy of the
"spine" of L1 with the last cons-cell connected to the ORIGINAL L2 -- NOT
A COPY OF L2.  The number of new cons-cells created is EXACTLY length(L1),
NOT the length of the result.  The Time of (APPEND L1 L2) is
Theta(length(L1)), NOT Theta(length(L1) + length(L2)), precisely because
the result "shares" L2.


Bruce's ingenious solution to implement an ITERATIVE APPEND:

(define (append-iter l1 l2)
  (define (reverse-append l1 l2)
    (if (null? l1)
	l2
	(reverse-append (cdr l1) (cons (car l1) l2))))
  (reverse-append (reverse-append l1 nil) l2))