Homework Assignment 2

CS 2360
Winter 1997
Homework Assignment 2
Due no later than 8:00am, Monday, January 27, 1997

One of the amazing things about LISP is that so much of the language can be
defined in terms of just a very few pre-existing functions.  In this
assignment, you will be constructing your own versions of 14 pre-existing
Common LISP functions by using a relatively small subset of Common LISP.
In the process of constructing those 14 functions, you'll not only get to
practice your LISP programming skills, but you'll also gain familiarity with
a lot of very useful LISP functions such as APPEND and ASSOC.  Then you'll
get a chance to do a little bit more.

The functions that you'll be constructing will, in some cases, be
simplifications of the pre-existing functions in that your versions will not
have to deal with optional arguments (which we haven't talked about much
anyway).  In all other regards, however, the behavior of your functions should
mimic the behavior of the pre-existing functions.  You can check out the
behavior of the pre-existing functions by playing around with them while
you're working in the LISP interpreter, and, if you're especially interested,
you can find exact specifications for those functions in "Common LISP: The
Language" by Guy Steele or "ANSI Common Lisp" by Paul Graham.

The functions that you are to define are listed below, along with examples of
how we expect them to work.  For all the functions, you can obtain the name of
their pre-existing counterparts by just removing the prefix "my-".

To construct these functions, you may use DEFUN, COND, IF, NULL, FIRST, REST,
CONS, the equality predicates (EQ, EQL, EQUAL, EQUALP, and =), QUOTE (or '), 
the arithmetic functions (+, -, *, and /), and the Boolean functions (AND, 
OR, and NOT; we haven't mentioned these in class yet, but if you look them 
up you'll see what they're all about pretty quickly).  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.  Don't use assignment, and don't use 
any control structure other than recursion.

If you were to look through various LISP books, you might find many
solutions to the problems below.  In fact, some of these were solved
today in class, and all of them were solved by CS2360 students last
spring, because this is the exact same assignment I gave them.  So it's
going to be relatively easy to find solutions to all these problems
if you want to.  But knowing where to find these answers isn't going to
help you in the weeks to come; if you can't solve most of these problems
on your own now, you're going to encounter great difficulty with future
homework assignments.  So please, do yourself a very big favor and
solve as many as you can on your own and don't go looking up the
answers in textbooks or elsewhere.

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

Here are the functions we want you to construct:

1) my-member

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

2) my-append

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

3) my-remove-duplicates

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

4) my-reverse

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

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

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

7) my-intersection

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

8) my-union

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

9) my-make-list

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

10) my-subseq

(my-subseq '(a b c d) 0 3) => (a b c)
(my-subseq '(a b c d) 1 3) => (b c)
(my-subseq '(a b c d) 2 3) => (c)
(my-subseq '(a b c d) 3 3) => nil
(my-subseq '(a b c d) 1 4) => (b c d)

11) my-assoc

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

12) my-insert

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

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

14) my-last

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

15) Reconsider your solution to problem 1, in which you defined MY-MEMBER.
If you didn't use tail recursion in solving problem 1, provide a new
solution in which you do use only tail recursion.  If you did use
tail recursion in solving problem 1, provide a new solution in which
you use recursion, but not tail recursion.

16) Reconsider your solution to problem 2, in which you defined MY-APPEND.
If you didn't use tail recursion in solving problem 2, provide a new
solution in which you do use only tail recursion.  If you did use
tail recursion in solving problem 2, provide a new solution in which
you use recursion, but not tail recursion.

17) Reconsider your solution to problem 4, in which you defined MY-REVERSE.
If you didn't use tail recursion in solving problem 4, provide a new
solution in which you do use only tail recursion.  If you did use
tail recursion in solving problem 4, provide a new solution in which
you use recursion, but not tail recursion.

18) Reconsider your solution to problem 5, in which you defined MY-REMOVE.
If you didn't use tail recursion in solving problem 5, provide a new
solution in which you do use only tail recursion.  If you did use
tail recursion in solving problem 5, provide a new solution in which
you use recursion, but not tail recursion.

19) Reconsider your solution to problem 6, in which you defined
MY-SUBSTITUTE.  If you didn't use tail recursion in solving problem 6,
provide a new solution in which you do use only tail recursion.  If you
did use tail recursion in solving problem 6, provide a new solution in
which you use recursion, but not tail recursion.

20) Reconsider your solution to problem 7, in which you defined
MY-INTERSECTION.  If you didn't use tail recursion in solving problem 7,
provide a new solution in which you do use only tail recursion.  If you
did use tail recursion in solving problem 7, provide a new solution in
which you use recursion, but not tail recursion.



Copyright 1997 by Kurt Eiselt.  All rights reserved.