CS 3723
 Programming Languages 
   2. Lisp Lists  

See Lisp Lists for background and lisp Functions for examples.

Note: You must supply Lisp source and runs (or evaluations) for each problem.

Problems Involving Functions of Lists: See examples at: Lisp Functions.

  • Problem 2.1: Try out the expressions below in sequence on the interpreter. (Think about them carefully as you go. This is for practice, so you should not turn this in.)

      
    car, cdr, cons
    > (setq x '(a b))
> (setq y '(a b c))
> (car x)
> (car y)
> (cdr x)
> (cdr y)
> (car (cdr x))
> (car (cdr y))
> (cadr x)
> (cadr y)
> (cons x y)
> (append x y)
> (cons (car y) (cdr y))

    		   
    append and list
    > (list 'a 'b 'c)
> (list 'a '(b c) 'd)
> (append '(a b) '(c d) '(e f))
> (setq l '(a b))
> (append l l)
> (append l l l)
> (list l l)
> (list l l l)
> (list 'l l)
> (append 'l l)         ;;; an error
> (append '(a) '() '(b) '())
> (append '((a) (b)) '((c)(d)))
> (list '((a)(b)) '((c)(d)))
> (cons l l)
> (cons 'l l)
> (length '(a (b c) d))
> (reverse '(a (b c) d))
> (car '(cdr '(a b c)))
> (car (cdr '(a b c)))
> (cons 'a nil)
> (setq x '(a b))
> (cons (car x) (cons (cadr x) '(c d)))

  • Problem 2.2: Write a recursive function maxvec that finds the maximum of a simple list of numbers. [Hint: if the cdr is nil, just return the car, and otherwise return the maximum of the car and of maxvec applied to the cdr. For example,
      (maxvec '(2 5 6 3))
    returns 6.]

  • Problem 2.3: 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 length1 and list-atoms from lisp_functions.]

  • Problem 2.4: 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 12 20 10), which is (2*1 3*4 4*5 5*2). This problem may be a little tricky. You may want to use both append and list. You are not allowed to use mapcar for this function, since that is problem 2.11 below.]

  • Problem 2.5: Use the following addvec function (already given in lisp_functions under the name add)

    addvec in Lisp
    (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 50 by calculating 1*7 + 2*8 + 3*9 or 50. Hint: this is very easy.]

  • Problem 2.6: 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.]

  • Problem 2.7: 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.]

  • Problem 2.8: Try out the function reverse in Lisp:

    reverse in Lisp
    > (reverse '(a b c)) 
> (reverse '((a b c))) 
> (reverse '(a (b c d) e))

    Define your own function reverse1 which will behave the same way as reverse, reversing the order of elements of a list at the top level only. [Hint: Invoke reverse1 recursively on the cdr and tack on the car at the end. Finally, extra superhint.]

  • Problem 2.9: 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.]

Problems Involving mapcar and apply: See: Reference.

Problem 10.

  • Problem 2.10: Give the result of each of the following:

    mapcar and apply
    > (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))

  • Problem 2.11: [Very short code for each of the three below.]

    1. Use apply to define addvec above.

    2. Use mapcar to define vecmul above.

    3. Give code for the function innprod (see 10.6 above) that uses only apply and mapcar

Problems Involving Internal Representations and dotted pairs: See Reference.
  • Problem 2.12:

    1. Give the internal lisp representation for the S-expression: ( (a b) c (d) ). [This should involve lisp cells that each have a car and a cdr pointer. You will need to draw some kind of diagram, perhaps similar to the diagrams in the link above.]

    2. What does the dotted expression ( (a . (b . nil) ) . (c . ( (d . nil) . nil) ) ) represent as a normal S-expression (without dots). [There is a trivial way to solve this.]

( Revision date: 2014-03-26. Please use ISO 8601, the International Standard Date and Time Notation.)