7. car, cdr, cons: Fundamental Functions

In Lisp, car, cdr, and cons are fundamental functions. The cons function is used to construct lists, and the car and cdr functions are used to take them apart.

In the walk through of the copy-region-as-kill function, we will see cons as well as two variants on cdr, namely, setcdr and nthcdr. (See section 8.5 copy-region-as-kill.)

Strange Names

The name of the cons function is not unreasonable: it is an abbreviation of the word `construct'. The origins of the names for car and cdr, on the other hand, are esoteric: car is an acronym from the phrase `Contents of the Address part of the Register'; and cdr (pronounced `could-er') is an acronym from the phrase `Contents of the Decrement part of the Register'. These phrases refer to specific pieces of hardware on the very early computer on which the original Lisp was developed. Besides being obsolete, the phrases have been completely irrelevant for more than 25 years to anyone thinking about Lisp. Nonetheless, although a few brave scholars have begun to use more reasonable names for these functions, the old terms are still in use. In particular, since the terms are used in the Emacs Lisp source code, we will use them in this introduction.

7.1 car and cdr

The CAR of a list is, quite simply, the first item in the list. Thus the CAR of the list (rose violet daisy buttercup) is rose.

If you are reading this in Info in GNU Emacs, you can see this by evaluating the following:

(car '(rose violet daisy buttercup))

After evaluating the expression, rose will appear in the echo area.

Clearly, a more reasonable name for the car function would be first and this is often suggested.

car does not remove the first item from the list; it only reports what it is. After car has been applied to a list, the list is still the same as it was. In the jargon, car is `non-destructive'. This feature turns out to be important.

The CDR of a list is the rest of the list, that is, the cdr function returns the part of the list that follows the first item. Thus, while the CAR of the list '(rose violet daisy buttercup) is rose, the rest of the list, the value returned by the cdr function, is (violet daisy buttercup).

You can see this by evaluating the following in the usual way:

