Exercises in this lecture  previous -- Keyboard shortcut: 'p'  next -- Keyboard shortcut: 'n'  Go to the slide, where this exercise belongs -- Keyboard shortcut: 'u'  

Exercise 3.3
The append function **

The function append, which is a standard Scheme function, concatenates two or more lists. Let us here show a version which appends two lists:

  (define (my-append lst1 lst2)
       (cond ((null? lst1) lst2)
             (else (cons (car lst1) (my-append (cdr lst1) lst2)))))

We will now challenge ourselves by programming an iterative solution, by means of tail recursion. We start with the standard setup:

  (define (my-next-append lst1 lst2)
    (my-next-append-1 lst1 lst2 ...))

where my-next-append-1 is going to be the tail recursive function:

  (define (my-next-append-1 lst1 lst2 res)
    (cond ((null? lst1) ...)
          (else (my-next-append-1 (cdr lst1) lst2 ...))))

Fill out the details, and try out your solution.

Most likely, you will encounter a couple of problems! Now, do your best to work around these problems, maybe by changing aspects of the templates I have given above.

One common problem with iterative solutions and tail recursive functions is that lists will be built in the wrong order. This is due to our use of cons to construct lists, and the fact that cons operates on the front end of the list. The common medicine is to reverse a list, using the function reverse, either on of the input, or on the output.

Solution