What if you want to pack more than two values into a data structure? Does Scheme provide a different kind of data structure for each different number of values?
That turns out not to be necessary. Since pairs can have pairs as components, they are extensible -- whenever you need space for an extra component, just replace one of the components that you already have with a new pair.
In fact, there's a conventional way to do this in Scheme that is very well supported in the language: Let's say that you want to put the integers from 1 to 5 into a data structure. Construct a pair in which the first component is the first integer 1 and the second component is another pair. Construct this second pair so that its first component is the integer 2 and its second component is another pair. Construct this third pair so that it s first component is the integer 3 and its second component is another pair. Construct this fourth pair so that its first component is the integer 4 and its second component is ...
... the integer 5?
You could do that, but the conventional way is to construct yet another
pair, with 5 as its first component and an end-marker, denoted by the
literal '(), as its second component:
The fact that all the elements of the data structures are in the(cons 1 (cons 2 (cons 3 (cons 4 (cons 5 '())))))
car position of their respective pairs makes it simpler to
write procedures to work with them, without having to consider the last
element as a special case.
A structure that is built up in this way from pairs, with the end-marker as
the second component of the last pair, is called a list. More
precisely, a list is either the empty list, '(), or else a
pair in which the second component is a list.
What's the ``empty list''?
What I've been calling the end-marker is actually a list that contains zero components. It's not a pair -- it's a special value belonging to a type of its own (the null type). You use it when you want something that has the shape of a data structure but has no constituents, or alternatively when you want to mark the terminus of some succession of components in a data structure.
How does Scheme treat lists differently from other pairs in Scheme?
For one thing, they are printed differently:
The usual external representation for a list is a pair of parentheses enclosing all of the elements of the list, separated by spaces. (The Scheme 48 implementation attaches a single quotation mark at the front of a list when displaying it as the value of a top-level expression.) The external representation of an empty list is just a pair of parentheses, with nothing between them.> (cons 1 (cons 2 (cons 3 (cons 4 (cons 5 '()))))) (1 2 3 4 5)
Next topic
Previous topic
Table of contents
This document is available on the World Wide Web as
http://www.math.grin.edu/~stone/scheme-web/lists.html