Next: , Previous: , Up: Data structures   [Contents][Index]

### 14.2 Lists

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 empty list is in X.
• If list is in X, then any pair whose cdr field contains list is also in X.

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!

Procedure: make-list k [fill]

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)
```

#### 14.2.1 SRFI-1 list library

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)
```
Procedure: reverse! list

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.

#### 14.2.2 SRFI-101 Purely Functional Random-Access Pairs and Lists

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: , Previous: , Up: Data structures   [Contents][Index]