Next: Construction of Lists, Previous: Lists, Up: Lists

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

— procedure: **pair?**` object`

Returns

`#t`

ifobjectis 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

obj1and whose cdr isobj2. 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: **xcons**` obj1 obj2`

(SRFI 1) Returns a newly allocated pair whose car is

obj2and whose cdr isobj1.(xcons '(b c) 'a) => (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: **car+cdr**` pair`

(SRFI 1) The fundamental pair deconstructor:

(lambda (p) (values (car p) (cdr p)))(receive (a b) (car+cdr (cons 1 2)) (write-line a) (write-line b)) -| 1 -| 2

— procedure: **set-car!**` pair object`

Stores

objectin the car field ofpair. 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

objectin the cdr field ofpair. The value returned by`set-cdr!`

is unspecified.

— procedure: **caar**` pair`

— procedure:**cadr**` pair`

— procedure:**cdar**` pair`

— procedure:**cddr**` pair`

— procedure:**caaar**` pair`

— procedure:**caadr**` pair`

— procedure:**cadar**` pair`

— procedure:**caddr**` pair`

— procedure:**cdaar**` pair`

— procedure:**cdadr**` pair`

— procedure:**cddar**` pair`

— procedure:**cdddr**` pair`

— procedure:**caaaar**` pair`

— procedure:**caaadr**` pair`

— procedure:**caadar**` pair`

— procedure:**caaddr**` pair`

— procedure:**cadaar**` pair`

— procedure:**cadadr**` pair`

— procedure:**caddar**` pair`

— procedure:**cadddr**` pair`

— procedure:**cdaaar**` pair`

— procedure:**cdaadr**` pair`

— procedure:**cdadar**` pair`

— procedure:**cdaddr**` pair`

— procedure:**cddaar**` pair`

— procedure:**cddadr**` pair`

— procedure:**cdddar**` pair`

— procedure:**cddddr**` pair`

— procedure:

— procedure:

— procedure:

— procedure:

— procedure:

— procedure:

— procedure:

— procedure:

— procedure:

— procedure:

— procedure:

— procedure:

— procedure:

— procedure:

— procedure:

— procedure:

— procedure:

— procedure:

— procedure:

— procedure:

— procedure:

— procedure:

— procedure:

— procedure:

— procedure:

— procedure:

— procedure:

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`

.Pathencodes a particular sequence of`car`

and`cdr`

operations, which`general-car-cdr`

executes onobject.Pathis 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.^{1}For example, the following are equivalent:

(general-car-cdrobject#b1011) (cdr (car (carobject)))Here is a partial table of path/operation equivalents:

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

— procedure: **tree-copy**` tree`

(SRFI 1) This copies an arbitrary

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

[1] Note that
`path` is restricted to a machine-dependent range, usually the size
of a machine word. On many machines, this means that the maximum length
of `path` will be 30 operations (32 bits, less the sign bit and the
“end-of-sequence” bit).