Math 372 Homework 1		Lisp	Dordal 	
Due: Wed, Sept 15, 2004

Write the following functions in Lisp. Sumcubes should use ordinary arithmetic recursion; the others should use cdr recursion. As far as editing lisp is concerned, I suggest using Allegro Common Lisp (eg the trial version) and typing your functions in an edit window (notice how this editor gives a visual indication of matching parentheses), and then save into a file. 

Email me the file of your function definitions (as a text attachment), and paste in a demo session if you wish. None of your functions should use SETQ internally, although you may use SETQ to set some global constants for use in examples. Be sure your email includes your name and states what assignment you are submitting.

To use a file in ACL, first create the file with File => New, and save it in an appropriate place, in a suitable directory with a name like hwk1.lisp. Later you can open it with File => Open. To load the file into your Lisp session (in the debug window), select the debug window and then type the following top-level commands (note that they don't have parentheses)
	:cd c:/pld/372/fall04		;; or whatever directory
	:ld hwk1.lisp

sumcubes: 
This should take a number, n, and return the sum 1*1*1 + 2*2*2 + ... + n*n*n. Thus, (sumcubes 0) returns 0, and (sumcubes 4) returns 100 (=1+8+27+64).


sumlist: 
This should take a list and return the sum of all the numbers in the list, at the top level. Thus, (sumlist '(1 2 (3) (4 a) nil b 5)) should return 1+2+5=8; the numbers 3 and 4 are not at the top level. Use NUMBERP to check if a thing is a number.


pairup:  
This should take two lists of the same length and pair up the corresponding entries into a list of two-element lists. Thus, 
(pairup '(a b c) '(1 2 3)) should return ((a 1) (b 2) (c 3)). This function will need cdr recursion on both parameters; if the parameters are x and y then the recursive call should include something like
	(pairup (cdr x) (cdr y))
i.e. this involves cdr recursion on both parameters. You will also, of course, have to form the list of (car x) and (car y) [use (list (car x) (car y))], and stick this onto the front.

Try to avoid using the length function to see if the lists are the same length. In the event that the lists are not the same length (and using cdr recursion you will discover this when one of the lists is nil and the other isn't), you can use the function ERROR to cause an exit. Specifically, use of the following
	(error "pairup: lists of unequal length")
will terminate your function. Unfortunately, it will also start the debugger; you may have better luck with ABORT, and also some mechanism for generating a line of output. Note that errors discovered deep within the recursion are particularly difficult to handle gracefully without some such mechanism.


countwhat:  
This should take a list and a predicate, and return the count of the number of elements of the list that satisfy the predicate. Here is, for comparison, a function that returns a list of the things that satisfy the predicate:

(defun filter (lis pred)
  (cond
     ((null lis) nil) 	;; nobody satisfies pred.
     ((funcall pred (car lis)) (cons (car lis)  
                                     (filter (cdr lis) pred))) 
			;; note use of pred and funcall!
     (t  (filter (cdr lis) pred))))

As examples, you might try (countwhat '(a 1 c 2 b e) #'numberp) and also the same list with the predicates #'symbolp and #'atom. You should also try an example with a different, hierarchical, list (e.g. (a (b) c (2 3) 4)). #'fname is the same as (function fname) and is preferred in theory to 'fname (or (quote fname)).


union:
This should take two lists, L1 and L2, and return the list of elements that appear in either list. The result differs from APPEND in that you should remove duplicates; you may assume that neither L1 nor L2 has duplicates although if either does then at worst your function should compute the union also with duplicates. For example, (UNION '(A B D) '(B C E)) should return something like (A B C D E), although (A D B C E) (or other orders) is also acceptable. Hint: use MEMBER to check if (car L1) is duplicated in L2; if so, do not include it in the union. Here is INTERSECT for comparison:

(defun intersect (L1 L2) 
  (cond ((null L1) nil)
        ((member (car L1) L2)    ;; put it in intersection
         (cons (car L1) (intersect (cdr L1) L2)))
        (t (intersect (cdr L1) L2))))