Lisp/Types/List

List

The list is the fundamental type in Lisp. Conceptually, you can build all the other types, even integers, from the list.

The list is a cons cell, which is merely a pair of two things. The item on the left is called the car, and the item on the right is called cdr. Although these names seem weird, they are really the best way to think of it, since all other lisp programmers think of it this way.

(cons 1 2) -> (1 . 2)
(car (cons 1 2)) -> 1
(cdr (cons 1 2)) -> 2

(Notice the dot in the middle of (1 . 2). This means that this is not a list of two items. It is a cons cell with the left side being 1 and the right side a 2.

You can make any kind of data structure with a cons cell, including trees, multi-dimensional lists, etc... However, when you are building a one dimensional list, the way it is done is as follows.

(cons 1
      (cons 2
            (cons 3
                  (cons 4
                        (cons 5 nil)))))
=> (1  2  3  4  5)

(Remember, nil is the empty list, which can also be expressed as () or '(), depending on your mood.)

Note some interesting properties of lists built this way.

• The car of a list is the first item.
• The cdr of a list is everything but the first item.
• The end of the list is marked with nil.

Of course, building cons cells with the cons function is only one way to do it. There are other ways to build cons cells into a list.

If you want a literal list, one that can't be modified, you can use the list function.

(list 1 2 3 4 5) => (1 2 3 4 5)

But you can also use the quote function to quote the remainder of the expression.

(quote 1 2 3 4 5) => (1 2 3 4 5)

And there's a useful shorthand for quote:

'(1 2 3 4 5) => (1 2 3 4 5)

You can also use backquotes and it will mean the same thing:

`(1 2 3 4 5) => (1 2 3 4 5)

(With backquotes, you can unquote some of the items in the list, making it very useful for macros.)

To get the items from the list, you'll have to use a car's and cdr's.

(car '(1 2 3 4 5)) => 1
(car (cdr '(1 2 3 4 5))) => 2
(car (cdr (cdr '(1 2 3 4 5)))) => 3
(car (cdr (cdr (cdr '(1 2 3 4 5))))) => 4
(car (cdr (cdr (cdr (cdr '(1 2 3 4 5)))))) => 5

Because it is pretty boring to write car and cdr all the time, and keep track of the parentheses, these functions were introduced:

• cadr: The car of the cdr
• caddr: The car of the cdr of the cdr
• cadddr: The car of the cdr of the cdr of the cdr.

Note that any combination of a and d in between the c and r, up to four, are defined in common lisp. If you need more than that, you should probably be doing recursion, or using one of the more useful functions I'll introduce below.

car and cdr are nice, but there are other functions that look a little more like English.

• first is car
• rest is cdr
• second is cadr
• third is caddr
• fourth is cadddr
• fifth through tenth are also defined, meaning what you expect them to mean.
• nth is a function that takes an integer and then a list, and returns the element from the list with that index.
• elt is like nth but the order is reversed. Plus, elt works on other kinds of sequences, like vectors.

You aren't limited to storing integers or other scalar values in each item of the list. You can store lists as well.