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 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: 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: 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: 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. This section describes the simple operations that are available for constructing and manipulating arbitrary graphs constructed from pairs. sublist returns a newly allocated list formed from the elements of list beginning at index start (inclusive) and ending at end (exclusive). 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. Here are some examples that demonstrate how delete-member-procedure could have been used to implement delv and delete!: 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. 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: 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: If sequence is a list (vector), sort returns a newly allocated list (vector) whose elements are those of sequence, except that they are rearranged to be sorted in the order defined by procedure. So, for example, if the elements of sequence are numbers, and procedure is <,, then the resulting elements are sorted in monotonically nondecreasing order. Likewise, if procedure is >,, the resulting elements are sorted in monotonically nonincreasing order. To be precise, if x and y are any two adjacent elements in the result, where x precedes y, it is the case that Source.