pairs-and-lists.texinfo (12930B)
1 @node Pairs and lists 2 @section Pairs and lists 3 4 A @define{pair} (sometimes called a @define{dotted pair}) is a record 5 structure with two fields called the car and cdr fields (for historical 6 reasons). Pairs are created by the procedure @code{cons}. The car and 7 cdr fields are accessed by the procedures @code{car} and @code{cdr}. The 8 car and cdr fields are assigned by the procedures @code{set-car!} 9 and @code{set-cdr!}. 10 11 @cindex empty list 12 13 Pairs are used primarily to represent lists. A @define{list} can be defined 14 recursively as either the empty list or a pair whose cdr is a list. More 15 precisely, the set of lists is defined as the smallest set @var{X} 16 such that 17 18 @itemize 19 20 @item 21 The empty list is in @var{X}. 22 23 @item 24 If @var{list} is in @var{X}, then any pair whose cdr field contains 25 @var{list} is also in @var{X}. 26 27 @end itemize 28 29 The objects in the car fields of successive pairs of a list are the 30 elements of the list. For example, a two-element list is a pair whose 31 car is the first element and whose cdr is a pair whose car is the second 32 element and whose cdr is the empty list. The length of a list is the 33 number of elements, which is the same as the number of pairs. 34 35 @cindex empty list 36 37 The empty list is a special object of its own type. It is not a pair, 38 it has no elements, and its length is zero. 39 40 Note: The above definitions imply that all lists have finite length and 41 are terminated by the empty list. 42 43 The most general notation (external representation) for Scheme pairs 44 is the ``dotted'' notation @code{(}@vari{c}@code{ . }@varii{c}@code{)} 45 where @vari{c} is the value of the car field and @varii{c} is the value of 46 the cdr field. For example @code{(4 . 5)} is a pair whose car is 4 and 47 whose cdr is 5. Note that @code{(4 . 5)} is the external representation 48 of a pair, not an expression that evaluates to a pair. 49 50 @cindex empty list 51 52 A more streamlined notation can be used for lists: the elements of 53 the list are simply enclosed in parentheses and separated by spaces. 54 The empty list is written @code{()}. For example, 55 56 @lisp 57 (a b c d e) 58 @end lisp 59 60 and 61 62 @lisp 63 (a . (b . (c . (d . (e . ()))))) 64 @end lisp 65 66 are equivalent notations for a list of symbols. 67 68 A chain of pairs not ending in the empty list is called an 69 @define{improper list}. Note that an improper list is not a list. The list 70 and dotted notations can be combined to represent improper lists: 71 72 @lisp 73 (a b c . d) 74 @end lisp 75 76 is equivalent to 77 78 @lisp 79 (a . (b . (c . d))) 80 @end lisp 81 82 Whether a given pair is a list depends upon what is stored in the cdr 83 field. When the @code{set-cdr!} procedure is used, an object can be a 84 list one moment and not the next: 85 86 @lisp 87 (define x (list 'a 'b 'c)) 88 (define y x) 89 y @result{} (a b c) 90 (list? y) @result{} @code{#t} 91 (set-cdr! x 4) @result{} @r{unspecified} 92 x @result{} (a . 4) 93 (eqv? x y) @result{} @code{#t} 94 y @result{} (a . 4) 95 (list? y) @result{} @code{#f} 96 (set-cdr! x x) @result{} @r{unspecified} 97 (list? x) @result{} @code{#f} 98 @end lisp 99 100 Within literal expressions and representations of objects read by the 101 @code{read} procedure, the forms @code{'}@svar{datum}, 102 @code{`}@svar{datum}, @code{,}@svar{datum}, and @code{,@@}@svar{datum} 103 denote two-element lists whose first elements are the symbols 104 @code{quote}, @code{quasiquote}, @code{unquote}, and 105 @code{unquote-splicing}, respectively. The second element in each case 106 is @svar{datum}. This convention is supported so that arbitrary Scheme 107 programs can be represented as lists. That is, according to Scheme's 108 grammar, every @svar{expression} is also a @svar{datum} 109 (@xref{External representations formal}). 110 Among other things, this permits the use of the @code{read} procedure to 111 parse Scheme programs. @xref{External representations basic}. 112 113 @deffn procedure pair? obj 114 115 The @code{pair?} predicate returns @code{#t} if @var{obj} is a pair, 116 and otherwise returns @code{#f}. 117 118 @lisp 119 (pair? '(a . b)) @result{} #t 120 (pair? '(a b c)) @result{} #t 121 (pair? '()) @result{} #f 122 (pair? '#(a b)) @result{} #f 123 @end lisp 124 @end deffn 125 126 @deffn procedure cons @vari{obj} @varii{obj} 127 128 Returns a newly allocated pair whose car is @vari{obj} and whose cdr is 129 @varii{obj}. The pair is guaranteed to be different (in the sense of 130 @code{eqv?}) from every existing object. 131 132 @lisp 133 (cons 'a '()) @result{} (a) 134 (cons '(a) '(b c d)) @result{} ((a) b c d) 135 (cons "a" '(b c)) @result{} ("a" b c) 136 (cons 'a 3) @result{} (a . 3) 137 (cons '(a b) 'c) @result{} ((a b) . c) 138 @end lisp 139 @end deffn 140 141 @deffn procedure car pair 142 143 @cindex empty list 144 145 Returns the contents of the car field of @var{pair}. Note that it is an 146 error to take the car of the empty list. 147 148 @lisp 149 (car '(a b c)) @result{} a 150 (car '((a) b c d)) @result{} (a) 151 (car '(1 . 2)) @result{} 1 152 (car '()) @result{} @r{error} 153 @end lisp 154 @end deffn 155 156 @deffn procedure cdr pair 157 158 Returns the contents of the cdr field of @var{pair}. Note that it is an 159 error to take the cdr of the empty list. 160 161 @lisp 162 (cdr '((a) b c d)) @result{} (b c d) 163 (cdr '(1 . 2)) @result{} 2 164 (cdr '()) @result{} @r{error} 165 @end lisp 166 @end deffn 167 168 @deffn procedure set-car! pair obj 169 170 Stores @var{obj} in the car field of @var{pair}. 171 172 @lisp 173 (define (f) (list 'not-a-constant-list)) 174 (define (g) '(constant-list)) 175 (set-car! (f) 3) @result{} @r{unspecified} 176 (set-car! (g) 3) @result{} @r{error} 177 @end lisp 178 @end deffn 179 180 @deffn procedure set-cdr! pair obj 181 182 Stores @var{obj} in the cdr field of @var{pair}. 183 184 @end deffn 185 186 @deffn procedure caar pair 187 @deffnx procedure cadr pair 188 @deffnx procedure cdar pair 189 @deffnx procedure cddr pair 190 191 These procedures are compositions of @code{car} and @code{cdr} as 192 follows: 193 194 @lisp 195 (define (caar x) (car (car x))) 196 (define (cadr x) (car (cdr x))) 197 (define (cdar x) (cdr (car x))) 198 (define (cddr x) (cdr (cdr x))) 199 @end lisp 200 201 @end deffn 202 203 @c This formatting isn't great. 204 @deffn {cxr library procedure} caaar @var{pair} 205 @deffnx {cxr library procedure} caadr @var{pair} 206 @end deffn 207 @dots{} 208 @deffn {cxr library procedure} cdddar @var{pair} 209 @deffnx {cxr library procedure} cddddr @var{pair} 210 211 These twenty-four procedures are further compositions of @code{car} and 212 @code{cdr} on the same principles. For example, @code{caddr} could be 213 defined by 214 215 @lisp 216 (define caddr (lambda (x) (car (cdr (cdr x))))). 217 @end lisp 218 219 Arbitrary compositions up to four deep are provided. 220 221 @end deffn 222 223 @deffn procedure null? obj 224 225 @cindex empty list 226 227 Returns @code{#t} if @var{obj} is the empty list, 228 otherwise returns @code{#f}. 229 230 @end deffn 231 232 @deffn procedure list? obj 233 234 Returns @code{#t} if @var{obj} is a list. Otherwise, it returns 235 @code{#f}. By definition, all lists have finite length and are 236 terminated by the empty list. 237 238 @lisp 239 (list? '(a b c)) @result{} #t 240 (list? '()) @result{} #t 241 (list? '(a . b)) @result{} #f 242 (let ((x (list 'a))) 243 (set-cdr! x x) 244 (list? x)) @result{} #f 245 @end lisp 246 247 @end deffn 248 249 @deffn procedure make-list k 250 @deffnx procedure make-list k fill 251 252 Returns a newly allocated list of @var{k} elements. If a second 253 argument is given, then each element is initialized to @var{fill}. 254 Otherwise the initial contents of each element is unspecified. 255 256 @lisp 257 (make-list 2 3) @result{} (3 3) 258 @end lisp 259 260 @end deffn 261 262 @deffn procedure list obj @dots{} 263 264 Returns a newly allocated list of its arguments. 265 266 @lisp 267 (list 'a (+ 3 4) 'c) @result{} (a 7 c) 268 (list) @result{} () 269 @end lisp 270 271 @end deffn 272 273 @deffn procedure length list 274 275 Returns the length of @var{list}. 276 277 @lisp 278 (length '(a b c)) @result{} 3 279 (length '(a (b) (c d e))) @result{} 3 280 (length '()) @result{} 0 281 @end lisp 282 283 @end deffn 284 285 @deffn procedure append list@dots{} 286 287 The last argument, if there is one, can be of any type. 288 289 Returns a list consisting of the elements of the first @var{list} 290 followed by the elements of the other @var{lists}. If there are no 291 arguments, the empty list is returned. If there is exactly one 292 argument, it is returned. Otherwise the resulting list is always newly 293 allocated, except that it shares structure with the last argument. An 294 improper list results if the last argument is not a proper list. 295 296 @lisp 297 (append '(x) '(y)) @result{} (x y) 298 (append '(a) '(b c d)) @result{} (a b c d) 299 (append '(a (b)) '((c))) @result{} (a (b) (c)) 300 301 (append '(a b) '(c . d)) @result{} (a b c . d) 302 (append '() 'a) @result{} a 303 @end lisp 304 305 @end deffn 306 307 @deffn procedure reverse list 308 309 Returns a newly allocated list consisting of the elements of @var{list} 310 in reverse order. 311 312 @lisp 313 (reverse '(a b c)) @result{} (c b a) 314 (reverse '(a (b c) d (e (f)))) @result{} ((e (f)) d (b c) a) 315 @end lisp 316 317 @end deffn 318 319 @deffn procedure list-tail list k 320 321 It is an error if @var{list} has fewer than @var{k} elements. 322 323 Returns the sublist of @var{list} obtained by omitting the first 324 @var{k} elements. The @code{list-tail} procedure could be defined by 325 326 @lisp 327 (define list-tail 328 (lambda (x k) 329 (if (zero? k) 330 x 331 (list-tail (cdr x) (- k 1))))) 332 @end lisp 333 334 @end deffn 335 336 @deffn procedure list-ref list k 337 338 The @var{list} argument can be circular, but it is an error if @var{list} 339 has @var{k} or fewer elements. 340 341 Returns the @var{k}th element of @var{list}. (This is the same as the 342 car of @code{(list-tail }@var{list} @var{k}@code{)}.) 343 344 @lisp 345 (list-ref '(a b c d) 2) @result{} c 346 (list-ref '(a b c d) (exact (round 1.8))) @result{} c 347 @end lisp 348 349 @end deffn 350 351 @deffn procedure list-set! list k obj 352 353 It is an error if @var{k} is not a valid index of @var{list}. 354 355 The @code{list-set!} procedure stores @var{obj} in element @var{k} of 356 @var{list}. 357 358 @lisp 359 (let ((ls (list 'one 'two 'five!))) 360 (list-set! ls 2 'three) 361 ls) @result{} (one two three) 362 363 (list-set! '(0 1 2) 1 "oops") @result{} @r{error} ; constant list 364 @end lisp 365 @end deffn 366 367 @deffn procedure memq obj list 368 @deffnx procedure memv obj list 369 @deffnx procedure member obj list 370 @deffnx procedure member obj list compare 371 372 These procedures return the first sublist of @var{list} whose car is 373 @var{obj}, where the sublists of @var{list} are the non-empty lists 374 returned by @code{(list-tail }@var{list} @var{k}@code{)} for @var{k} 375 less than the length of @var{list}. If @var{obj} does not occur in 376 @var{list}, then @code{#f} (not the empty list) is returned. The 377 @code{memq} procedure uses @code{eq?} to compare @var{obj} with the 378 elements of @var{list}, while @code{memv} uses @code{eqv?} and 379 @code{member} uses @var{compare}, if given, and @code{equal?} 380 otherwise. 381 382 @lisp 383 (memq 'a '(a b c)) @result{} (a b c) 384 (memq 'b '(a b c)) @result{} (b c) 385 (memq 'a '(b c d)) @result{} #f 386 (memq (list 'a) '(b (a) c)) @result{} #f 387 (member (list 'a) 388 '(b (a) c)) @result{} ((a) c) 389 (member "B" 390 '("a" "b" "c") 391 string-ci=?) @result{} ("b" "c") 392 (memq 101 '(100 101 102)) @result{} @r{unspecified} 393 (memv 101 '(100 101 102)) @result{} (101 102) 394 @end lisp 395 396 @end deffn 397 398 @deffn procedure assq obj alist 399 @deffnx procedure assv obj alist 400 @deffnx procedure assoc obj alist 401 @deffnx procedure assoc obj alist compare 402 403 It is an error if @var{alist} (for ``association list'') is not a list 404 of pairs. 405 406 These procedures find the first pair in @var{alist} whose car field 407 is @var{obj}, and returns that pair. If no pair in @var{alist} has 408 @var{obj} as its car, then @code{#f} (not the empty list) is returned. 409 The @code{assq} procedure uses @code{eq?} to compare @var{obj} with the 410 car fields of the pairs in @var{alist}, while @code{assv} uses @code{eqv?} 411 and @code{assoc} uses @var{compare} if given and @code{equal?} otherwise. 412 413 @lisp 414 (define e '((a 1) (b 2) (c 3))) 415 (assq 'a e) @result{} (a 1) 416 (assq 'b e) @result{} (b 2) 417 (assq 'd e) @result{} #f 418 (assq (list 'a) '(((a)) ((b)) ((c)))) @result{} #f 419 (assoc (list 'a) '(((a)) ((b)) ((c)))) @result{} ((a)) 420 (assoc 2.0 '((1 1) (2 4) (3 9)) =) @result{} (2 4) 421 (assq 5 '((2 3) (5 7) (11 13))) @result{} @r{unspecified} 422 (assv 5 '((2 3) (5 7) (11 13))) @result{} (5 7) 423 @end lisp 424 425 @end deffn 426 427 Although they are often used as predicates, @code{memq}, @code{memv}, 428 @code{member}, @code{assq}, @code{assv}, and @code{assoc} do not have 429 question marks in their names because they return potentially useful 430 values rather than just @code{#t} or @code{#f}. 431 432 @deffn procedure list-copy obj 433 434 Returns a newly allocated copy of the given @var{obj} if it is a list. 435 Only the pairs themselves are copied; the cars of the result are the same 436 (in the sense of @code{eqv?}) as the cars of @var{list}. If @var{obj} 437 is an improper list, so is the result, and the final cdrs are the same in 438 the sense of @code{eqv?}. An @var{obj} which is not a list is returned 439 unchanged. It is an error if @var{obj} is a circular list. 440 441 @lisp 442 (define a '(1 8 2 8)) ; a may be immutable 443 (define b (list-copy a)) 444 (set-car! b 3) ; b is mutable 445 b @result{} (3 8 2 8) 446 a @result{} (1 8 2 8) 447 @end lisp 448 449 @end deffn