Scheme Programming/List Operations
Cons Cells and Lists
One of more powerful features of Scheme is it's 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 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.
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 1 2 3) (1 2 3)
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.
car and the
cdr of any cons cell can be modified at will by using
> (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.
There are five primitive functions for manipulating lists and pairs in Scheme. They are
> (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.
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)