Next: Vectors, Previous: Sequences, Up: Data structures [Contents][Index]
A pair (sometimes called a dotted pair) is a record structure
with two fields called the car and cdr fields (for historical
reasons). Pairs are created by the procedure cons
. The
car and cdr fields are accessed by the procedures car
and
cdr
. The car and cdr fields are assigned by the procedures
set-car!
and set-cdr!
.
Pairs are used primarily to represent lists. A list can be defined recursively as either the empty list or a pair whose cdr is a list. More precisely, the set of lists is defined as the smallest set X such that:
The objects in the car fields of successive pairs of a list are the elements of the list. For example, a two-element list is a pair whose car is the first element and whose cdr is a pair whose car is the second element and whose cdr is the empty list. The length of a list is the number of elements, which is the same as the number of pairs.
The empty list is a special object of its own type. It is not a pair, it has no elements, and its length is zero.
Note: The above definitions imply that all lists have finite length and are terminated by the empty list.
The most general notation (external representation) for
Scheme pairs is the “dotted” notation (c1 . c2 )
where c1 is the value of the car field and
c2 is the value of the cdr field.
For example (4 . 5)
is a pair whose car is 4 and
whose cdr is 5. Note that (4 . 5)
is the external representation
of a pair, not an expression that evaluates to a pair.
A more streamlined notation can be used for lists: the
elements of the list are simply enclosed in parentheses and
separated by spaces. The empty list is written ()
.
For example,
(a b c d e)
and
(a . (b . (c . (d . (e . ())))))
are equivalent notations for a list of symbols.
A chain of pairs not ending in the empty list is called an improper list. Note that an improper list is not a list. The list and dotted notations can be combined to represent improper lists:
(a b c . d)
is equivalent to
(a . (b . (c . d)))
Needs to finish merging from R7RS!
Returns a newly allocated list of k elements. If a second argument is given, the each element is initialized to fill. Otherwise the initial contents of each element is unspecified.
(make-list 2 3) ⇒ (3 3)
The SRFI-1 List Library
is available, though not enabled by default. To use its functions you
must (require 'list-lib)
or (require 'srfi-1)
.
(require 'list-lib) (iota 5 0 -0.5) ⇒ (0.0 -0.5 -1.0 -1.5 -2.0)
The result is a list consisting of the elements of list in reverse order.
No new pairs are allocated, instead the pairs of list are re-used,
with cdr
cells of list reversed in place. Note that if list
was pair, it becomes the last pair of the reversed result.
SRFI-101
specifies immutable (read-only) lists with fast (logarithmic) indexing
and functional
update (i.e. return a modified list).
These are implemented by a RAPair
class
which extends the generic pair
type, which means that most
code that expects a standard list will work on these lists as well.
Next: Vectors, Previous: Sequences, Up: Data structures [Contents][Index]