# Lists

A pair (sometimes called a dotted pair) is a data 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.(8)

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, the following are equivalent notations for a list of symbols:

```(a b c d e)
(a . (b . (c . (d . (e . ())))))
```

Whether a given pair is a list depends upon what is stored in the cdr field. When the `set-cdr!` procedure is used, an object can be a list one moment and not the next:

```(define x (list 'a 'b 'c))
(define y x)
y                                       =>  (a b c)
(list? y)                               =>  #t
(set-cdr! x 4)                          =>  unspecified
x                                       =>  (a . 4)
(eqv? x y)                              =>  #t
y                                       =>  (a . 4)
(list? y)                               =>  #f
(set-cdr! x x)                          =>  unspecified
(list? y)                               =>  #f
```

A chain of pairs that doesn't end 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, as the following equivalent notations show:

```(a b c . d)
(a . (b . (c . d)))
```

Within literal expressions and representations of objects read by the `read` procedure, the forms `'datum`, ``datum`, `,datum`, and `,@datum` denote two-element lists whose first elements are the symbols `quote`, `quasiquote`, `unquote`, and `unquote-splicing`, respectively. The second element in each case is datum. This convention is supported so that arbitrary Scheme programs may be represented as lists. Among other things, this permits the use of the `read` procedure to parse Scheme programs.

## Pairs

This section describes the simple operations that are available for constructing and manipulating arbitrary graphs constructed from pairs.

procedure: pair? object
Returns `#t` if object is a pair; otherwise returns `#f`.

```(pair? '(a . b))                        =>  #t
(pair? '(a b c))                        =>  #t
(pair? '())                             =>  #f
(pair? '#(a b))                         =>  #f
```

procedure: cons obj1 obj2
Returns a newly allocated pair whose car is obj1 and whose cdr is obj2. The pair is guaranteed to be different (in the sense of `eqv?`) from every previously existing object.

```(cons 'a '())                           =>  (a)
(cons '(a) '(b c d))                    =>  ((a) b c d)
(cons "a" '(b c))                       =>  ("a" b c)
(cons 'a 3)                             =>  (a . 3)
(cons '(a b) 'c)                        =>  ((a b) . c)
```

procedure: car pair
Returns the contents of the car field of pair. Note that it is an error to take the `car` of the empty list.

```(car '(a b c))                          =>  a
(car '((a) b c d))                      =>  (a)
(car '(1 . 2))                          =>  1
(car '())                               error--> Illegal datum
```

procedure: cdr pair
Returns the contents of the cdr field of pair. Note that it is an error to take the `cdr` of the empty list.

```(cdr '((a) b c d))                      =>  (b c d)
(cdr '(1 . 2))                          =>  2
(cdr '())                               error--> Illegal datum
```

procedure: set-car! pair object
Stores object in the car field of pair. The value returned by `set-car!` is unspecified.

```(define (f) (list 'not-a-constant-list))
(define (g) '(constant-list))
(set-car! (f) 3)                        =>  unspecified
(set-car! (g) 3)                        error--> Illegal datum
```

procedure: set-cdr! pair object
Stores object in the cdr field of pair. The value returned by `set-cdr!` is unspecified.

procedure: caar pair
procedure: cdar pair
procedure: cddr pair
procedure: caaar pair
procedure: cdaar pair
procedure: cddar pair
procedure: cdddr pair
procedure: caaaar pair
procedure: cdaaar pair
procedure: cddaar pair
procedure: cdddar pair
procedure: cddddr pair
These procedures are compositions of `car` and `cdr`; for example, `caddr` could be defined by

```(define caddr (lambda (x) (car (cdr (cdr x)))))
```

procedure+: general-car-cdr object path
This procedure is a generalization of `car` and `cdr`. Path encodes a particular sequence of `car` and `cdr` operations, which `general-car-cdr` executes on object. Path is an exact non-negative integer that encodes the operations in a bitwise fashion: a zero bit represents a `cdr` operation, and a one bit represents a `car`. The bits are executed LSB to MSB, and the most significant one bit, rather than being interpreted as an operation, signals the end of the sequence.(9)

For example, the following are equivalent:

```(general-car-cdr object #b1011)
(cdr (car (car object)))
```

Here is a partial table of path/operation equivalents:

```#b10    cdr
#b11    car
#b100   cddr
#b101   cdar
#b111   caar
#b1000  cdddr
```

