(Click or use local copy.)

CS 3723/3721  Programming Languages  Spring 2005  Recitation 11  Lisp: Functions and mapcar     Week 11: Apr 4-8  Due (on time): 2005-04-11  23:59:59  Due (late):        2005-04-15  23:59:59

Recitation 11 must be submitted following directions at: submissions with deadlines 2005-04-11  23:59:59 (that's Monday, 11 April 2005, 11:59:59 pm) for full credit. 2005-04-15  23:59:59 (that's Friday, 15 April 2005, 11:59:59 pm) for 75% credit.

Trying out recursion in C/C++/Java:

1. In one of the three languages C, C++, Java, write a recursive version of the functions harmonic from the previous recitation. (It is always possible to replace a loop with recursion.)

For this recitation and the previous one, your Lisp functions should not have any iterative constructs (such as prog, do, etc.) but all iteration should be done with recursion. Inside functions you should not make use of the setf or setq functions.

---

2. Define a function count-atoms that will count the number of atoms in a list, at all levels. For example (count-atoms '(a (b c) (d (e) f))) should return 6. [Hint: Mimic list-atoms from class.]

   ---

3. Write a function vecmul that will take as inputs two simple lists of numbers. vecmul should multiply these lists coordinate-wise as one would multiply vectors. Assume the two lists are the same length. [For example, (vecmul '(2 3 4 5) '(1 4 5 2)) returns (2*1 3*4 4*5 5*2) or (2 12 20 10). You are not allowed to use mapcar for this function, since that is problem 10 below.]

   ---

4. Use the following addvec function (already given in the Lisp write-up under the name add)

   
   (defun addvec (list)
         (cond ((null list) 0)
         (t (+ (car list) (addvec (cdr list)))) ))
   

   along with vecmul above to define an inner product function innprod. [For example, (innprod '(1 2 3) '(7 8 9)) returns 1*7 + 2*8 + 3*9 or 50. Hint: this is very easy.]

   ---

5. Define a function last1 which returns the last element of a list (at the top level) without making use of reverse or last (already built in to Common Lisp.)

   ---

6. Write a ``super'' reverse function srev which reverses all lists that occur in an S-expression at any level. Thus (srev '((a b (c d)) e (f g))) should yield ((g f) e ((d c) b a)). [Hint: This is similar to the previous reverse1, except for additional recursion.]

   ---

7. Write a function insert1 which takes its first integer argument and inserts it at the correct place in its second argument, a list of integers sorted in increasing order, so that (insert1 3 '(1 4 6 6 7)) produces (1 3 4 6 6 7). [insert1 only works for sorted lists.]

   ---

8. Use insert1 to write a function sort1 which sorts a list of integers into increasing order. [We are done if the list is nil. Otherwise insert the car of the list into the sorted cdr.]

9. Give the result of each of the following:

   > (mapcar '1+ '(1 2 3))
   > (mapcar '+ '(1 2 3) '(8 10 12))
   > (mapcar '* '(1 2 3) '(8 10 12))
   > (mapcar 'car '((a b c) (x y z) (r s t)))
   > (mapcar 'cdr '((a b c) (x y z) (r s t)))
   > (apply '+ '(2 4 6 8))
   > (apply '* '(1 2 3 4 5))
   > (apply 'list '(a b c d))
   

10. Questions about apply and mapcar
    1. Use apply to define addvec above.

    2. Use mapcar to define vecmul above.

    3. Conclude that you can define innprod by

       
       (defun innprod (x y)
          (apply '+ (mapcar '* x y)) )
       

Contents of submission for Recitation 11: Last Name, First Name; Course Number; Recitation Number. Answers to questions 1 through 10 above.