CS 3723
 Programming Languages 
   Lisp Workpage 3  
  Lists in Lisp  

Lists in Lisp: Using car, cdr, and cons.

Note that you must supply runs (or evaluations) using clisp of any of your lisp materials submitted.

Note: Addition examples of Lisp functions that make use of car, cdr, cons, list, and append are given at: Lisp Functions.

  • Stopping evaluation: Sometimes we don't want to evaluate a list or an atom. quote is another Lisp special function that doesn't evaluate its argument, but instead returns it unevaluated. A single quote mark, without the parens, gives a shorthand version of the longer form.

    Quote or ', Preventing Evaluation
    > (quote (a b c))
(A B C)
> '(a b c)
(A B C)
> (a b c)
Error: The function A is undefined.

  • car and cdr tear lists apart: car returns the first element of a list, and cdr returns the remainder of the list with the first element deleted.

    car and cdr: Tearing Lists Apart
    > (car '(a b c))      ;;; first element is a
A
> (cdr '(a b c))      ;;; rest of list is (b c)
(B C)
> (car (cdr '(a b)))  ;;; cdr gives (b), and car of that is b
B
> (car (a b c))       ;;; lisp tries to evaluate (a b c)
Error: The function A is undefined.

  • cons puts two lists together: cons assembles a list from its car and cdr.

    Cons: Assembling Lists
    > (cons 'a '(b c))
(A B C)
> (cons (car '(a b c)) (cdr '(a b c)))
(A B C)

  • list and append give two more ways to create new lists:

    List: Creating Lists
    ; list takes any seq of S-expressions
; and makes a list out of them:
> (list 'a 'b 'c)
(A B C)
> (list '(a) '(b c) 'd)
((A) (B C) D)
> (list '(a (b c) d) '((e) f ((g))))
((A (B C) D) ((E) F ((G))))
> (list 'a '(b c) nil 'd () )
(A (B C) NIL D NIL)
; Note: list keeps empty lists
    		  
    Append: Tack Lists Together
    ; append takes any sequence of lists and
; combines them into a single list:
> (append '(a b) '(c d))
(A B C D)
> (append '(a (b c) d) '((e) f ((g))))
(A (B C) D (E) F ((G)))
> (append '(a b) nil '(c) () )
(A B C)    ; append drops empty lists
> (append 'a '(b c))
*** - APPEND: A is not a list
> (append '(a b) 'c)    
(A B . C) ; more on this notation later

  • Evaluating lists -- Another Look Look back at what was said under an earlier header, "Evaluating lists." Let's see how Lisp can evaluate using actual functions apply and eval:

    Eval and Apply
    > (+ 3 4 5)
12
> (eval (+ 3 4 5))
12
> (apply '+ '(3 4 5))
12
> (apply (car '(+ 2 3 4)) (cdr '(+ 3 4 5)))
12

List Library Functions: Common Lisp has a large number of library functions. Here are a few of them:

  • List Functions:

    List Functions
    first (same as car)  second  third  fourth  ... 
 last  rest (same as cdr)
    
caar  cadr  cdar  cddr  ...  append  list

  • Other Predicates: (Boolean-valued functions, they return t or nil)

    Predicates
    member  atom  listp  null  eq  eql  equal  numberp

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

  • Problem 10.1: Try out the expressions below in sequence on the interpreter. (Think about them carefully as you go.)

      
    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 10.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 10.3: 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. (Note: There is now a further hint on the Questions page about how to do the above.) Note: Don't try to give a new definition to standard Lisp functions; this is why I tacked a "1" on at the end of this new reverse.]

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

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

  • Problem 10.6: 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 1*7 + 2*8 + 3*9 or 50. Hint: this is very easy.]

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

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

Problems Involving mapcar and apply: See: Reference.

  • Problem 10.9: 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 10.10:

    1. Use apply to define addvec above.

    2. Use mapcar to define vecmul above.

    3. (Note: Problem slightly misstated earlier.) Give code for the function innprod (see 10.6 above) that uses only addvec and vecmul. Alternatively, give code for innprod that uses only apply and mapcar [Very short code here.]
Problems Involving Internal Representations and dotted pairs: See Reference.
  • Problem 10.11:

    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: 2013-11-03. (Please use ISO 8601, the International Standard Date and Time Notation.)