procedure+: tree-copy tree
This copies an arbitrary tree constructed from pairs, copying both the car and cdr elements of every pair. This could have been defined by

```(define (tree-copy tree)
(let loop ((tree tree))
(if (pair? tree)
(cons (loop (car tree)) (loop (cdr tree)))
tree)))
```

## Construction of Lists

procedure: list object ...
Returns a list of its arguments.

```(list 'a (+ 3 4) 'c)                    =>  (a 7 c)
(list)                                  =>  ()
```

These expressions are equivalent:

```(list obj1 obj2 ... objN)
(cons obj1 (cons obj2 ... (cons objN '()) ...))
```

procedure+: make-list k [element]
This procedure returns a newly allocated list of length k, whose elements are all element. If element is not supplied, it defaults to the empty list.

procedure+: cons* object object ...
`cons*` is similar to `list`, except that `cons*` conses together the last two arguments rather than consing the last argument with the empty list. If the last argument is not a list the result is an improper list. If the last argument is a list, the result is a list consisting of the initial arguments and all of the items in the final argument. If there is only one argument, the result is the argument.

```(cons* 'a 'b 'c)                        =>  (a b . c)
(cons* 'a 'b '(c d))                    =>  (a b c d)
(cons* 'a)                              =>  a
```

These expressions are equivalent:

```(cons* obj1 obj2 ... objN-1 objN)
(cons obj1 (cons obj2 ... (cons objN-1 objN) ...))
```

procedure+: list-copy list
Returns a newly allocated copy of list. This copies each of the pairs comprising list. This could have been defined by

```(define (list-copy list)
(if (null? list)
'()
(cons (car list)
(list-copy (cdr list)))))
```

procedure: vector->list vector
procedure+: subvector->list vector start end
`vector->list` returns a newly allocated list of the elements of vector. `subvector->list` returns a newly allocated list of the elements of the given subvector. The inverse of `vector->list` is `list->vector`.

```(vector->list '#(dah dah didah))        =>  (dah dah didah)
```

procedure: string->list string
procedure: substring->list string start end
`string->list` returns a newly allocated list of the character elements of string.
`substring->list` returns a newly allocated list of the character elements of the given substring. The inverse of `string->list` is `list->string`.

```(string->list "abcd")                   =>  (#\a #\b #\c #\d)
(substring->list "abcdef" 1 3)          =>  (#\b #\c)
```

## Selecting List Components

procedure+: list? object
Returns `#t` if object is a list, otherwise returns `#f`. By definition, all lists have finite length and are terminated by the empty list. This procedure returns an answer even for circular structures.

Any object satisfying this predicate will also satisfy exactly one of `pair?` or `null?`.

```(list? '(a b c))                        =>  #t
(list? '())                             =>  #t
(list? '(a . b))                        =>  #f
(let ((x (list 'a)))
(set-cdr! x x)
(list? x))                            =>  #f
```

procedure: length list
Returns the length of list.

```(length '(a b c))                       =>  3
(length '(a (b) (c d e)))               =>  3
(length '())                            =>  0
```

procedure: null? object
Returns `#t` if object is the empty list; otherwise returns `#f` (but see section True and False).

```(null? '(a . b))                        =>  #f
(null? '(a b c))                        =>  #f
(null? '())                             =>  #t
```

procedure: list-ref list k
Returns the kth element of list, using zero-origin indexing. The valid indexes of a list are the exact non-negative integers less than the length of the list. The first element of a list has index `0`, the second has index `1`, and so on.

```(list-ref '(a b c d) 2)                 =>  c
(list-ref '(a b c d)
(inexact->exact (round 1.8)))
=>  c
```

`(list-ref list k)` is equivalent to ```(car (list-tail list k))```.

procedure+: first list
procedure+: second list
procedure+: third list
procedure+: fourth list
procedure+: fifth list
procedure+: sixth list
procedure+: seventh list
procedure+: eighth list
procedure+: ninth list
procedure+: tenth list
Returns the specified element of list. It is an error if list is not long enough to contain the specified element (for example, if the argument to `seventh` is a list that contains only six elements).

## Cutting and Pasting Lists

procedure+: sublist list start end
Start and end must be exact integers satisfying

```0 <= start <= end <= (length list)
```

`sublist` returns a newly allocated list formed from the elements of list beginning at index start (inclusive) and ending at end (exclusive).

