Comp210 Exam#1 Solutions -- Problem 1

1998 Spring

Write the function append2, which takes two <list-of-symbol> s and returns the contents of the first followed by the contents of the second. Show the (recursive) calls to your function that occur in the hand-evaluation of (append2 (list 'cyan 'teal) (list 'ochre)); the answer should be (list 'cyan 'teal 'ochre) (If two lines denote equal values, connect them with ``=''; don't write down a series of unrelated values.)
Hint: recur only on the first argument, never varying the second argument.

For this problem, you don't need to write the data-definition and template for a <list-of-symbol>, though if you are stuck these might help you, and they can provide partial credit.

You of course cannot appeal to the built-in function append.

SOLUTION:

For this problem, we will use the hint kindly provided by the exam, and recur only on the first argument. What this means is that we can use the single-list template, as follows: 

(define list-fun
  (lambda (los1 los2)
    (cond ((null? los1) ... los2 ...)
          (else ... (first los1) ...
                (list-fun ... (rest los1) ...)
                ... los2 ...))))

Please notice two things about this template:

  1. los2 appears only as an argument, not as a control-flow buddy. In other words, our template treats los2 as a single piece of data, like a number or a symbol. We write the template this way because the hint suggests it.
  2. Part of the design recipe is to put all of the possible pieces in the right-hand side of each conditional case. That doesn't mean we have to use all of them, just that those are the pieces we have available to combine and rearrange.

Now, let's think about how to solve this problem, case by case. In the first case, when los1 is null, what is the result of appending the two lists? It is simply los2, because los1 is empty. So this case is simple. What about when los1 is not null? In this case, we want to recur on the first argument, so the pieces we have to work with include the first of the list, the rest of the list, and the second list, los2. Now we make the recursion assumption; we assume that append2 works for smaller pieces of data, so we can call append2 recursively on (rest los1) and los2. That will give us the result of appending the rest of the first list with all of the second one. So once we've got this result, how do we combine it with the other piece, (first los1)? Well, we can simply cons that first element on to the result we've obtained, and the code we end up with is this: 

(define append2
  (lambda (los1 los2)
    (cond ((null? los1) los2)
          (else (cons (car los1)
                      (append2 (cdr los1) los2))))))