3.9 Pairs and Lists
Pairs and Lists in Guide: Racket introduces pairs and lists.
A pair combines exactly two values. The first value is
accessed with the car procedure, and the second value is
accessed with the cdr procedure. Pairs are not mutable (but
see Mutable Pairs and Lists).
A list is recursively defined: it is either the constant
null, or it is a pair whose second value is a list.
A list can be used as a single-valued sequence (see
Sequences). The elements of the list serve as elements
of the sequence. See also in-list.
Cyclic data structures can be created using only immutable pairs via
read or make-reader-graph. If starting with a pair
and using some number of cdrs returns to the starting pair,
then the pair is not a list.
3.9.1 Pair Constructors and Selectors
Returns #t if v is
a pair, #f otherwise.
Returns #t if v is
the empty list, #f otherwise.
Returns a newly allocated pair whose first
element is a and second element is d.
Returns the first element of the
pair p.
Returns the second element of the
pair p.
Examples: |
| > (cdr '(1 2)) | '(2) | | > (cdr '(1)) | '() |
|
The empty list.
Returns #t if v
is a list: either the empty list, or a pair whose second element is a
list. This procedure effectively takes constant time due to internal caching
(so that any necessary traversals of pairs can in principle count as an
extra cost of allocating the pairs).
Returns a newly allocated list
containing the vs as its elements.
Like
list, but the last argument is used as the tail of
the result, instead of the final element. The result is a list
only if the last argument is a list.
Creates a list of
n elements by applying
proc to the
integers from
0 to
(sub1 n) in order. If
lst is the resulting list, then
(list-ref lst i)
is the value produced by
(proc i).
3.9.2 List Operations
Returns the number of elements in lst.
Returns the element of
lst at position
pos, where
the list’s first element is position
0. If the list has
pos or fewer elements, then the
exn:fail:contract exception is raised.
The lst argument need not actually be a list; lst
must merely start with a chain of at least pos pairs.
Returns the list after the first
pos elements of
lst. If the list has fewer than
pos elements, then
the
exn:fail:contract exception is raised.
The lst argument need not actually be a list; lst
must merely start with a chain of at least pos pairs.
When given all list arguments, the result is a list that contains all
of the elements of the given lists in order. The last argument is used
directly in the tail of the result.
The last argument need not be a list, in which case the result is an
“improper list.”
Returns a list that has the same elements as lst, but in
reverse order.
3.9.3 List Iteration
Applies proc to the elements of the lsts from the
first elements to the last. The proc argument must accept
the same number of arguments as the number of supplied lsts,
and all lsts must have the same number of elements. The
result is a list containing each result of proc in order.
Examples: |
| '(2 3 4 5) | | > (map (lambda (number1 number2) | | (+ number1 number2)) | | '(1 2 3 4) | | '(10 100 1000 10000)) |
| '(11 102 1003 10004) |
|
Similar to
map, except that
the result is #f if any application of proc produces
#f, in which case proc is not applied to later
elements of the lsts; and
the result is that of proc applied to the last elements
of the lsts; more specifically, the application of
proc to the last elements in the lsts is in tail
position with respect to the andmap call.
If the lsts are empty, then #t is returned.
Similar to
map, except that
the result is #f if every application of proc produces
#f; and
the result is that of the first application of proc producing a
value other than #f, in which case proc is not
applied to later elements of the lsts;
the application of proc to the last elements of the
lsts is in tail position with respect to the
ormap call.
If the lsts are empty, then #f is returned.
Similar to
map, but
proc is called only for its
effect, and its result (which can be any number of values) is
ignored.
Like
map,
foldl applies a procedure to the
elements of one or more lists. Whereas
map combines the return
values into a list,
foldl combines the return values in an
arbitrary way that is determined by
proc.
If foldl is called with n lists, then proc
must take n+1 arguments. The extra argument is the combined
return values so far. The proc is initially invoked with the
first item of each list, and the final argument is init. In
subsequent invocations of proc, the last argument is the
return value from the previous invocation of proc. The input
lsts are traversed from left to right, and the result of the
whole foldl application is the result of the last
application of proc. If the lsts are empty, the
result is init.
Unlike foldr, foldl processes the lsts in
constant space (plus the space for each call to proc).
Like
foldl, but the lists are traversed from right to left.
Unlike
foldl,
foldr processes the
lsts in
space proportional to the length of
lsts (plus the space for
each call to
proc).
3.9.4 List Filtering
Returns a list with the elements of lst for which
pred produces a true value. The pred procedure is
applied to each element from first to last.
Returns a list that is like lst, omitting the first element
of lst that is equal to v using the comparison
procedure proc (which must accept two arguments).
Like
remove, but removes from
lst every instance of
every element of
v-lst.
Returns a list sorted according to the less-than? procedure,
which takes two elements of lst and returns a true value if
the first is less (i.e., should be sorted earlier) than the
second.
The sort is stable; if two elements of lst are “equal”
(i.e., proc does not return a true value when given the pair
in either order), then the elements preserve their relative order
from lst in the output list. To preserve this guarantee,
use sort with a strict comparison functions (e.g.,
< or string<?; not <= or
string<=?).
The #:key argument extract-key is used to extract a
key value for comparison from each list element. That is, the full
comparison procedure is essentially
| (lambda (x y) |
| (less-than? (extract-key x) (extract-key y))) |
By default, extract-key is applied to two list elements for
every comparison, but if cache-keys? is true, then the
extract-key function is used exactly once for each list
item. Supply a true value for cache-keys? when
extract-key is an expensive operation; for example, if
file-or-directory-modify-seconds is used to extract a
timestamp for every file in a list, then cache-keys? should
be #t to minimize file-system calls, but if
extract-key is car, then cache-keys?
should be #f. As another example, providing
extract-key as (lambda (x) (random)) and
#t for cache-keys? effectively shuffles the list.
Examples: |
| > (sort '(1 3 4 2) <) | '(1 2 3 4) | | > (sort '("aardvark" "dingo" "cow" "bear") string<?) | '("aardvark" "bear" "cow" "dingo") | | '(("aardvark") ("bear") ("cow") ("dingo")) |
|
3.9.5 List Searching
Locates the first element of
lst that is
equal? to
v. If such an element exists, the tail of
lst
starting with that element is returned. Otherwise, the result is
#f.
Like
member, but finds an element using the predicate
proc; an element is found when
proc applied to the
element returns a true value.
Like
memf, but returns the element or
#f
instead of a tail of
lst or
#f.
Locates the first element of
lst whose
car is
equal? to
v. If such an element exists, the pair
(i.e., an element of
lst) is returned. Otherwise, the result
is
#f.
Like
assoc, but finds an element using
eq?.
Like
assoc, but finds an element using the predicate
proc; an element is found when
proc applied to the
car of an
lst element returns a true value.
3.9.6 Pair Accessor Shorthands
Returns (car (car p))
Returns (car (cdr p))
Returns (cdr (car p))
Example: |
| > (cdar '((7 6 5 4 3 2 1) 8 9)) | '(6 5 4 3 2 1) |
|
Returns (cdr (cdr p))
Returns (car (car (car p)))
Example: |
| > (caaar '(((6 5 4 3 2 1) 7) 8 9)) | 6 |
|
Returns (car (car (cdr p)))
Example: |
| > (caadr '(9 (7 6 5 4 3 2 1) 8)) | 7 |
|
Returns (car (cdr (car p)))
Example: |
| > (cadar '((7 6 5 4 3 2 1) 8 9)) | 6 |
|
Returns (car (cdr (cdr p)))
Returns (cdr (car (car p)))
Example: |
| > (cdaar '(((6 5 4 3 2 1) 7) 8 9)) | '(5 4 3 2 1) |
|
Returns (cdr (car (cdr p)))
Example: |
| > (cdadr '(9 (7 6 5 4 3 2 1) 8)) | '(6 5 4 3 2 1) |
|
Returns (cdr (cdr (car p)))
Example: |
| > (cddar '((7 6 5 4 3 2 1) 8 9)) | '(5 4 3 2 1) |
|
Returns (cdr (cdr (cdr p)))
Returns (car (car (car (car p))))
Example: |
| > (caaaar '((((5 4 3 2 1) 6) 7) 8 9)) | 5 |
|
Returns (car (car (car (cdr p))))
Example: |
| > (caaadr '(9 ((6 5 4 3 2 1) 7) 8)) | 6 |
|
Returns (car (car (cdr (car p))))
Example: |
| > (caadar '((7 (5 4 3 2 1) 6) 8 9)) | 5 |
|
Returns (car (car (cdr (cdr p))))
Example: |
| > (caaddr '(9 8 (6 5 4 3 2 1) 7)) | 6 |
|
Returns (car (cdr (car (car p))))
Example: |
| > (cadaar '(((6 5 4 3 2 1) 7) 8 9)) | 5 |
|
Returns (car (cdr (car (cdr p))))
Example: |
| > (cadadr '(9 (7 6 5 4 3 2 1) 8)) | 6 |
|
Returns (car (cdr (cdr (car p))))
Example: |
| > (caddar '((7 6 5 4 3 2 1) 8 9)) | 5 |
|
Returns (car (cdr (cdr (cdr p))))
Returns (cdr (car (car (car p))))
Example: |
| > (cdaaar '((((5 4 3 2 1) 6) 7) 8 9)) | '(4 3 2 1) |
|
Returns (cdr (car (car (cdr p))))
Example: |
| > (cdaadr '(9 ((6 5 4 3 2 1) 7) 8)) | '(5 4 3 2 1) |
|
Returns (cdr (car (cdr (car p))))
Example: |
| > (cdadar '((7 (5 4 3 2 1) 6) 8 9)) | '(4 3 2 1) |
|
Returns (cdr (car (cdr (cdr p))))
Example: |
| > (cdaddr '(9 8 (6 5 4 3 2 1) 7)) | '(5 4 3 2 1) |
|
Returns (cdr (cdr (car (car p))))
Example: |
| > (cddaar '(((6 5 4 3 2 1) 7) 8 9)) | '(4 3 2 1) |
|
Returns (cdr (cdr (car (cdr p))))
Example: |
| > (cddadr '(9 (7 6 5 4 3 2 1) 8)) | '(5 4 3 2 1) |
|
Returns (cdr (cdr (cdr (car p))))
Example: |
| > (cdddar '((7 6 5 4 3 2 1) 8 9)) | '(4 3 2 1) |
|
Returns (cdr (cdr (cdr (cdr p))))
3.9.7 Additional List Functions and Synonyms
The empty list.
The same as
(car lst), but only for lists (that are not empty).
Example: |
| > (first '(1 2 3 4 5 6 7 8 9 10)) | 1 |
|
The same as
(cdr lst), but only for lists (that are not empty).
Example: |
| > (rest '(1 2 3 4 5 6 7 8 9 10)) | '(2 3 4 5 6 7 8 9 10) |
|
Returns the second element of the list.
Example: |
| > (second '(1 2 3 4 5 6 7 8 9 10)) | 2 |
|
Returns the third element of the list.
Example: |
| > (third '(1 2 3 4 5 6 7 8 9 10)) | 3 |
|
Returns the fourth element of the list.
Example: |
| > (fourth '(1 2 3 4 5 6 7 8 9 10)) | 4 |
|
Returns the fifth element of the list.
Example: |
| > (fifth '(1 2 3 4 5 6 7 8 9 10)) | 5 |
|
Returns the sixth element of the list.
Example: |
| > (sixth '(1 2 3 4 5 6 7 8 9 10)) | 6 |
|
Returns the seventh element of the list.
Example: |
| > (seventh '(1 2 3 4 5 6 7 8 9 10)) | 7 |
|
Returns the eighth element of the list.
Example: |
| > (eighth '(1 2 3 4 5 6 7 8 9 10)) | 8 |
|
Returns the ninth element of the list.
Example: |
| > (ninth '(1 2 3 4 5 6 7 8 9 10)) | 9 |
|
Returns the tenth element of the list.
Example: |
| > (tenth '(1 2 3 4 5 6 7 8 9 10)) | 10 |
|
Returns the last element of the list.
Example: |
| > (last '(1 2 3 4 5 6 7 8 9 10)) | 10 |
|
Returns the last pair of a (possibly improper) list.
Returns a newly constructed list of length k, holding
v in all positions.
Example: |
| > (make-list 7 'foo) | '(foo foo foo foo foo foo foo) |
|
Returns a fresh list whose elements are the first
pos elements of
lst. If
lst has fewer than
pos elements, the
exn:fail:contract exception is raised.
The lst argument need not actually be a list; lst
must merely start with a chain of at least pos pairs.
Examples: |
| > (take '(1 2 3 4) 2) | '(1 2) | | > (take 'non-list 0) | '() |
|
Returns the same result as
(values (take lst pos) (drop lst pos))
except that it can be faster.
Returns the
list’s
pos-length tail. If
lst
has fewer than
pos elements, then the
exn:fail:contract exception is raised.
The lst argument need not actually be a list; lst
must merely end with a chain of at least pos pairs.
Returns a fresh list whose elements are the prefix of
lst,
dropping its
pos-length tail. If
lst has fewer than
pos elements, then the
exn:fail:contract exception is raised.
The lst argument need not actually be a list; lst
must merely end with a chain of at least pos pairs.
Returns the same result as
(values (drop-right lst pos) (take-right lst pos))
except that it can be faster.
Returns a list with the same elements as lst, but with
v between each pair of items in lst.
Examples: |
| > (append* '(a) '(b) '((c) (d))) | '(a b c d) | | '("Alpha" ", " "Beta" ", " "Gamma") |
|
Flattens an arbitrary S-expression structure of pairs into a
list. More precisely,
v is treated as a binary tree where
pairs are interior nodes, and the resulting list contains all of the
non-
null leaves of the tree in the same order as an inorder
traversal.
Returns a list that has all items in lst, but without
duplicate items, where same? determines whether two elements
of the list are equivalent. The resulting list is in the same order
as lst, and for any item that occurs multiple times, the
first one is kept.
The #:key argument extract-key is used to extract a
key value from each list element, so two items are considered equal if
(same? (extract-key x) (extract-key y)) is true.
Returns
(filter (lambda (x) x) (map proc lst ...)), but
without building the intermediate list.
Returns
(length (filter proc lst ...)), but without building
the intermediate list.
Similar to
filter, except that two values are returned: the
items for which
pred returns a true value, and the items for
which
pred returns
#f.
The result is the same as
(values (filter pred lst) (filter (negate pred) lst))
but pred is applied to each item in lst only once.
Like
filter, but the meaning of the
pred predicate
is reversed: the result is a list of all items for which
pred
returns
#f.
Returns a list with all elements from lst, randomly shuffled.
Example: |
| > (shuffle '(1 2 3 4 5 6)) | '(5 1 2 6 3 4) |
|
Returns the first element in the list lst that minimizes
the result of proc. Signals an error on an empty list.
Examples: |
| > (argmin car '((3 pears) (1 banana) (2 apples))) | '(1 banana) | | > (argmin car '((1 banana) (1 orange))) | '(1 banana) |
|
Returns the first element in the list lst that maximizes
the result of proc. Signals an error on an empty list.
Examples: |
| > (argmax car '((3 pears) (1 banana) (2 apples))) | '(3 pears) | | > (argmax car '((3 pears) (3 oranges))) | '(3 pears) |
|
3.9.8 Immutable Cyclic Data
Returns a value like
v, with placeholders created by
make-placeholder replaced with the values that they contain,
and with placeholders created by
make-hash-placeholder
with an immutable hash table. No part of
v is mutated;
instead, parts of
v are copied as necessary to construct
the resulting graph, where at most one copy is created for any given
value.
Since the copied values can be immutable, and since the copy is also
immutable, make-reader-graph can create cycles involving only
immutable pairs, vectors, boxes, and hash tables.
Only the following kinds of values are copied and traversed to detect
placeholders:
Due to these restrictions, make-reader-graph creates exactly
the same sort of cyclic values as read.
Changes the value of ph to v.
Returns the value of ph.