Returns a newly allocated list consisting of the first k elements of list. K must not be greater than the length of list.

We could have defined `list-head` this way:

```(define (list-head list k)
(sublist list 0 k))
```

procedure: list-tail list k
Returns the sublist of list obtained by omitting the first k elements. The result, if it is not the empty list, shares structure with list. K must not be greater than the length of list.

procedure: append list ...
Returns a list consisting of the elements of the first list followed by the elements of the other lists.

```(append '(x) '(y))                      =>  (x y)
(append '(a) '(b c d))                  =>  (a b c d)
(append '(a (b)) '((c)))                =>  (a (b) (c))
(append)                                =>  ()
```

The resulting list is always newly allocated, except that it shares structure with the last list argument. The last argument may actually be any object; an improper list results if the last argument is not a proper list.

```(append '(a b) '(c . d))                =>  (a b c . d)
(append '() 'a)                         =>  a
```

procedure+: append! list ...
Returns a list that is the argument lists concatenated together. The arguments are changed rather than copied. (Compare this with `append`, which copies arguments rather than destroying them.) For example:

```(define x '(a b c))
(define y '(d e f))
(define z '(g h))
(append! x y z)                         =>  (a b c d e f g h)
x                                       =>  (a b c d e f g h)
y                                       =>  (d e f g h)
z                                       =>  (g h)
```

## Filtering Lists

procedure+: list-transform-positive list predicate
procedure+: list-transform-negative list predicate
These procedures return a newly allocated copy of list containing only the elements for which predicate is (respectively) true or false. Predicate must be a procedure of one argument.

```(list-transform-positive '(1 2 3 4 5) odd?) => (1 3 5)
(list-transform-negative '(1 2 3 4 5) odd?) => (2 4)
```

procedure+: delq element list
procedure+: delv element list
procedure+: delete element list
Returns a newly allocated copy of list with all entries equal to element removed. `delq` uses `eq?` to compare element with the entries in list, `delv` uses `eqv?`, and `delete` uses `equal?`.

procedure+: delq! element list
procedure+: delv! element list
procedure+: delete! element list
Returns a list consisting of the top-level elements of list with all entries equal to element removed. These procedures are like `delq`, `delv`, and `delete` except that they destructively modify list. `delq!` uses `eq?` to compare element with the entries in list, `delv!` uses `eqv?`, and `delete!` uses `equal?`. Because the result may not be `eq?` to list, it is desirable to do something like `(set! x (delete! x))`.

```(define x '(a b c b))
(delete 'b x)                           =>  (a c)
x                                       =>  (a b c b)

(define x '(a b c b))
(delete! 'b x)                          =>  (a c)
x                                       =>  (a c)
;; Returns correct result:
(delete! 'a x)                          =>  (c)

;; Didn't modify what x points to:
x                                       =>  (a c)
```

procedure+: delete-member-procedure deletor predicate
Returns a deletion procedure similar to `delv` or `delete!`. Deletor should be one of the procedures `list-deletor` or `list-deletor!`. Predicate must be an equivalence predicate. The returned procedure accepts exactly two arguments: first, an object to be deleted, and second, a list of objects from which it is to be deleted. If deletor is `list-deletor`, the procedure returns a newly allocated copy of the given list in which all entries equal to the given object have been removed. If deletor is `list-deletor!`, the procedure returns a list consisting of the top-level elements of the given list with all entries equal to the given object removed; the given list is destructively modified to produce the result. In either case predicate is used to compare the given object to the elements of the given list.

Here are some examples that demonstrate how `delete-member-procedure` could have been used to implement `delv` and `delete!`:

```(define delv (delete-member-procedure list-deletor eqv?))
(define delete! (delete-member-procedure list-deletor! equal?))
```

procedure+: list-deletor predicate
procedure+: list-deletor! predicate
These procedures each return a procedure that deletes elements from lists. Predicate must be a procedure of one argument. The returned procedure accepts exactly one argument, which must be a proper list, and applies predicate to each of the elements of the argument, deleting those for which it is true.

The procedure returned by `list-deletor` deletes elements non-destructively, by returning a newly allocated copy of the argument with the appropriate elements removed. The procedure returned by `list-deletor!` performs a destructive deletion.

## Searching Lists

