Comp 372 study guide answers

> 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.

(defun equal (x y)
     (cond ((and (atom x) (atom y))  (eql x y))    ; atomic case
           ((or (atom x) (atom y)) nil)       ;; one atom and one nonatom!
           (t (and (equal (car x) (car y)) (equal (cdr x) (cdr y))))))
 
Note the third cond clause (and, for that matter, the first) returns
a Boolean expression representing the return value. Also note that
the above EQUAL works equally well (so to speak) for both lists and atoms.


> 2. Write a function UNIQ, 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.

For each element of the list, if it appears in the remaining part of the list,
take it out. Only the final instance will be saved.
 
(defun uniq (L)
     (do ((result nil))
         ((null L) (return result))
        (if (not (member (car L) (cdr L)))
            (setq result (cons (car L) result)))
        (setq L (cdr L)))) 

This looks like it should be easy with REMOVE-IF, except that
REMOVE-IF applies its predicate to each *element* of the list,
and that predicate has no "access" to the cdr of the list at that point.
We need something that doesn't work with the successive elements,
but instead works with the successive cdrs, as below:
    

> 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 #'(lambda (L) (if (not (member (car L) (cdr L)))
                                      (setq result (cons (car L) result))))
                    lis)
           result))
 
Note the similarity to #2.


> 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)...)). 
 
Applying no functions (null flis) means x is unchanged:

listapplier []   x = x 
listapplier f:fs x = f (listapplier fs x)

The type of this function is, where a is the type of x,
	[a -> a] -> a  -> a
That is, the first parameter is a list of functions a->a.


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

Fractional list -> Fractional;  foo adds up a list of reals. 
The result type must be real because 0.0 is, and since we're 
adding to the result type, that means the list components must 
also be real.

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

L is a list and the result type is int. Since headd(L) is being 
applied to 1, head(L) must be a function, that takes an Int as 
argument. It must also return int, because the result must be 
compatible with 0. 

If L is the list of Int->Int functions [f1,...,fn], then bar(L) is
f1(1)+f2(1) + ...+ fn(1).

The type is [Int->Int] -> Int

> 6. Consider the following function in C++. Rewrite it so that it 
> does not use assignment. 

Or, more specifically, so that it uses recursion instead of a loop.

> 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;
> }
 
int looper (int i, int m, int n) {
    if (i<n) {
	return looper(i+1, m+2*(i+1)+1);
    } else return m;
}

main() {
    cout << "The answer is: " << looper(0, 0, readint());
}


#7 won't be on the exam; macros will NOT be on the exam. 
But here is the answer anyway.

> 7. Suppose we define a swap macro so that (swap X Y) expands into 
> (let ((temp X)) (setq X Y) (setq Y temp)). 
> Lisp does have arrays; if A is an array the (aref A n) returns the 
> nth component of A and (setq (aref A n) x) does what would be 
> written in C++ as A[n]=x. What happens if we call 
>      (swap n (aref A n)), 
> when n is initially 4 and the array A is indexed starting at 1 and 
> has components 5,4,3,2,1?
 
The idea here is that we're exchanging n and a[n].
The issue has nothing to do with Lisp; it would apply in any
language with macros (that is, statements that expand into
inline code).

The swap statement expands into 
    (let ((temp n)) (setq n (aref A n)) (setq (aref A n) temp))
Temp would be set to 4. With the array as above, the first setq
would leave n = (aref A 4) = 2.

The problem occurs with the second setq: (setq (aref A n) temp).
N is now *2*, not 4, and so we assign TEMP to (aref A 2).
N has *changed* since we entered the function, and so we update
the wrong A[N]!

If swap were written in C++ using reference parameters, 
we would evaluate the *locations* of both arguments at the 
time of entry to swap. Here, though, the location of (aref A n), 
which depends of course on n, isn't evaluated until the 
expression is actually used. In the meantime, n changed.


> 8. Give a tail-recursive version of the FACTORIAL (FACT) function
> in Lisp.

(defun fact (n) (auxfact n 1))

(defun auxfact (x y) ;; computes x! * y
    (if (= x 0) y
        (auxfact (1- x) (* x y))))


> 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)...)).

(defun repeat (f n x)
    (if (= n 1) (funcall f x)   ;; or (if (= n 0) x ...)
        (funcall f (repeat f (1- n) x))))


> 10. Do the preceding problem using tail recursion.

We just move the call to f in the recursion to *inside*:

(defun repeat (f n x)
    (if (= n 1) (funcall f x)   ;; or (if (= n 0) x ...)
        (repeat f (1- n) (funcall f x))))