Exercises in this lecture   Go to the notes, in which this exercise belongs -- Keyboard shortcut: 'u'   Alphabetic index   Course home   

Exercise solution:
The append function

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.

Here is my solution

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

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

In order to compensate for the 'reversing problem' I pass lst1 in reversed form to the iterative function my-next-append-1.

Also I pass the list lst2 as the initial value of res. This is crucial in order to get the lists appended at all.

As an additional observation, the second parameter of my-next-append-1 is not used. Thus, it can be eliminated. I have not done so, however.