procedure+: list-search-positive list predicate
procedure+: list-search-negative list predicate
Returns the first element in list for which predicate is (respectively) true or false; returns `#f` if it doesn't find such an element. (This means that if predicate is true (false) for `#f`, it may be impossible to distinguish a successful result from an unsuccessful one.) Predicate must be a procedure of one argument.

procedure: memq object list
procedure: memv object list
procedure: member object list
These procedures return the first pair of list whose car is object; the returned pair is always one from which list is composed. If object does not occur in list, `#f` (n.b.: not the empty list) is returned. `memq` uses `eq?` to compare object with the elements of list, while `memv` uses `eqv?` and `member` uses `equal?`.(10)

```(memq 'a '(a b c))                      =>  (a b c)
(memq 'b '(a b c))                      =>  (b c)
(memq 'a '(b c d))                      =>  #f
(memq (list 'a) '(b (a) c))             =>  #f
(member (list 'a) '(b (a) c))           =>  ((a) c)
(memq 101 '(100 101 102))               =>  unspecified
(memv 101 '(100 101 102))               =>  (101 102)
```

procedure+: member-procedure predicate
Returns a procedure similar to `memq`, except that predicate, which must be an equivalence predicate, is used instead of `eq?`. This could be used to define `memv` as follows:

```(define memv (member-procedure eqv?))
```

## Mapping of Lists

procedure: map procedure list list ...
Procedure must be a procedure taking as many arguments as there are lists. If more than one list is given, then they must all be the same length. `map` applies procedure element-wise to the elements of the lists and returns a list of the results, in order from left to right. The dynamic order in which procedure is applied to the elements of the lists is unspecified; use `for-each` to sequence side effects.

```(map cadr '((a b) (d e) (g h)))           =>  (b e h)
(map (lambda (n) (expt n n)) '(1 2 3 4))  =>  (1 4 27 256)
(map + '(1 2 3) '(4 5 6))                 =>  (5 7 9)
(let ((count 0))
(map (lambda (ignored)
(set! count (+ count 1))
count)
'(a b c)))                         =>  unspecified
```

procedure+: map* initial-value procedure list1 list2 ...
Similar to `map`, except that the resulting list is terminated by initial-value rather than the empty list. The following are equivalent:

```(map procedure list list ...)
(map* '() procedure list list ...)
```

procedure+: append-map procedure list list ...
procedure+: append-map* initial-value procedure list list ...
Similar to `map` and `map*`, respectively, except that the results of applying procedure to the elements of lists are concatenated together by `append` rather than by `cons`. The following are equivalent, except that the former is more efficient:

```(append-map procedure list list ...)
(apply append (map procedure list list ...))
```

procedure+: append-map! procedure list list ...
procedure+: append-map*! initial-value procedure list list ...
Similar to `map` and `map*`, respectively, except that the results of applying procedure to the elements of lists are concatenated together by `append!` rather than by `cons`. The following are equivalent, except that the former is more efficient:

```(append-map! procedure list list ...)
(apply append! (map procedure list list ...))
```

procedure: for-each procedure list list ...
The arguments to `for-each` are like the arguments to `map`, but `for-each` calls procedure for its side effects rather than for its values. Unlike `map`, `for-each` is guaranteed to call procedure on the elements of the lists in order from the first element to the last, and the value returned by `for-each` is unspecified.

```(let ((v (make-vector 5)))
(for-each (lambda (i)
(vector-set! v i (* i i)))
'(0 1 2 3 4))
v)                            =>  #(0 1 4 9 16)
```

## Reduction of Lists

procedure+: reduce procedure initial list
Combines all the elements of list using the binary operation procedure. For example, using `+` one can add up all the elements:

```(reduce + 0 list-of-numbers)
```

The argument initial is used only if list is empty; in this case initial is the result of the call to `reduce`. If list has a single argument, it is returned. Otherwise, the arguments are reduced in a left-associative fashion. For example:

```(reduce + 0 '(1 2 3 4))                 =>  10
(reduce + 0 '(1 2))                     =>  3
(reduce + 0 '(1))                       =>  1
(reduce + 0 '())                        =>  0
(reduce + 0 '(foo))                     =>  foo
(reduce list '() '(1 2 3 4))            =>  (((1 2) 3) 4)
```

procedure+: reduce-right procedure initial list
Like `reduce` except that it is right-associative.

```(reduce-right list '() '(1 2 3 4))      =>  (1 (2 (3 4)))
```

