CS 381, Spring 2002
Programming Assignment 1
Due: Monday, April 15

More on Lisp

In programming assignment zero we were introduced to the programming language Lisp. In this assignment we will continue our investigation of this language.

The major emphasis of this assignment is to get you thinking recursively. You might want to take a look at the course notes entitled ``thinking recursively''. A link to these can be found on the course web page.

In programming assignment zero we encountered the following recursive definition: 


> (defun length (x) (if (null x) 0 (plusOne (length (cdr x)))))

> (length `(a b c))
In your programming assignment you were asked to create another function, a program to compute the sum of the values in a list. If you played with this function you may have noted that it works fine for a list like (1 2 3), but what happens if we want to try a list like ((1 2) (3 (4 5)))? It won't work. We can fix this by making a nested if statement. If the argument is not null, then if it is an atom we add it to the sum of the cdr, otherwise if it is not an atom then we compute its sum recursively. 
> (defun sumAll (x)
  (if (null x) 0
    (+ (if (atom (car x)) (car x) (sumAll (car x))) (sumAll (cdr x)))))

Trace this carefully to see how the two different recursive calls are being used.

The Programming Assignment

For this assignment I want you to place your commands into a file, named progOne, similar to the one you created for the first assignment. Comments at the beginning of this file should give your name, the assignment number, and the date, but not your student ID number. To help you debug your programs I will give you a test script (from a link in the web page). To test your progran, load your file, then load the test script. The test script will print values in pairs, first your output and then the correct output: 


> (load "progOne")
...
> (load "testScript" :print t )
(a b c)
(a b c)
(2 3)
(2 3)
...

When you think you have the entire problem solved, hand in just your file using the college of engineering web-based form. At some later point I will evaluate your solutions using a different test script, and e-mail back your grade.

For the first programming assignment, create a file containing the following definitions:

  1. The function plusOne which we defined in the previous assignment.
  2. The function addToEnd, from programming assignment zero.
  3. Using addToEnd, a recursive version of a function named reverse that will reverse the elements of a list (This function must use recursion).
  4. The function count, that will take two arguments, and count the number of occurrences of the first argument in the list given by the second argument, which is a simple one-level list. For example, 
    
>	(count 2 `(2 3 2 4))
2
  5. The function countAll, which will take two arguments, and count the number of occurrences of the first argument (which must be an atom) in the list given by the second argument, which can have arbitrary nested lists. For example, 
    
>	(countAll 2 `(2 (3 2) ((2 3 2) 2) 2))
6
  6. The function flatten, which takes an arbitrary list, and returns a single level list of all the elements in order. For example: 
    
>	(flatten `((2 3) 3 (4 5) 3))
(2 3 3 4 5 3)
  7. The function insert, which takes an integer value and a list that is assumed to be ordered list of integers (it may be empty). The function returns a new list in which the value is inserted in its proper place. For example: 
    
>	(insert 3 `(2 4 6 7))
(2 3 4 6 7)
  8. Lists can be used to represent a variety of different data structures. For example, suppose we want to represent the idea of a set, a collection of unique (that is, non-repeating) values. This can be done by writing a set of functions. Write the function setAdd. This function takes two arguments, an element and a set (which is being represented by a list). If the element is already in the set it simply returns the 2nd argument (that is, the set). If the element is not in the set it adds the element to the front, returning the new list. For example: 
    
>	(SetAdd 2 `(1 3 4))
(2 1 3 4)

>	(SetAdd 3 `(1 3 4))
(1 3 4)
  9. Write the function setIncludes. This takes as arguments an element and a set. It returns true if the element is in the set, and nil otherwise. 
    
>	(SetIncludes 2 `(1 3 4))
nil

>	(SetIncludes 3 `(1 3 4))
t
  10. Write the function setRemove. This takes as arguments an element and a set. If the element is in the set it returns a new set with the element removed, otherwise it returns the argument set. For example: 
    
>	(SetRemove 3 `(1 3 4))
(1 4)

>	(SetRemove 2 `(1 3 4))
(1 3 4)

You can examine the testing script to see examples of the input and output for each of these.

Once more, note that I want you to solve these problems using only the features of Lisp I have described in this document. In particular, there are Lisp statements (such as set or replaca) that allow you to program in an imperative style, if you want. I do not want. I want you to restrict yourself to the functional style.