commit 2a8df0d95ff0336a6a0772530ee5d41a7c62e017
parent 2f3a977b58fe7e8f7cce32179e6b8bf2997279b5
Author: Wolfgang Corcoran-Mathe <wcm@sigwinch.xyz>
Date: Sat, 3 Feb 2024 14:28:46 -0500
Pairs & Lists: Reflow paragraphs & tidy examples.
Diffstat:
1 file changed, 159 insertions(+), 167 deletions(-)
diff --git a/doc/r7rs-small/procedures/pairs-and-lists.texinfo b/doc/r7rs-small/procedures/pairs-and-lists.texinfo
@@ -1,17 +1,17 @@
@node Pairs and lists
@section Pairs and lists
-A @dfn{pair} (sometimes called a @dfn{dotted pair}) is a
-record structure with two fields called the car and cdr fields (for
-historical reasons). Pairs are created by the procedure @code{cons}.
-The car and cdr fields are accessed by the procedures @code{car} and
-@code{cdr}. The car and cdr fields are assigned by the procedures
-@code{set-car!} and @code{set-cdr!}.
-
-Pairs are used primarily to represent lists. A @dfn{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 @var{X} such that
+A @dfn{pair} (sometimes called a @dfn{dotted pair}) is a record
+structure with two fields called the car and cdr fields (for historical
+reasons). Pairs are created by the procedure @code{cons}. The car and
+cdr fields are accessed by the procedures @code{car} and @code{cdr}. The
+car and cdr fields are assigned by the procedures @code{set-car!}
+and @code{set-cdr!}.
+
+Pairs are used primarily to represent lists. A @dfn{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 @var{X}
+such that
@itemize
@@ -25,28 +25,27 @@ If @var{list} is in @var{X}, then any pair whose cdr field contains
@end itemize
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.
+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.
+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.
+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 @code{(}@vari{c}@code{ . }@varii{c}@code{)} where
-@vari{c} is the value of the car field and @varii{c} is the value of the
-cdr field. For example @code{(4 . 5)} is a pair whose car is 4 and whose
-cdr is 5. Note that @code{(4 . 5)} is the external representation of a
-pair, not an expression that evaluates to a pair.
+The most general notation (external representation) for Scheme pairs
+is the ``dotted'' notation @code{(}@vari{c}@code{ . }@varii{c}@code{)}
+where @vari{c} is the value of the car field and @varii{c} is the value of
+the cdr field. For example @code{(4 . 5)} is a pair whose car is 4 and
+whose cdr is 5. Note that @code{(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 @code{()}. For example,
+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 @code{()}. For example,
@lisp
(a b c d e)
@@ -61,9 +60,8 @@ and
are equivalent notations for a list of symbols.
A chain of pairs not ending in the empty list is called an
-@dfn{improper list}. Note that an improper list is not a list.
-The list and dotted notations can be combined to represent
-improper lists:
+@dfn{improper list}. Note that an improper list is not a list. The list
+and dotted notations can be combined to represent improper lists:
@lisp
(a b c . d)
@@ -76,86 +74,86 @@ is equivalent to
@end lisp
Whether a given pair is a list depends upon what is stored in the cdr
-field. When the @code{set-cdr!} procedure is used, an object can be a
+field. When the @code{set-cdr!} procedure is used, an object can be a
list one moment and not the next:
@lisp
(define x (list 'a 'b 'c))
(define y x)
-y @result{} (a b c)
-(list? y) @result{} @code{#t}
-(set-cdr! x 4) @result{} @r{unspecified}
-x @result{} (a . 4)
-(eqv? x y) @result{} @code{#t}
-y @result{} (a . 4)
-(list? y) @result{} @code{#f}
-(set-cdr! x x) @result{} @r{unspecified}
-(list? x) @result{} @code{#f}
+y @result{} (a b c)
+(list? y) @result{} @code{#t}
+(set-cdr! x 4) @result{} @r{unspecified}
+x @result{} (a . 4)
+(eqv? x y) @result{} @code{#t}
+y @result{} (a . 4)
+(list? y) @result{} @code{#f}
+(set-cdr! x x) @result{} @r{unspecified}
+(list? x) @result{} @code{#f}
@end lisp
Within literal expressions and representations of objects read by the
@code{read} procedure, the forms @code{'}@svar{datum},
-@code{`}@svar{datum}, @code{,}@svar{datum}, and
-@code{,@@}@svar{datum} denote two-element lists whose first elements are
-the symbols @code{quote}, @code{quasiquote}, @code{unquote}, and
+@code{`}@svar{datum}, @code{,}@svar{datum}, and @code{,@@}@svar{datum}
+denote two-element lists whose first elements are the symbols
+@code{quote}, @code{quasiquote}, @code{unquote}, and
@code{unquote-splicing}, respectively. The second element in each case
is @svar{datum}. This convention is supported so that arbitrary Scheme
-programs can be represented as lists.
-That is, according to Scheme's grammar, every
-@svar{expression} is also a @svar{datum} (@xref{External representations formal}).
+programs can be represented as lists. That is, according to Scheme's
+grammar, every @svar{expression} is also a @svar{datum}
+(@xref{External representations formal}).
Among other things, this permits the use of the @code{read} procedure to
parse Scheme programs. @xref{External representations}.
@deffn procedure pair? obj
-The @code{pair?} predicate returns @code{#t} if @var{obj} is a pair, and otherwise
-returns @code{#f}.
+The @code{pair?} predicate returns @code{#t} if @var{obj} is a pair,
+and otherwise returns @code{#f}.
@lisp
-(pair? '(a . b)) @result{} #t
-(pair? '(a b c)) @result{} #t
-(pair? '()) @result{} #f
-(pair? '#(a b)) @result{} #f
+(pair? '(a . b)) @result{} #t
+(pair? '(a b c)) @result{} #t
+(pair? '()) @result{} #f
+(pair? '#(a b)) @result{} #f
@end lisp
@end deffn
@deffn procedure cons @vari{obj} @varii{obj}
Returns a newly allocated pair whose car is @vari{obj} and whose cdr is
-@varii{obj}. The pair is guaranteed to be different (in the sense of
+@varii{obj}. The pair is guaranteed to be different (in the sense of
@code{eqv?}) from every existing object.
@lisp
-(cons 'a '()) @result{} (a)
-(cons '(a) '(b c d)) @result{} ((a) b c d)
-(cons "a" '(b c)) @result{} ("a" b c)
-(cons 'a 3) @result{} (a . 3)
-(cons '(a b) 'c) @result{} ((a b) . c)
+(cons 'a '()) @result{} (a)
+(cons '(a) '(b c d)) @result{} ((a) b c d)
+(cons "a" '(b c)) @result{} ("a" b c)
+(cons 'a 3) @result{} (a . 3)
+(cons '(a b) 'c) @result{} ((a b) . c)
@end lisp
@end deffn
@deffn procedure car pair
-Returns the contents of the car field of
-@var{pair}. Note that it is an error to take the car of the empty list.
+Returns the contents of the car field of @var{pair}. Note that it is an
+error to take the car of the empty list.
@lisp
-(car '(a b c)) @result{} a
-(car '((a) b c d)) @result{} (a)
-(car '(1 . 2)) @result{} 1
-(car '()) @error{}
+(car '(a b c)) @result{} a
+(car '((a) b c d)) @result{} (a)
+(car '(1 . 2)) @result{} 1
+(car '()) @error{}
@end lisp
@end deffn
@deffn procedure cdr pair
-Returns the contents of the cdr field of
-@var{pair}. Note that it is an error to take the cdr of the empty list.
+Returns the contents of the cdr field of @var{pair}. Note that it is an
+error to take the cdr of the empty list.
@lisp
-(cdr '((a) b c d)) @result{} (b c d)
-(cdr '(1 . 2)) @result{} 2
-(cdr '()) @error{}
+(cdr '((a) b c d)) @result{} (b c d)
+(cdr '(1 . 2)) @result{} 2
+(cdr '()) @error{}
@end lisp
@end deffn
@@ -166,8 +164,8 @@ Stores @var{obj} in the car field of @var{pair}.
@lisp
(define (f) (list 'not-a-constant-list))
(define (g) '(constant-list))
-(set-car! (f) 3) @result{} @r{unspecified}
-(set-car! (g) 3) @error{}
+(set-car! (f) 3) @result{} @r{unspecified}
+(set-car! (g) 3) @error{}
@end lisp
@end deffn
@@ -182,7 +180,8 @@ Stores @var{obj} in the cdr field of @var{pair}.
@deffnx procedure cdar pair
@deffnx procedure cddr pair
-These procedures are compositions of @code{car} and @code{cdr} as follows:
+These procedures are compositions of @code{car} and @code{cdr} as
+follows:
@lisp
(define (caar x) (car (car x)))
@@ -200,16 +199,15 @@ These procedures are compositions of @code{car} and @code{cdr} as follows:
@deffnx {cxr library procedure} cdddar @var{pair}
@deffnx {cxr library procedure} cddddr @var{pair}
-These twenty-four procedures are further compositions of @code{car} and @code{cdr}
-on the same principles.
-For example, @code{caddr} could be defined by
+These twenty-four procedures are further compositions of @code{car} and
+@code{cdr} on the same principles. For example, @code{caddr} could be
+defined by
@lisp
(define caddr (lambda (x) (car (cdr (cdr x))))).
@end lisp
-Arbitrary compositions up to four deep are
-provided.
+Arbitrary compositions up to four deep are provided.
@end deffn
@@ -222,17 +220,17 @@ otherwise returns @code{#f}.
@deffn procedure list? obj
-Returns @code{#t} if @var{obj} is a list. Otherwise, it returns @code{#f}.
-By definition, all lists have finite length and are terminated by
-the empty list.
+Returns @code{#t} if @var{obj} is a list. Otherwise, it returns
+@code{#f}. By definition, all lists have finite length and are
+terminated by the empty list.
@lisp
-(list? '(a b c)) @result{} #t
- (list? '()) @result{} #t
- (list? '(a . b)) @result{} #f
- (let ((x (list 'a)))
- (set-cdr! x x)
- (list? x)) @result{} #f
+(list? '(a b c)) @result{} #t
+(list? '()) @result{} #t
+(list? '(a . b)) @result{} #f
+(let ((x (list 'a)))
+ (set-cdr! x x)
+ (list? x)) @result{} #f
@end lisp
@end deffn
@@ -240,12 +238,12 @@ the empty list.
@deffn procedure make-list k
@deffnx procedure make-list k fill
-Returns a newly allocated list of @var{k} elements. If a second
+Returns a newly allocated list of @var{k} elements. If a second
argument is given, then each element is initialized to @var{fill}.
Otherwise the initial contents of each element is unspecified.
@lisp
-(make-list 2 3) @result{} (3 3)
+(make-list 2 3) @result{} (3 3)
@end lisp
@end deffn
@@ -255,8 +253,8 @@ Otherwise the initial contents of each element is unspecified.
Returns a newly allocated list of its arguments.
@lisp
-(list 'a (+ 3 4) 'c) @result{} (a 7 c)
-(list) @result{} ()
+(list 'a (+ 3 4) 'c) @result{} (a 7 c)
+(list) @result{} ()
@end lisp
@end deffn
@@ -266,9 +264,9 @@ Returns a newly allocated list of its arguments.
Returns the length of @var{list}.
@lisp
-(length '(a b c)) @result{} 3
-(length '(a (b) (c d e))) @result{} 3
-(length '()) @result{} 0
+(length '(a b c)) @result{} 3
+(length '(a (b) (c d e))) @result{} 3
+(length '()) @result{} 0
@end lisp
@end deffn
@@ -285,33 +283,34 @@ allocated, except that it shares structure with the last argument. An
improper list results if the last argument is not a proper list.
@lisp
-(append '(x) '(y)) @result{} (x y)
-(append '(a) '(b c d)) @result{} (a b c d)
-(append '(a (b)) '((c))) @result{} (a (b) (c))
+(append '(x) '(y)) @result{} (x y)
+(append '(a) '(b c d)) @result{} (a b c d)
+(append '(a (b)) '((c))) @result{} (a (b) (c))
-(append '(a b) '(c . d)) @result{} (a b c . d)
-(append '() 'a) @result{} a
+(append '(a b) '(c . d)) @result{} (a b c . d)
+(append '() 'a) @result{} a
@end lisp
+
@end deffn
@deffn procedure reverse list
-Returns a newly allocated list consisting of the elements of
-@var{list} in reverse order.
+Returns a newly allocated list consisting of the elements of @var{list}
+in reverse order.
@lisp
-(reverse '(a b c)) @result{} (c b a)
-(reverse '(a (b c) d (e (f))))
-@result{} ((e (f)) d (b c) a)
+(reverse '(a b c)) @result{} (c b a)
+(reverse '(a (b c) d (e (f)))) @result{} ((e (f)) d (b c) a)
@end lisp
+
@end deffn
@deffn procedure list-tail list k
It is an error if @var{list} has fewer than @var{k} elements.
-Returns the sublist of @var{list} obtained by omitting the first @var{k}
-elements. The @code{list-tail} procedure could be defined by
+Returns the sublist of @var{list} obtained by omitting the first
+@var{k} elements. The @code{list-tail} procedure could be defined by
@lisp
(define list-tail
@@ -320,39 +319,37 @@ elements. The @code{list-tail} procedure could be defined by
x
(list-tail (cdr x) (- k 1)))))
@end lisp
+
@end deffn
@deffn procedure list-ref list k
-The @var{list} argument can be circular, but
-it is an error if @var{list} has fewer than @var{k} elements.
+The @var{list} argument can be circular, but it is an error if @var{list}
+has fewer than @var{k} elements.
-Returns the @var{k}th element of @var{list}. (This is the same
-as the car of @code{(list-tail }@var{list} @var{k}@code{)}.)
+Returns the @var{k}th element of @var{list}. (This is the same as the
+car of @code{(list-tail }@var{list} @var{k}@code{)}.)
@lisp
-(list-ref '(a b c d) 2) @result{} c
-(list-ref '(a b c d)
- (exact (round 1.8)))
-@result{} c
+(list-ref '(a b c d) 2) @result{} c
+(list-ref '(a b c d) (exact (round 1.8))) @result{} c
@end lisp
+
@end deffn
@deffn procedure list-set! list k obj
It is an error if @var{k} is not a valid index of @var{list}.
-The @code{list-set!} procedure stores @var{obj} in element @var{k}
-of @var{list}.
+The @code{list-set!} procedure stores @var{obj} in element @var{k} of
+@var{list}.
@lisp
(let ((ls (list 'one 'two 'five!)))
(list-set! ls 2 'three)
- ls)
-@result{} (one two three)
+ ls) @result{} (one two three)
-(list-set! '(0 1 2) 1 "oops")
-@error{} ; constant list
+(list-set! '(0 1 2) 1 "oops") @error{} ; constant list
@end lisp
@end deffn
@@ -363,27 +360,28 @@ of @var{list}.
These procedures return the first sublist of @var{list} whose car is
@var{obj}, where the sublists of @var{list} are the non-empty lists
-returned by @code{(list-tail }@var{list} @var{k}@code{)} for @var{k} less
-than the length of @var{list}. If
-@var{obj} does not occur in @var{list}, then @code{#f} (not the empty list) is
-returned. The @code{memq} procedure uses @code{eq?} to compare @var{obj}
-with the elements of
-@var{list}, while @code{memv} uses @code{eqv?} and
-@code{member} uses @var{compare}, if given, and @code{equal?} otherwise.
+returned by @code{(list-tail }@var{list} @var{k}@code{)} for @var{k}
+less than the length of @var{list}. If @var{obj} does not occur in
+@var{list}, then @code{#f} (not the empty list) is returned. The
+@code{memq} procedure uses @code{eq?} to compare @var{obj} with the
+elements of @var{list}, while @code{memv} uses @code{eqv?} and
+@code{member} uses @var{compare}, if given, and @code{equal?}
+otherwise.
@lisp
-(memq 'a '(a b c)) @result{} (a b c)
-(memq 'b '(a b c)) @result{} (b c)
-(memq 'a '(b c d)) @result{} #f
-(memq (list 'a) '(b (a) c)) @result{} #f
+(memq 'a '(a b c)) @result{} (a b c)
+(memq 'b '(a b c)) @result{} (b c)
+(memq 'a '(b c d)) @result{} #f
+(memq (list 'a) '(b (a) c)) @result{} #f
(member (list 'a)
- '(b (a) c)) @result{} ((a) c)
+ '(b (a) c)) @result{} ((a) c)
(member "B"
'("a" "b" "c")
- string-ci=?) @result{} ("b" "c")
-(memq 101 '(100 101 102)) @result{} @r{unspecified}
-(memv 101 '(100 101 102)) @result{} (101 102)
+ string-ci=?) @result{} ("b" "c")
+(memq 101 '(100 101 102)) @result{} @r{unspecified}
+(memv 101 '(100 101 102)) @result{} (101 102)
@end lisp
+
@end deffn
@deffn procedure assq obj alist
@@ -391,49 +389,43 @@ with the elements of
@deffnx procedure assoc obj alist
@deffnx procedure assoc obj alist compare
-It is an error if @var{alist} (for ``association list'') is not a list of
-pairs.
+It is an error if @var{alist} (for ``association list'') is not a list
+of pairs.
-These procedures find the first pair in @var{alist} whose car field is @var{obj},
-and returns that pair. If no pair in @var{alist} has @var{obj} as its
-car, then @code{#f} (not the empty list) is returned. The @code{assq} procedure uses
-@code{eq?} to compare @var{obj} with the car fields of the pairs in @var{alist},
-while @code{assv} uses @code{eqv?} and @code{assoc} uses @var{compare} if given
-and @code{equal?} otherwise.
+These procedures find the first pair in @var{alist} whose car field
+is @var{obj}, and returns that pair. If no pair in @var{alist} has
+@var{obj} as its car, then @code{#f} (not the empty list) is returned.
+The @code{assq} procedure uses @code{eq?} to compare @var{obj} with the
+car fields of the pairs in @var{alist}, while @code{assv} uses @code{eqv?}
+and @code{assoc} uses @var{compare} if given and @code{equal?} otherwise.
@lisp
(define e '((a 1) (b 2) (c 3)))
-(assq 'a e) @result{} (a 1)
-(assq 'b e) @result{} (b 2)
-(assq 'd e) @result{} #f
-(assq (list 'a) '(((a)) ((b)) ((c))))
- @result{} #f
-(assoc (list 'a) '(((a)) ((b)) ((c))))
- @result{} ((a))
-(assoc 2.0 '((1 1) (2 4) (3 9)) =)
- @result{} (2 4)
-(assq 5 '((2 3) (5 7) (11 13)))
- @result{} @r{unspecified}
-(assv 5 '((2 3) (5 7) (11 13)))
- @result{} (5 7)
+(assq 'a e) @result{} (a 1)
+(assq 'b e) @result{} (b 2)
+(assq 'd e) @result{} #f
+(assq (list 'a) '(((a)) ((b)) ((c)))) @result{} #f
+(assoc (list 'a) '(((a)) ((b)) ((c)))) @result{} ((a))
+(assoc 2.0 '((1 1) (2 4) (3 9)) =) @result{} (2 4)
+(assq 5 '((2 3) (5 7) (11 13))) @result{} @r{unspecified}
+(assv 5 '((2 3) (5 7) (11 13))) @result{} (5 7)
@end lisp
@end deffn
-Although they are often used as predicates,
-@code{memq}, @code{memv}, @code{member}, @code{assq}, @code{assv}, and @code{assoc} do not
-have question marks in their names because they return
-potentially useful values rather than just @code{#t} or @code{#f}.
+Although they are often used as predicates, @code{memq}, @code{memv},
+@code{member}, @code{assq}, @code{assv}, and @code{assoc} do not have
+question marks in their names because they return potentially useful
+values rather than just @code{#t} or @code{#f}.
@deffn procedure list-copy obj
Returns a newly allocated copy of the given @var{obj} if it is a list.
-Only the pairs themselves are copied; the cars of the result are
-the same (in the sense of @code{eqv?}) as the cars of @var{list}.
-If @var{obj} is an improper list, so is the result, and the final
-cdrs are the same in the sense of @code{eqv?}.
-An @var{obj} which is not a list is returned unchanged.
-It is an error if @var{obj} is a circular list.
+Only the pairs themselves are copied; the cars of the result are the same
+(in the sense of @code{eqv?}) as the cars of @var{list}. If @var{obj}
+is an improper list, so is the result, and the final cdrs are the same in
+the sense of @code{eqv?}. An @var{obj} which is not a list is returned
+unchanged. It is an error if @var{obj} is a circular list.
@lisp
(define a '(1 8 2 8)) ; a may be immutable
