Scheme Programming/List Operations

Cons Cells and Lists

One of more powerful features of Scheme is its ability to process 'Lists' of data.

Lists are constructed by using the cons keyword, as is shown here:

> (cons 1 '())
(1)

cons creates a 'Pair' of values, known as a cons cell.

A cons cell has two parts: The car and the cdr (pronounced "could-er"). Both parts are allowed to hold any value, but there is a certain convention that is followed when Lisp programmers want to create lists out of cons cells. The car, which stands for "Contents of Address Register", holds the first value of the list, while the cdr (stands for "Contents of Data Register") contains the next cons cell, with its own car and cdr. The car of that cons cell is the second element of the list, but also, the cdr of a list is also a list in its own right.

The names car and cdr come from the original 1958 implementation of Lisp on the IBM 704, where they were nothing but assembler macros.

A list of only one element is created by putting the empty list, also known as null, in the cdr. The empty list terminates a list.

The Scheme reader and printer automatically interpret chains of cons cells as being lists:

> (cons 1 (cons 2 (cons 3 '())))
(1 2 3)
> '(1 2 3)
(1 2 3)

Helpfully, there is a shortcut to creating a list, the list function,

> (list 1 2 3)
(1 2 3)

If the cdr of the last cons cell in a list is not the empty list, then the result is a "dotted list":

> (cons 1 (cons 2 3))
(1 2 . 3)

Most built-in list manipulation functions in Scheme are not designed to handle dotted lists, but they are commonly used in macro programming.

The car and the cdr of any cons cell can be modified at will by using set-car! and set-cdr!.

> (define x '(1 . 2))
#<unspecified>
> (set-cdr! x (cons 2 '()))
#<unspecified>
> x
(1 2)

Unlike the lists found in statically-typed programming languages like Java, Scheme lists can hold elements of different types, including other lists:

> '(1 2 (a b) "three" four)
'(1 2 (a b) "three" four)

Because of this property, lists in Scheme and Lisp are commonly used to represent HTML and XML data:

(html 
  (head
    (title "My Web Page"))
  (body (@ (style "mystyle.css"))
    "This is a commonly-used HTML/XML representation known as SXML."
    (p "This is a paragraph. It contains a "
       (a (@ (href "http://en.wikibooks.org/")) "link to another site!"))))

Many programmers consider that to be easier to read than HTML.

List manipulation

There are five primitive functions for manipulating lists and pairs in Scheme. They are cons, car, cdr, set-car! and set-cdr!

> (define test (cons 1 2))
#<unspecified>
> (car test)
1
> (cdr test)
2

As you can see from the example above, when used with a pair, car and cdr select the first and second half of the pair respectively. car And cdr can also be applied to lists.

> (define test (list 1 1 2 3 5))
#<unspecified>
> (car test)
1
> (cdr test)
(1 2 3 5)

So The result of cdr is always a list, if the parameter is a list. cdr can return the empty list, (), and this is often used to test if one has reached the end of the list. car can return an atomic data, however, what happens if we do this:

> (define test (list (list 1 1) 2 3 5))
#<unspecified>
> (car test)
?

The answer is that you get another list, (1 1). Lists can contain within them any number of other datatypes. Vectors, symbols, strings, lists, pairs, numbers, any datatype that Scheme has. And car and cdr can handle them.

There are shortcut procedures for accessing other elements in a list besides just the car and cdr. The second element of a list is accessed with cadr, the third with caddr, and so on.

Now, map is often considered to be one of the more useful (if less versatile) methods for manipulating a list. map takes a list, and a procedure, and applies the procedure to every element of the list, creating a new list with the results:

> (map (lambda (x) (* x x)) (list 1 2 3 4 5 6))
(1 4 9 16 25 36)

Since it is less versatile, it is not seen or used as often, and is overlooked. Many programmers forget the map procedure when repeatedly applying an operation to a list.

Some Scheme programmers (for example, those using the Racket dialect of Scheme) like to give more descriptive names to car and cdr.

(define first car)
(define second cadr)
(define rest cdr)