**********************************************************************
File ~/../public/A0/README

Homework Assignment 0
CSE 150, UCSD
Winter 1997

Due:  Thursday, January 16, 10:00AM 
(NOTE: Special due date time so we can discuss it in class!)
**********************************************************************

>>> SUMMARY:

This assignment will acquaint you with the basics of defining functions
that manipulate lists in LISP.


>>> RULES:

In writing your function definitions, you may use any built-in LISP
function, special form, or macro introduced in Chapters 1 through 4 in
the Winston and Horn text, except for SET, SETF, and SETQ.  Also, you may
not use any iteration constructs such as DO, DOTIMES, DOLIST, or LOOP
--- so you will be writing recursive function definitions without
assignment statements:  real functional programming!

HOWEVER, it is often useful to use SETQ when TESTING your code.
E.g.,

USER[2]: (setq testlist '(1 2 3))
(1 2 3)
USER[3]: testlist
(1 2 3)
USER[4]: (SUMMATION testlist)	; Note NO QUOTES!
6

This saves a lot of typing. However, NO SETQ's SHOULD APPEAR IN YOUR
HOMEWORK FILE!!!

You may discuss your program with other students or the TA or the
professor.  However, you may not take written notes or copy anybody
else's program.  In writing your code, you are on your own.


>>> ASSIGNMENT:

This assignment has 4 parts, described below.  Each part involves
defining a function with a specified name.  (You may find it useful to
define some other functions too, if you wish.)  All these function
definitions should be put in a file named "hw0.cl" so that when that
file is loaded into LISP, evaluating calls to the functions will work
as required.  Make sure the file name and function names are spelled
correctly; your assignment will be graded in part by a computer
program, and computer programs don't handle misspellings very well.

Make sure your programs are commented in acceptable LISP style!

Your file "hw0.cl" must be submitted using the "turnin" utility
no later than the due time deadline specified above.  Once you
have done a "prep cs150w", just type "turnin hw0.cl" to submit
your solution file.

**NOTE** 
Make sure your code returns the correctly parenthesized answer.  
((Alpha Beta Gamma)) is NOT the same as (Alpha Beta Gamma) - one 
is a list of lists and the other is just a list.  

----------------------------------------------------------------------
Part I.

Define a function named SUMMATION.

SUMMATION takes one argument, a list of integers and returns the sum of the 
integers of that list.  For example:
	
	(SUMMATION '(1 2 3))

	would return:
	
	6

(HINT: You will need to use recursion in this problem.)

----------------------------------------------------------------------
Part II.

Define a function named LAST_NAMES.

LAST_NAMES takes one argument, a list of two element lists, as input.  The 
input will be of the form:

 ((firstname_1 lastname_1)(firstname_2 lastname_2)...(firstname_n lastname_n))

LAST_NAMES will filter the lastname field from the input and return a list of
just last names.  The output will be of the form:
	
 (lastname_1 lastname_2 ... lastname_n)

For example:
 
USER[3]: (LAST_NAMES '((Eddie Vedder)(Stone Gossard)(Jeff Ament)))

(VEDDER GOSSARD AMENT)

----------------------------------------------------------------------
Part III.

You are asked to write LISP code to compress an inventory listing.  The
inventory listing is given in the following format:

	((item_1 qty_1)(item_2 qty_2)...(item_n qty_n))

	For example:
	
	((widgets 2)(cogs 3)(bolts 1)(widgets 3)(bolts 2)(bolts 3))

As shown above, it is possible for there to be duplicate entries in
the inventory listing.  It would be desirable to compress such a list
so that each entry is unique, but the inventory of the list remains
the same as the input.  So for example, the above list would become:

	((WIDGETS 5)(COGS 3)(BOLTS 6))

In order to accomplish this you will need three functions.  The first
function is given below.  It takes a list with the above format and an
entry name (such as widgets) and returns the total quantity of items
with that name in the given list.

;;; Function: SUM_DUPLICATES
;;; Arguments: 
;;;	x: an inventory list of the form ((item1 amt1) (item2 amt2) ...)
;;;	y: an item
;;; Returns: The sum of the amounts for y in the list x
;;; Side effects: none

(defun SUM_DUPLICATES (x y)
  (if (endp x) 			             ; Check if list x is empty 
    0                                        ; if empty return 0
    (if (eq (caar x) y)         	     ; if not empty check if
				             ; first element of the first
				             ; list in x is equal to y 
      (+ (cadar x) (SUM_DUPLICATES (cdr x) y))  
					     ; if so, then add the second
					     ; element of the first list in 
					     ; x to the recursively determined 
					     ; value of SUM_DUPLICATES for the
					     ; rest of x and the same value of
					     ; y. 
      (SUM_DUPLICATES (cdr x) y))))          ; Otherwise, return the value
					     ; SUM_DUPLICATES for the
					     ; rest of x.
So 
  
  (SUM_DUPLICATES '((widgets 2)(bolts 3)(bolts 5)(widgets 3)) 'bolts)

returns:
  
  8

Using the "style" of the above function, write a similar function called 
REMOVE_DUPLICATES that takes a list of the above format and an entry name as 
input (just like SUM_DUPLICATES).  REMOVE_DUPLICATES will return a list that
does not contain *ANY* entries with the given name.  So for example:

  (REMOVE_DUPLICATES '((widgets 2)(bolts 3)(bolts 5)(widgets 3)) 'bolts)

would return:

  ((WIDGETS 2) (WIDGETS 3))

(HINT: SUM_DUPLICATES searches the inventory list for entries that match the 
       search parameter y, and recursively builds an integer that is the sum
       of the quantities of that entry.  For REMOVE_DUPLICATES, you want to 
       build a list that does not contain the entries that match the search
       parameter y.  Thus, both functions are looking for the same thing, but
       manipulate the data differently when found.)

----------------------------------------------------------------------
Part IV.

Now, using the two functions from Part III, define a new function called 
INVENTORY_COMPRESSION that takes a list of the format described in Part III
and removes all duplicates, but still retains the correct quantities.

For example:

(INVENTORY_COMPRESSION 
 '((bolts 2)(nuts 1)(nuts 3)(screws 5)(bolts 3)(nuts 4)(screws 7)(washers 2)
  (nuts 2)))

should return:

((BOLTS 5) (NUTS 10) (SCREWS 12) (WASHERS 2))

(HINT: You will need to call both REMOVE_DUPLICATES and SUM_DUPLICATES to get 
this working.  Recursively step through the input list for each two element 
list.  For each entry encountered, use SUM_DUPLICATES to find the total 
quantity of each type of item, and then use REMOVE_DUPLICATES to eliminate
that entry name from the remainder of the input list.  So for the above 
example, your INVENTORY_COMPRESSION should be constructing a list that has 
(BOLTS 5) as the first element and should call itself again with the list
((nuts 1)(nuts 3)(screws 5)(nuts 4)(screws 7)(washers 2)(nuts 2)).  Thus,
SUM_DUPLICATES and REMOVE_DUPLICATES should only be called once for each type 
of item.)

========================================================

GOOD LUCK!