Comp 372 sample exam/study guide	Dordal	Oct 13, 2004	

The exam will be Wednesday, Oct 20, and will be open book (but not notes). 
However, you will make the best use of your time if you plan on using 
the books only as an occasional reference.  

Here are some Lisp things you should know:
	recursive functions (arithmetic recursion, cdr & car/cdr recursion
	iteration (via DO loops)
	what tail-recursive functions are
	use of MAPCAR, etc, and LAMBDA functions
Here are some Haskell things you should know:
	Recursive function definitions (numeric and list)
	Function definitions involving patterns
	use of list comprehension and lambda
	Basic Haskell type inference / unification rules 

Most of the Lisp material covered so far has been in chapters 2 & 3
of Paul Graham's book.

Here are some sections of the Haskell book by Thompson that
are particularly important:

Chapter 3: 3.4, on guards
Chapter 4: recursion
Chapter 5: 5.1-5.4 on tuples, lists, and list comprehensions
	   5.7: polymorphism
	   5.8: built-in functions in Prelude.hs
Chapter 7: 7.1-7.3 on defining list functions with patterns
Chapter 9: 9.1 - 9.3: map, filter, fold, splitting
Chapter 10: functions as values: 
	   10.3 - lambda expressions; 10.4 - partial application
Chapter 13: 13.2, on polymorphic type checking
	   

Here are a few sample problems
1. Define (EQUAL x y) in lisp. Two atoms are EQUAL if they are EQL; 
two lists are EQUAL if the cars and cdrs, respectively, are EQUAL. 
This is car/cdr recursion.

2. Write a function UNIQ in lisp, that takes a list of symbols and 
eliminates duplicates. For example, (uniq '(a b c b a)) could 
return either (a b c) or (c b a). Use a DO loop.

3. Write UNIQ using a lambda function and MAPLIST. 
(MAPLIST fun '(a b c d e)) is like MAPCAR, but fun is applied 
successively not to the *elements* a, b, c, d, e, but instead 
to the successive cdrs: 
((fun '(a b c d e)) (fun '(b c d e)) (fun '(c d e)) (fun '(d e)) (fun '(e)) (fun nil)). 
Here is something to get you started; stick an element onto the 
result when it's *not* in the rest of the list:
   	(defun uniq (lis)
	      (let (result nil)
	            (maplist __________________________________ lis)
	            result))

4. Write a function in Haskell that takes a list of functions, 
flis = [f1, f2, ....fn], and an x, and returns f1(f2(...(fn(x)...)). 

5. What is the type of the following Haskell functions:
(a). 
foo [] = 0.0 
foo (x:xs) = x + foo(xs)

(b). bar (L) = if null L then 0 else (head L)(1) + bar(tail L);

6. Consider the following function in C++. Rewrite it so that it 
does not use assignment. You may assume that a function readint() 
is available that returns the next integer in the input:
	
main() {
    int n, m =0, i=0;
    cin >> n;
    while (i<n) {
        i++;        m += 2*i+1;
    }
    cout << "The answer is: " << m;
}

7. Suppose we define a swap macro in Lisp so that ...

OMITTED; macros won't be on the exam.

8. Give a tail-recursive version of the FACTORIAL (FACT) function
in Lisp; that is, the value returned by the inner recursive call
is not further modified by the current function instance.
Hint: (trfact n m) should return n!*m; you get (fact n) as 
(trfact n 1).

9. Define a lisp function REPEAT that takes a function f, and an
integer n, and a value x, and returns f(f(...n times...f(x)...)).

10. Do the preceding problem using tail recursion.