My other car is a cdr
In Scheme, car
, cdr
, and cons
are the most important functions. The cons
function is used to construct pairs and pairs are used to construct the lists. The car
and cdr
are used to access data and return accordingly first and second element from a pair.
The name of the cons
function is an abbreviation of the word construct
. The origins of the names for car
and cdr
are a little bit historical and comes from the IBM 704. car
is an acronym from the phrase Contents of the Address part of the Register; and cdr
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 Lisp language was developed. Nowadays the more appropriate names for these functions would be firs
and rest
.
Cons
The cons
function accepts any two values, not just a list for the second argument. The two values joined with cons
are printed between parentheses, with a dot, because Lisp interpreters uses a .
to visually separate the elements in the pair. For example:
> (cons 1 2)
(1 . 2)
Lists are built on top of pairs. For example, the list '(a b c)
is constructed by evaluating the following expression:
> (cons 'a (cons 'b (cons 'c '())))
(a b c)
The list
procedure provides a shortcut for creating lists:
> (list 'a 'b c)
(a b c)
The same can be achieved by '(a b c)
.
Appending value to the list can be done in the following way:
> (cons 1 '(2 3 4))
(1 2 3 4)
We can play more with the cons
function. Notice that the expression (cons '(a b c) ())
creates a pair whose first element is a list. So it evaluates to:
((a b c))
The ()
stands for null, so the result is a pair (value, null)
. Notice the double braces in the returned expression. Let’s consider more examples:
> (cons '(a b c) '(d))
((a b c) d)
Above result is a list with two elements — a list as the first and d
as the second. It is equivalent to [[a, b, c], d]
.
Whether a given pair is a list depends on what is stored in the cdr
field. A proper list is defined in the recursive way as and empty list ()
or a pair which second element is a proper list. A chain of pairs that doesn’t end in the empty list is called an improper list.
Car
As mentioned earlier the car
of a pair is its first item. And in case of lists it’s the head of the list. Thus the car
of the list (a b c d)
is a
and the car
of the pair (a . b)
is also a
.
car
is non-destructive which means it doesn’t mutate the pair by removing the first item from it, it only echoes what it is. After car
has been applied to a list, the list is still the same as it was.
Cdr
The cdr
function returns the second element of the pair which in case of lists is the list’s tail. So applying the cdr
function to the examples above we will get:
> (cdr '(a b c d))
(b c d)> (cdr '(a . b))
b
Like car
, cdr
does not remove any elements form the list.
Setters
The functions set-car!
and set-cdr!
are used to set accordingly the first and the second element of the pair. And contrarily to the car
and cdr
they actually mutate the pair. Applying them to the lists we will get following results:
> (define x '(a b c d))
First we defined new list x and notation above stands for x = [a, b, c, d]
.
> (set-car! x 'z)
> x
(z b c d)> (set-cdr! x '(y x))
> x
(z y x)
If we set car
of the list as any possible value it remains a list but if we will try to set cdr
of the list as a non-list value we’ll got a pair in return.
> (set-cdr! x 'a)
(z . a)