CS 2360 Summer 1998
Homework Assignment 2
Due no later than 8:00 a.m., Tuesday, July 14, 1998

***NOTE***HW Due dates are now Tuesday morning at 8:00 a.m.

For all these problems, make sure that you adhere to the constraints 
of the functional programming paradigm (e.g., access only information 
passed as parameters, return one value, no side effects, etc.).  
Furthermore, remember that you're programming for people, not for the 
benefit of the computer.  Write your code so that other people can 
understand it easily.  That means you should worry about modularity
and abstraction where appropriate, and you should employ meaningful 
function and parameter names.  Don't forget to document your code
with appropriate comments, and it wouldn't hurt to use indentation
to make your code look pretty (which in turn makes for happier and
more generous graders).

Each of the 20 problems specified below is worth 10 points.  Don't forget 
to worry about modularity, abstraction, meaningful function and
parameter names, reasonable comments, appropriate indentation, and
all that.

To construct these functions, you may use DEFUN, COND, IF, NULL, ATOM, 
LISTP, NUMBERP, FIRST, REST, CONS, LIST, ZEROP, the equality predicates  
(EQ, EQL, EQUAL, EQUALP, and =), the inequalities (<, >, >=, <=), QUOTE (or 
'), the arithmetic functions (+, -, *, and /), and the Boolean functions 
(AND, OR, and NOT).  You may not need all these functions, but they are 
available to you.  You may also use (or reuse) any function which you 
have defined.  Furthermore, if you must construct/use additional functions 
in support of your tail recursive solutions make sure that these 
supportive functions are also tail recursive (in other words, if you are 
to write a tail recursive function, you may not call an augmenting 
recursive helper function--all helpers must also be tail recursive).  
Also on problems that don't specify tail/augmenting (a few of them 
don't) you can do those however you like.

In testing these functions, please use more test data than the examples 
in this writeup.  To determine the exact behavior of these most of these 
functions, use the predefined functions which will have the same name as 
each of these functions without the "my-".  Each of your functions need to 
return the SAME result as the predifined one.


Implement the following functions which mimic their similarly-named
Common-Lisp counterparts.

1) my-member

   (my-member 'c '(a b c d e)) => (c d e)


2) my-append   augmenting recursive version

   (my-append '(a b) '(c d)) => (a b c d)


3) my-append-tr   tail recursive version

   (my-append-tr '(a b) '(c d)) => (a b c d)


4) my-remove-duplicates   augmenting recursive version

   (my-remove-duplicates '(a b a c a d)) => (b c a d)
   (my-remove-duplicates '(a b (a c) a d)) => (b (a c) a d)


5) my-remove-duplicates-tr   tail recursive version

   (my-remove-duplicates-tr '(a b a c a d)) => (b c a d)
   (my-remove-duplicates-tr '(a b (a c) a d)) => (b (a c) a d)


6) my-reverse    augmenting recursive version

   (my-reverse '(a b c)) => (c b a)
   (my-reverse '(a (b c) d) => (d (b c) a)


7) my-reverse-tr   tail recursive version

   (my-reverse-tr '(a b c)) => (c b a)
   (my-reverse-tr '(a (b c) d) => (d (b c) a)


8) my-remove

   (my-remove 'a '(a b a c a d)) => (b c d)
   (my-remove 'a '(a b (a c) a d)) => (b (a c) d)


9) my-substitute

   (my-substitute 'x 'a '(a b a c a d)) => (x b x c x d)
   (my-substitute 'x 'a '(a b (a c) a d)) => (x b (a c) x d)


10) my-intersection   augmenting recursion version

   (my-intersection '(a b c) '(b c d)) => (b c)  ; order is unimportant


11) my-intersection-tr    tail recursive version

   (my-intersection-tr '(a b c) '(b c d)) => (b c)  ; order is unimportant


12) my-union

   (my-union '(a b c) '(b c d)) => (a b c d)     ; order is unimportant



13) my-assoc

   (my-assoc 'a '((c d)(a b)(e f))) => (a b)
   (my-assoc 'c '((c d)(a b)(e f))) => (c d)


14) my-insert   (INSERT is not a Common Lisp function--see newsgroup)

   (my-insert 'a '(b c d e) 0) => (a b c d e)
   (my-insert 'a '(b c d e) 2) => (b c a d e)
   (my-insert 'a '(b c d e) 4) => (b c d e a)


15) my-nthcdr

   (my-nthcdr 0 '(a b c)) => (a b c)
   (my-nthcdr 2 '(a b c)) => (c)
   (my-nthcdr 4 '(a b c)) => nil


16) my-last

   (my-last '(a b c d)) => (d)
   (my-last '(a b (c d))) => ((c d))
   (my-last nil) => nil
   (my-last '(a b . c)) => (b . c)

17) my-flatten

   (my-flatten '(a b (c) d)) => (a b c d)
   (my-flatten '(a b (c (d) e))) => (a b c d e)
   (my-flatten '((((()))))) => ()

18) my-make-list   augmenting recursion version

   (my-make-list 3) => (nil nil nil)
   (my-make-list 0) => ()

19) count-atoms

   (count-atoms '(a b (c (d)))) => 4
   (count-atoms '(nil nil nil) => 0
   (count-atoms '()) => 0
   

20) rotate-left

    This function is going to work the same as the rotate-left
    that you wrote in hw1; however, this one will work on lists
    of arbitrary length.

    (rotate-left '(a b c d e)) => (b c d e a)
    (rotate-left '(a)) => (a)
    (rotate-left '(a b)) => (b a)



Good Luck!