procedure+: fold-right procedure initial list
Combines all of the elements of list using the binary operation procedure. Unlike `reduce` and `reduce-right`, initial is always used:

```(fold-right + 0 '(1 2 3 4))             =>  10
(fold-right + 0 '(foo))                 error--> Illegal datum
(fold-right list '() '(1 2 3 4))        =>  (1 (2 (3 (4 ()))))
```

`Fold-right` has interesting properties because it establishes a homomorphism between (`cons`, `()`) and (procedure, initial). It can be thought of as replacing the pairs in the spine of the list with procedure and replacing the `()` at the end with initial. Many of the classical list processing procedures can be expressed in terms of `fold-right`, at least for the simple versions that take a fixed number of arguments:

```(define (copy-list list)
(fold-right cons '() list))

(define (append list1 list2)
(fold-right cons list2 list1))

(define (map p list)
(fold-right (lambda (x r) (cons (p x) r)) '() list))

(define (reverse items)
(fold-right (lambda (x r) (append r (list x))) '() items))
```

procedure+: fold-left procedure initial list
Combines all the elements of list using the binary operation procedure. Elements are combined starting with initial and then the elements of list from left to right. Whereas `fold-right` is recursive in nature, capturing the essence of `cdr`-ing down a list and then computing a result, fold-left is iterative in nature, combining the elements as the list is traversed.

```(fold-left list '() '(1 2 3 4))         =>  ((((() 1) 2) 3) 4)

(define (length list)
(fold-left (lambda (sum element) (+ sum 1)) 0 list))

(define (reverse items)
(fold-left (lambda (x y) (cons y x)) () items))
```

procedure+: there-exists? list predicate
Predicate must be a procedure of one argument. Applies predicate to each element of list, in order from left to right. If predicate is true for any element of list, the value yielded by predicate is immediately returned as the value of `there-exists?`; predicate will not be applied to the remaining elements of list. If predicate returns `#f` for all of the elements of list, then `#f` is returned.

procedure+: for-all? list predicate
Predicate must be a procedure of one argument. Applies predicate to each element of list, in order from left to right. If predicate returns `#f` for any element of list, `#f` is immediately returned as the value of `for-all?`; predicate will not be applied to the remaining elements of list. If predicate is true for all of the elements of list, then `#t` is returned.

## Miscellaneous List Operations

procedure+: circular-list object ...
procedure+: make-circular-list k [element]
These procedures are like `list` and `make-list`, respectively, except that the returned lists are circular. `circular-list` could have been defined like this:

```(define (circular-list . objects)
(append! objects objects))
```

procedure: reverse list
Returns a newly allocated list consisting of the top-level elements of list in reverse order.

```(reverse '(a b c))                      =>  (c b a)
(reverse '(a (b c) d (e (f))))          =>  ((e (f)) d (b c) a)
```

procedure+: reverse! list
Returns a list consisting of the top-level elements of list in reverse order. `reverse!` is like `reverse`, except that it destructively modifies list. Because the result may not be `eqv?` to list, it is desirable to do something like `(set! x (reverse! x))`.

procedure+: last-pair list
Returns the last pair in list, which may be an improper list. `last-pair` could have been defined this way:

```(define last-pair
(lambda (x)
(if (pair? (cdr x))
(last-pair (cdr x))
x)))
```

procedure+: except-last-pair list
procedure+: except-last-pair! list
These procedures remove the last pair from list. List may be an improper list, except that it must consist of at least one pair. `except-last-pair` returns a newly allocated copy of list that omits the last pair. `except-last-pair!` destructively removes the last pair from list and returns list. If the cdr of list is not a pair, the empty list is returned by either procedure.

procedure+: sort list procedure
Procedure must be a procedure of two arguments that defines a total ordering on the elements of list. In other words, if x and y are two distinct elements of list, then it must be the case that

```(and (procedure x y)
(procedure y x))
=>  #f
```

`sort` returns a newly allocated list whose elements are the elements of list, except that the elements are rearranged so that they are sorted in the order defined by procedure. So, for example, if the elements of list are numbers, and procedure is `<`, then the resulting list is sorted in monotonically nondecreasing order. Likewise, if procedure is `>`, the resulting list is sorted in monotonically nonincreasing order. To be precise, if x and y are any two adjacent elements in the resulting list, where x precedes y, it is the case that

```(procedure y x)
=>  #f
```