commit e26e1581c70d577ebb79da1130888348d93b6f60
parent a6d3d3034fa774692e7b13d75c57484cf42e90d3
Author: Wolfgang Corcoran-Mathe <wcm@sigwinch.xyz>
Date: Sat, 3 Feb 2024 14:14:38 -0500
Pairs & Lists: Texify.
Diffstat:
1 file changed, 155 insertions(+), 203 deletions(-)
diff --git a/doc/r7rs-small/procedures/pairs-and-lists.texinfo b/doc/r7rs-small/procedures/pairs-and-lists.texinfo
@@ -1,99 +1,115 @@
@node Pairs and lists
@section Pairs and 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!.
+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 list can be defined recursively as either the
-empty listor a pair whose cdr is a list. More precisely, the set of lists is defined as the
-smallest set
+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
-X such that
+@itemize
-* The empty list is in
+@item
+The empty list is in @var{X}.
- X.
+@item
+If @var{list} is in @var{X}, then any pair whose cdr field contains
+@var{list} is also in @var{X}.
-* If
+@end itemize
- list is in
+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.
- X, then any pair whose cdr field contains
+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.
- 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 listis 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 (
+Note:
+The above definitions imply that all lists have finite length and are
+terminated by the empty list.
-c1 .
+The most general notation (external representation) for Scheme pairs is
+the ``dotted'' notation @code{(}@var{c@sub{1}}@code{ . }@var{c@sub{2}}@code{)} where
+@var{c@sub{1}} is the value of the car field and @var{c@sub{2}} 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.
-c2)
+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,
-where
+@lisp
+(a b c d e)
+@end lisp
-c1 is the value of the car field and
+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.
+@lisp
+(a . (b . (c . (d . (e . ())))))
+@end lisp
-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 listis written (). For
-example,
+are equivalent notations for a list of symbols.
-(a b c d e) and
+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:
-(a . (b . (c . (d . (e . ()))))) are equivalent notations for a list of symbols.
+@lisp
+(a b c . d)
+@end lisp
-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:
+is equivalent to
-(a b c . d) is equivalent to
+@lisp
+(a . (b . (c . d)))
+@end lisp
-(a . (b . (c . d))) 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:
+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
+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{} #t
-(set-cdr! x 4) @result{} unspecified
+(list? y) @result{} @code{#t}
+(set-cdr! x 4) @result{} @r{unspecified}
x @result{} (a . 4)
-(eqv? x y) @result{} #t
+(eqv? x y) @result{} @code{#t}
y @result{} (a . 4)
-(list? y) @result{} #f
-(set-cdr! x x) @result{} unspecified
-(list? x) @result{} #f Within literal expressions and representations of objects read by the
-read procedure, the forms '@svar{datum}, `@svar{datum}, ,@svar{datum}, and ,@@@svar{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 @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} (see
-section 7.1.2). Among other things, this permits the use of the read procedure to parse
-Scheme programs. See section 3.3.
+(list? y) @result{} @code{#f}
+(set-cdr! x x) @result{} @r{unspecified}
+(list? x) @result{} @code{#f}
+@end lisp
-@deffn procedure pair? obj
+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{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}).
+Among other things, this permits the use of the @code{read} procedure to
+parse Scheme programs. @xref{External representations}.
-The pair? predicate returns #t if
+@deffn procedure pair? obj
-obj is a pair, and otherwise returns #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
@@ -105,12 +121,9 @@ obj is a pair, and otherwise returns #f.
@deffn 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 existing
-object.
+Returns a newly allocated pair whose car is @var{obj@sub{1}} and whose cdr is
+@var{obj@sub{2}}. The pair is guaranteed to be different (in the sense of
+@code{eqv?}) from every existing object.
@lisp
(cons 'a '()) @result{} (a)
@@ -124,51 +137,44 @@ object.
@deffn 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.
+@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 '()) @result{} error
+(car '()) @error{}
@end lisp
@end deffn
@deffn 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.
+@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 '()) @result{} error
+(cdr '()) @error{}
@end lisp
@end deffn
@deffn procedure set-car! pair obj
-Stores
-
-obj in the car field of
-
-pair.
+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{} unspecified
-(set-car! (g) 3) @result{} error
+(set-car! (f) 3) @result{} @r{unspecified}
+(set-car! (g) 3) @error{}
+@end lisp
@end deffn
@deffn procedure set-cdr! pair obj
-Stores
-
-obj in the cdr field of
+Stores @var{obj} in the cdr field of @var{pair}.
-pair.
@end deffn
@deffn procedure caar pair
@@ -176,7 +182,7 @@ pair.
@deffnx procedure cdar pair
@deffnx procedure cddr pair
-These procedures are compositions of car and cdr as follows:
+These procedures are compositions of @code{car} and @code{cdr} as follows:
@lisp
(define (caar x) (car (car x)))
@@ -184,16 +190,19 @@ These procedures are compositions of car and cdr as follows:
(define (cdar x) (cdr (car x)))
(define (cddr x) (cdr (cdr x)))
@end lisp
+
@end deffn
+@c TODO: Figure out how to display this.
@deffn {cxr library procedure} caaar @var{pair}
@deffnx {cxr library procedure} caadr @var{pair}
@deffnx {cxr library procedure} c...r @var{pair}
@deffnx {cxr library procedure} cdddar @var{pair}
@deffnx {cxr library procedure} cddddr @var{pair}
-These twenty-four procedures are further compositions of car and cdr on the same
-principles. For example, 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))))).
@@ -206,17 +215,16 @@ provided.
@deffn procedure null? obj
-Returns #t if
+Returns @code{#t} if @var{obj} is the empty list,
+otherwise returns @code{#f}.
-obj is the empty list, otherwise returns #f.
@end deffn
@deffn procedure list? obj
-Returns #t if
-
-obj is a list. Otherwise, it returns #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
@@ -226,20 +234,20 @@ terminated by the empty list.
(set-cdr! x x)
(list? x)) @result{} #f
@end lisp
+
@end deffn
@deffn procedure make-list k
@deffnx procedure make-list k fill
-Returns a newly allocated list of
-
-k elements. If a second argument is given, then each element is initialized to
-
-fill. Otherwise the initial contents of each element is unspecified.
+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)
@end lisp
+
@end deffn
@deffn procedure list obj @dots{}
@@ -250,6 +258,7 @@ Returns a newly allocated list of its arguments.
(list 'a (+ 3 4) 'c) @result{} (a 7 c)
(list) @result{} ()
@end lisp
+
@end deffn
@deffn procedure length list
@@ -261,6 +270,7 @@ Returns the length of @var{list}.
(length '(a (b) (c d e))) @result{} 3
(length '()) @result{} 0
@end lisp
+
@end deffn
@deffn procedure append list@dots{}
@@ -298,17 +308,10 @@ Returns a newly allocated list consisting of the elements of
@deffn procedure list-tail list k
-It is an error if
-
-list has fewer than
-
-k elements.
-
-Returns the sublist of
+It is an error if @var{list} has fewer than @var{k} elements.
-list obtained by omitting the first
-
-k elements. The 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
@@ -321,23 +324,11 @@ k elements. The list-tail procedure could be defined by
@deffn procedure list-ref list k
-The
-
-list argument can be circular, but it is an error if
-
-list has
-
-k or fewer elements.
-
-Returns the
+The @var{list} argument can be circular, but
+it is an error if @var{list} has fewer than @var{k} elements.
-kth element of
-
-list. (This is the same as the car of (list-tail
-
-list
-
-k).)
+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
@@ -349,19 +340,10 @@ k).)
@deffn procedure list-set! list k obj
-It is an error if
-
-k is not a valid index of
-
-list.
+It is an error if @var{k} is not a valid index of @var{list}.
-The list-set! procedure stores
-
-obj in element
-
-k of
-
-list.
+The @code{list-set!} procedure stores @var{obj} in element @var{k}
+of @var{list}.
@lisp
(let ((ls (list 'one 'two 'five!)))
@@ -370,7 +352,7 @@ list.
@result{} (one two three)
(list-set! '(0 1 2) 1 "oops")
-@result{} error ; constant list
+@error{} ; constant list
@end lisp
@end deffn
@@ -379,31 +361,15 @@ list.
@deffnx procedure member obj list
@deffnx procedure member obj list compare
-These procedures return the first sublist of
-
-list whose car is
-
-obj, where the sublists of
-
-list are the non-empty lists returned by (list-tail
-
-list
-
-k) for
-
-k less than the length of
-
-list. If
-
-obj does not occur in
-
-list, then #f (not the empty list) is returned. The memq procedure uses eq? to compare
-
-obj with the elements of
-
-list, while memv uses eqv? and member uses
-
-compare, if given, and equal? otherwise.
+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.
@lisp
(memq 'a '(a b c)) @result{} (a b c)
@@ -415,7 +381,7 @@ compare, if given, and equal? otherwise.
(member "B"
'("a" "b" "c")
string-ci=?) @result{} ("b" "c")
-(memq 101 '(100 101 102)) @result{} unspecified
+(memq 101 '(100 101 102)) @result{} @r{unspecified}
(memv 101 '(100 101 102)) @result{} (101 102)
@end lisp
@end deffn
@@ -425,26 +391,15 @@ compare, if given, and equal? otherwise.
@deffnx procedure assoc obj alist
@deffnx procedure assoc obj alist compare
-It is an error if
-
-alist (for ``association list'') is not a list of pairs.
-
-These procedures find the first pair in
-
-alist whose car field is
-
-obj, and returns that pair. If no pair in
-
-alist has
+It is an error if @var{alist} (for ``association list'') is not a list of
+pairs.
-obj as its car, then #f (not the empty list) is returned. The assq procedure uses eq? to
-compare
-
-obj with the car fields of the pairs in
-
-alist, while assv uses eqv? and assoc uses
-
-compare if given and 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)))
@@ -458,31 +413,27 @@ compare if given and equal? otherwise.
(assoc 2.0 '((1 1) (2 4) (3 9)) =)
@result{} (2 4)
(assq 5 '((2 3) (5 7) (11 13)))
- @result{} unspecified
+ @result{} @r{unspecified}
(assv 5 '((2 3) (5 7) (11 13)))
@result{} (5 7)
@end lisp
-Rationale: Although they are often used as predicates, memq, memv, member, assq,
- assv, and assoc do not have question marks in their names because they return
- potentially useful values rather than just #t or #f.
@end deffn
-@deffn procedure list-copy obj
-
-Returns a newly allocated copy of the given
+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}.
-obj if it is a list. Only the pairs themselves are copied; the cars of the result are the same
-(in the sense of eqv?) as the cars of
-
-list. If
-
-obj is an improper list, so is the result, and the final cdrs are the same in the sense of
-eqv?. An
-
-obj which is not a list is returned unchanged. It is an error if
+@deffn procedure list-copy obj
-obj is a circular list.
+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.
@lisp
(define a '(1 8 2 8)) ; a may be immutable
@@ -491,4 +442,5 @@ obj is a circular list.
b @result{} (3 8 2 8)
a @result{} (1 8 2 8)
@end lisp
+
@end deffn
