Music 220b: Winter 2001
Fernando Lopez-Lezcano, instructor
Christopher Burns, teaching assistant
Tamara Smyth, teaching assistant

Week 2: lists - the fundamental Lisp data type

Lists are the canonical data structure of the Lisp programming language. Lisp programs are themselves expressed as lists; there is no fundamental difference in structure between a piece of "data" like '(1 2 3 4) and a "program" (or function) like (defun square (x) (* x x)). Hence the lisp truism that "there is no distinction between program and data," and the possibility of writing programs which themselves write programs....

• Creating a list:

  The standard way of creating a list is with the (list) command:

  (list 1 2 3 4)

  A shortcut which does almost the same thing is the (quote) command:

  (quote (1 2 3 4)) ; long form
  '(1 2 3 4)        ; short form
  

  This shorthand is ubiquitous -- for instance, you've used it to specify envelopes: '(0 0 0.5 1 1 0) is the classic triangular rise-and-fall envelope.

  There is a crucial difference between (list) and (quote). (List) evaluates its arguments, whereas (quote) assumes the arguments to be symbols, and doesn't evaluate them. By way of example:

  CM(11): (setf test-variable 77)
  77
  CM(12): (list 1 2 (+ 3 4) test-variable)
  (1 2 7 77)
  CM(13): '(1 2 (+ 3 4) test-variable)
  (1 2 (+ 3 4) TEST-VARIABLE)

  So, if we want to construct lists on the fly from variables, we're better off using (list) than (quote).

  Sometimes it's convenient to nest lists: (list (list 1 2) (list 3 4) (list 5 6)) returns a list of three elements, each of which is a list of two elements.

  Note that all standard lists (such as those created with (list) or (quote)) end with "nil," which signifies the "empty list." We'll see more about nil in the next section.

• Accessing the elements of a list:

  Once we've constructed a list, we'd probably like to use it. The standard ways of accessing a list are the (car), (cdr), and (nth) functions. (Car list) returns the first element of a list, while (cdr list) returns the entire list except for the first element. You can combine cars and cdrs in a single function: (cadr list) returns the car of the cdr of the list, for instance.

  (Nth) enables us to access any one element of a list, counting from zero. (Nth 0 list) is the same as (car list), while (nth 1 list) returns the second element only -- quite unlike (cdr list). While traditional lisp programming focuses on car and cdr, nth enables us to treat lists a little bit more like arrays.

  Some examples:

  CM(14): (setf test-list (list (list 1 2 3) (list 4 5) (list 7 8 9) 0))
  ((1 2 3) (4 5) (7 8 9) 0)
  CM(15): (car test-list)
  (1 2 3)
  CM(16): (car (car test-list))
  1
  CM(17): (cdr test-list)
  ((4 5) (7 8 9) 0)
  CM(18): (cadr test-list)
  (4 5)
  CM(19): (nth 2 test-list)
  (7 8 9)
  CM(20): (nth 2 (nth 2 test-list))
  9
  CM(21): (cdr (cdr test-list))
  ((7 8 9) 0)
  CM(22): (nth 1 (cdr (cdr test-list)))
  0
  CM(23): (nth 1 (car (cdr (cdr test-list))))
  8

• Modifying a list:

  The (append) command combines two lists into a single structure:

  CM(24): (append (list 1 2 3) (list 4 5 6))
  (1 2 3 4 5 6)

  The (setf) command is also extremely useful for modifying lists:

  CM(25): (setf x (list 1 2 3))
  (1 2 3)
  CM(26): (setf (car x) 4)
  4
  CM(27): x
  (4 2 3)

Guy Steele's online Lisp manual has a chapter on lists with more information.

Course resources main page
220b main page