Logic 1, WS 2007. Homework 6, given Dec 6, due Dec 13.

1. Design a “pattern program” for computing the reverse of a list, starting from the properties of the function when applied to the empty list and to a list formed by appending an element to a list.

2. Transform this program in a functional program and study its behaviour on a list with three elements.

3. Use the associativity of concatenation of lists in order to transform the trace obtained above into a list of pairs.

4. Design a tail recursive auxiliary function which can be used to compute the reverse of a list. Hint: the process is similar to the design and the transformation of the function which computes the sum of the first n numbers, which was studied in the lecture.