Programming Assignment #3

Last modified: "April 26, 2000 17:18:44 by evett"
Due: beginning of class, Wednesday, March 15.
From Graham's ANSI Common Lisp: Ch.3: 1,3,5; Ch. 4: 1,2,4; Ch.5: 5,7.

Use of global variables in the solutions to these problems will incur a full grade penalty. (Remember that a global variable is any variable that is neither a parameter to a function, nor declared in a LET statement.

3.1 Show the following in box notation (see Figure 14.1 of Sebesta). Note that the box notation of the dotted pair (x . y) is a box, with an arrow dropping directly from each half of the box, one to "x" the other to "y".

  1. (a b (c d))
  2. (a (b (c (d))))
  3. (((a b) c) d)
  4. (a (b . c) . d)
3.3 Define a function that takes a list and returns a list indicating the number of times each (using eql test) element appears, sorted from most common element to least common: 
> (occurrences '(a b a d a c d c a))
((A . 4) (C . 2) (D . 2) (B . 1))

For this function, you may want to use the built-in sort function. sort takes two arguments: a list, and a function. The function should take two arguments, each an elemnt of the list, and return T if the first argument should appear before the second in the sorted list. For example: 
> (sort '(1 3 2 6 4 2 0 8) #'<)
(0 1 2 2 3 4 6 8)
You should use sort in conjunction with a function you write.

3.5 Suppose the function pos+ takes a list of integers and returns a list comprised of each element of the original list plus its position there: 

> (pos+ '( 7 5 1 4))
(7 6 3 7)
Define this function using (a) recursion, (b) iteration, (c) mapcar.

4.1 Define a function, rotateArr to take a square array and returns the array, rotated 90 degrees clockwise. You'll need array-dimensions, which takes a single argument, an array, and returns a list comprised of the cardinalities of the dimensions of the array. For example: 

> (array-dimensions (make-array '(2 3)))
(2 3)

Hint: Remember that rotation is not the same as flipping the array across a diagonal!

4.2 The Lisp reduce function takes two arguments, a function and a list. reduce returns the result of successive applications of the function to successive elemtns of the list and previous results of the function. For example: 

> (reduce #'+ '(1 3 7 3))
14

Which is the same as: (+ (+ (+ 1 3) 7) 3)

Use reduce to define:

  1. my-copy-list, which takes a single argument, a list, and returns a brand new copy of the list. (You'll have to build the copy , and element at a time.)
  2. my-reverse, which takes a single argument, a list, and returns a copy of the argument, but with the order of the elements reveresed.
Note that you may not use Lisp's built-in reverse and copy-list functions to solve this problem.

5.5 Define iterative and recursive versions of a function that takes a character xand string v, and returns a list of all the objects that immediately precede x in v: 

> (precedes #\a "abracadabra")
(#\c #\d #\r)

5.7 Define a function that takes a list of numbers and returns true iff the difference between each sucessive pair of them is 1. For example, (diff1 '(1 2 3 2 1)), should return T. Define this function three different ways, using:

  1. recursion (call it diff1-recur)
  2. dolist (call it diff1-iter)
  3. mapc and return (call it diff1-mapc)