CS 3723/3721 Programming Languages
Lisp Recitation 2: More Functions and Mapcar

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.)
More Lisp Functions:

    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.
  1. 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).]
  2. Use addvec and vecmul 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.]
  3. 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.)
  4. 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.]
  5. 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.]
  6. Use insert 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.]
Use of mapcar and apply:

    Lisp has special types of functions that transform and expand the meaning of other functions. The most common of these is mapcar. Consider where f is a function and list1, list2, ..., listn are lists. The result of this is to make up a new list that looks like: Thus Similarly, (apply 'f '(s1 s2 ... sn)) becomes (f 's1 's2 ... 'sn) so that one has:
  1. Give the result of each of the following:
  2. Use mapcar to define addvec above.

  3. Use mapcar to define vecmul above.

  4. Conclude that you can define innprod by
  5. Explain how each of the following functions work:

  6. Check out the following transpose function for matrices. This code shows some of the real power of Lisp and of functional programming. A transpose function in a traditional language is much more complicated. The following code shows in more detail how this works: .txt, .pdf, .ps.
    In the code above, first a more traditional approach to transpose in Lisp is shown, and the parts of the traditional approach is step-by-step replaced by the use of mapcar.

Revision date: 2003-04-07. (Please use ISO 8601, the International Standard Date and Time Notation.)