(cdr '(rose violet daisy buttercup))

When you evaluate this, (violet daisy buttercup) will appear in the echo area.

Like car, cdr does not remove any elements from the list--it just returns a report of what the second and subsequent elements are.

Incidentally, in the example, the list of flowers is quoted. If it were not, the Lisp interpreter would try to evaluate the list by calling rose as a function. In this example, we do not want to do that.

Clearly, a more reasonable name for cdr would be rest.

(There is a lesson here: when you name new functions, consider very carefully what you are doing, since you may be stuck with the names for far longer than you expect. The reason this document perpetuates these names is that the Emacs Lisp source code uses them, and if I did not use them, you would have a hard time reading the code; but do, please, try to avoid using these terms yourself. The people who come after you will be grateful to you.)

When car and cdr are applied to a list made up of symbols, such as the list (pine fir oak maple), the element of the list returned by the function car is the symbol pine without any parentheses around it. pine is the first element in the list. However, the CDR of the list is a list itself, (fir oak maple), as you can see by evaluating the following expressions in the usual way:

(car '(pine fir oak maple))

(cdr '(pine fir oak maple))

On the other hand, in a list of lists, the first element is itself a list. car returns this first element as a list. For example, the following list contains three sub-lists, a list of carnivores, a list of herbivores and a list of sea mammals:

(car '((lion tiger cheetah)
       (gazelle antelope zebra)
       (whale dolphin seal)))

In this example, the first element or CAR of the list is the list of carnivores, (lion tiger cheetah), and the rest of the list is ((gazelle antelope zebra) (whale dolphin seal)).

(cdr '((lion tiger cheetah)
       (gazelle antelope zebra)
       (whale dolphin seal)))

It is worth saying again that car and cdr are non-destructive--that is, they do not modify or change lists to which they are applied. This is very important for how they are used.

Also, in the first chapter, in the discussion about atoms, I said that in Lisp, "certain kinds of atom, such as an array, can be separated into parts; but the mechanism for doing this is different from the mechanism for splitting a list. As far as Lisp is concerned, the atoms of a list are unsplittable." (See section 1.1.1 Lisp Atoms.) The car and cdr functions are used for splitting lists and are considered fundamental to Lisp. Since they cannot split or gain access to the parts of an array, an array is considered an atom. Conversely, the other fundamental function, cons, can put together or construct a list, but not an array. (Arrays are handled by array-specific functions. See section `Arrays' in The GNU Emacs Lisp Reference Manual.)

7.2 cons

The cons function constructs lists; it is the inverse of car and cdr. For example, cons can be used to make a four element list from the three element list, (fir oak maple):

(cons 'pine '(fir oak maple))

After evaluating this list, you will see

(pine fir oak maple)

appear in the echo area. cons puts a new element at the beginning of a list; it attaches or pushes elements onto the list.

Build a list

cons must have a list to attach to.(6) You cannot start from absolutely nothing. If you are building a list, you need to provide at least an empty list at the beginning. Here is a series of cons expressions that build up a list of flowers. If you are reading this in Info in GNU Emacs, you can evaluate each of the expressions in the usual way; the value is printed in this text after `=>', which you may read as `evaluates to'.

(cons 'buttercup ())
     => (buttercup)

(cons 'daisy '(buttercup))
     => (daisy buttercup)

(cons 'violet '(daisy buttercup))
     => (violet daisy buttercup)

(cons 'rose '(violet daisy buttercup))
     => (rose violet daisy buttercup)

In the first example, the empty list is shown as () and a list made up of buttercup followed by the empty list is constructed. As you can see, the empty list is not shown in the list that was constructed. All that you see is (buttercup). The empty list is not counted as an element of a list because there is nothing in an empty list. Generally speaking, an empty list is invisible.

The second example, (cons 'daisy '(buttercup)) constructs a new, two element list by putting daisy in front of buttercup; and the third example constructs a three element list by putting violet in front of daisy and buttercup.

7.2.1 Find the Length of a List: length

You can find out how many elements there are in a list by using the Lisp function length, as in the following examples:

(length '(buttercup))
     => 1

(length '(daisy buttercup))
     => 2

(length (cons 'violet '(daisy buttercup)))
     => 3

In the third example, the cons function is used to construct a three element list which is then passed to the length function as its argument.

We can also use length to count the number of elements in an empty list:

(length ())
     => 0

As you would expect, the number of elements in an empty list is zero.

An interesting experiment is to find out what happens if you try to find the length of no list at all; that is, if you try to call length without giving it an argument, not even an empty list:

(length )

What you see, if you evaluate this, is the error message

Wrong number of arguments: #<subr length>, 0

This means that the function receives the wrong number of arguments, zero, when it expects some other number of arguments. In this case, one argument is expected, the argument being a list whose length the function is measuring. (Note that one list is one argument, even if the list has many elements inside it.)

The part of the error message that says `#<subr length>' is the name of the function. This is written with a special notation, `#<subr', that indicates that the function length is one of the primitive functions written in C rather than in Emacs Lisp. (`subr' is an abbreviation for `subroutine'.) See section `What Is a Function?' in The GNU Emacs Lisp Reference Manual, for more about subroutines.

7.3 nthcdr

The nthcdr function is associated with the cdr function. What it does is take the CDR of a list repeatedly.

If you take the CDR of the list (pine fir oak maple), you will be returned the list (fir oak maple). If you repeat this on what was returned, you will be returned the list (oak maple). (Of course, repeated CDRing on the original list will just give you the original CDR since the function does not change the list. You need to evaluate the CDR of the CDR and so on.) If you continue this, eventually you will be returned an empty list, which in this case, instead of being shown as () is shown as nil.

For review, here is a series of repeated CDRs, the text following the `=>' shows what is returned.

(cdr '(pine fir oak maple))
     =>(fir oak maple)

(cdr '(fir oak maple))
     => (oak maple)

(cdr '(oak maple))
     =>(maple)

(cdr '(maple))
     => nil

(cdr 'nil)
     => nil

(cdr ())
     => nil

You can also do several CDRs without printing the values in between, like this:

(cdr (cdr '(pine fir oak maple)))
     => (oak maple)

In this example, the Lisp interpreter evaluates the innermost list first. The innermost list is quoted, so it just passes the list as it is to the innermost cdr. This cdr passes a list made up of the second and subsequent elements of the list to the outermost cdr, which produces a list composed of the third and subsequent elements of the original list. In this example, the cdr function is repeated and returns a list that consists of the original list without its first two elements.

The nthcdr function does the same as repeating the call to cdr. In the following example, the argument 2 is passed to the function nthcdr, along with the list, and the value returned is the list without its first two items, which is exactly the same as repeating cdr twice on the list:

(nthcdr 2 '(pine fir oak maple))
     => (oak maple)

Using the original four element list, we can see what happens when various numeric arguments are passed to nthcdr, including 0, 1, and 5:

;; Leave the list as it was.
(nthcdr 0 '(pine fir oak maple))
     => (pine fir oak maple)

;; Return a copy without the first element.
(nthcdr 1 '(pine fir oak maple))
     => (fir oak maple)

;; Return a copy of the list without three elements.
(nthcdr 3 '(pine fir oak maple))
     => (maple)

;; Return a copy lacking all four elements.
(nthcdr 4 '(pine fir oak maple))
     => nil

;; Return a copy lacking all elements.
(nthcdr 5 '(pine fir oak maple))
     => nil

7.4 nth

The nthcdr function takes the CDR of a list repeatedly. The nth function takes the CAR of the result returned by nthcdr. It returns the Nth element of the list.

Thus, if it were not defined in C for speed, the definition of nth would be:

(defun nth (n list)
  "Returns the Nth element of LIST.
N counts from zero.  If LIST is not that long, nil is returned."
  (car (nthcdr n list)))

(Originally, nth was defined in Emacs Lisp in `subr.el', but its definition was redone in C in the 1980s.)

The nth function returns a single element of a list. This can be very convenient.

Note that the elements are numbered from zero, not one. That is to say, the first element of a list, its CAR is the zeroth element. This is called `zero-based' counting and often bothers people who are accustomed to the first element in a list being number one, which is `one-based'.

For example:

(nth 0 '("one" "two" "three"))
    => "one"

(nth 1 '("one" "two" "three"))
    => "two"

It is worth mentioning that nth, like nthcdr and cdr, does not change the original list--the function is non-destructive. This is in sharp contrast to the setcar and setcdr functions.

7.5 setcar

As you might guess from their names, the setcar and setcdr functions set the CAR or the CDR of a list to a new value. They actually change the original list, unlike car and cdr which leave the original list as it was. One way to find out how this works is to experiment. We will start with the setcar function.

First, we can make a list and then set the value of a variable to the list, using the setq function. Here is a list of animals:

(setq animals '(antelope giraffe lion tiger))

If you are reading this in Info inside of GNU Emacs, you can evaluate this expression in the usual fashion, by positioning the cursor after the expression and typing C-x C-e. (I'm doing this right here as I write this. This is one of the advantages of having the interpreter built into the computing environment.)

When we evaluate the variable animals, we see that it is bound to the list (antelope giraffe lion tiger):

animals
     => (antelope giraffe lion tiger)

Put another way, the variable animals points to the list (antelope giraffe lion tiger).

Next, evaluate the function setcar while passing it two arguments, the variable animals and the quoted symbol hippopotamus; this is done by writing the three element list (setcar animals 'hippopotamus) and then evaluating it in the usual fashion:

(setcar animals 'hippopotamus)

After evaluating this expression, evaluate the variable animals again. You will see that the list of animals has changed:

animals
     => (hippopotamus giraffe lion tiger)

The first element on the list, antelope is replaced by hippopotamus.

So we can see that setcar did not add a new element to the list as cons would have; it replaced giraffe with hippopotamus; it changed the list.

7.6 setcdr

The setcdr function is similar to the setcar function, except that the function replaces the second and subsequent elements of a list rather than the first element.

To see how this works, set the value of the variable to a list of domesticated animals by evaluating the following expression:

(setq domesticated-animals '(horse cow sheep goat))

If you now evaluate the list, you will be returned the list (horse cow sheep goat):

domesticated-animals
     => (horse cow sheep goat)

Next, evaluate setcdr with two arguments, the name of the variable which has a list as its value, and the list to which the CDR of the first list will be set;

(setcdr domesticated-animals '(cat dog))

If you evaluate this expression, the list (cat dog) will appear in the echo area. This is the value returned by the function. The result we are interested in is the "side effect", which we can see by evaluating the variable domesticated-animals:

domesticated-animals
     => (horse cat dog)

Indeed, the list is changed from (horse cow sheep goat) to (horse cat dog). The CDR of the list is changed from (cow sheep goat) to (cat dog).

7.7 Exercise

Construct a list of four birds by evaluating several expressions with cons. Find out what happens when you cons a list onto itself. Replace the first element of the list of four birds with a fish. Replace the rest of that list with a list of other fish.