3.9 Pairs and Lists
Pairs and Lists in The Racket Guide 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.
See Reading Pairs and Lists for information on reading pairs and lists and Printing Pairs and Lists for information on printing pairs and lists.
3.9.1 Pair Constructors and Selectors
Examples: | ||||||
|
procedure
(build-list n proc) → list?
n : exact-nonnegative-integer? proc : (exact-nonnegative-integer? . -> . any)
Examples: | ||||
|
3.9.2 List Operations
procedure
(length lst) → exact-nonnegative-integer?
lst : list?
procedure
lst : pair? pos : exact-nonnegative-integer?
The lst argument need not actually be a list; lst must merely start with a chain of at least (add1 pos) pairs.
Examples: | ||||||||
|
procedure
lst : any/c pos : exact-nonnegative-integer?
Examples: | |||||||||||||
|
The last argument need not be a list, in which case the result is an “improper list.”
Examples: | ||||
|
Example: | ||
|
3.9.3 List Iteration
procedure
proc : procedure? lst : list?
Examples: | |||||||||||
|
procedure
proc : procedure? lst : list?
The andmap function is actually closer to foldl than map, since andmap doesn’t produce a list. Still, (andmap f (list x y z)) is equivalent to (and (f x) (f y) (f z)) in the same way that (map f (list x y z)) is equivalent to (list (f x) (f y) (f z)).
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.
Examples: | ||||||||||
|
procedure
proc : procedure? lst : list?
To continue the andmap note above, (ormap f (list x y z)) is equivalent to (or (f x) (f y) (f z)).
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.
Examples: | ||||||
|
procedure
proc : procedure? lst : list?
Example: | ||||||||||||
|
procedure
proc : procedure? init : any/c lst : list?
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).
Examples: | |||||||||||
|
procedure
proc : procedure? init : any/c lst : list?
Examples: | ||||
|
3.9.4 List Filtering
procedure
pred : procedure? lst : list?
Example: | ||
|
Examples: | ||||||||||
|
Examples: | ||||||||
|
Examples: | ||||||||
|
Example: | ||
|
procedure
(sort lst less-than? [ #:key extract-key #:cache-keys? cache-keys?]) → list? lst : list? less-than? : (any/c any/c . -> . any/c) extract-key : (any/c . -> . any/c) = (lambda (x) x) cache-keys? : boolean? = #f
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: | ||||||||
|
3.9.5 List Searching
Examples: | ||||
|
Examples: | ||||
|
procedure
proc : procedure? lst : list?
Example: | |||||
|
procedure
proc : procedure? lst : list?
Examples: | |||||||||
|
procedure
proc : procedure? lst : list?
3.9.6 Pair Accessor Shorthands
Example: | ||
|
Example: | ||
|
Example: | ||
|
Example: | ||
|
Example: | ||
|
Example: | ||
|
Example: | ||
|
Example: | ||
|
Example: | ||
|
Example: | ||
|
Example: | ||
|
Example: | ||
|
Example: | ||
|
Example: | ||
|
Example: | ||
|
Example: | ||
|
Example: | ||
|
Example: | ||
|
Example: | ||
|
Example: | ||
|
Example: | ||
|
Example: | ||
|
Example: | ||
|
Example: | ||
|
Example: | ||
|
Example: | ||
|
Example: | ||
|
Example: | ||
|
3.9.7 Additional List Functions and Synonyms
Example: | ||
|
Example: | ||
|
Example: | ||
|
Example: | ||
|
Example: | ||
|
Example: | ||
|
Example: | ||
|
Example: | ||
|
Example: | ||
|
Example: | ||
|
Example: | ||
|
Example: | ||
|
Example: | ||
|
Example: | ||
|
procedure
k : exact-nonnegative-integer? v : any?
Example: | ||
|
procedure
lst : any/c pos : exact-nonnegative-integer?
The lst argument need not actually be a list; lst must merely start with a chain of at least pos pairs.
Examples: | ||||
|
procedure
lst : any/c pos : exact-nonnegative-integer?
procedure
(split-at lst pos) →
list? any/c lst : any/c pos : exact-nonnegative-integer?
except that it can be faster.
procedure
(take-right lst pos) → any/c
lst : any/c pos : exact-nonnegative-integer?
The lst argument need not actually be a list; lst must merely end with a chain of at least pos pairs.
Examples: | ||||
|
procedure
(drop-right lst pos) → list?
lst : any/c pos : exact-nonnegative-integer?
The lst argument need not actually be a list; lst must merely end with a chain of at least pos pairs.
Examples: | ||||
|
procedure
(split-at-right lst pos) →
list? any/c lst : any/c pos : exact-nonnegative-integer?
(values (drop-right lst pos) (take-right lst pos))
except that it can be faster.
Examples: | ||||||||
|
procedure
(add-between lst v [ #:before-first before-first #:before-last before-last #:after-last after-last #:splice? splice?]) → list? lst : list? v : any/c before-first : list? = '() before-last : any/c = v after-last : list? = '() splice? : any/c = #f
If splice? is true, then v and before-last should be lists, and the list elements are spliced into the result. In addition, when splice? is true, before-first and after-last are inserted before the first element and after the last element respectively.
Examples: | |||||||||||
|
Examples: | ||||||
|
Examples: | ||||
|
procedure
(remove-duplicates lst [ same? #:key extract-key]) → list? lst : list? same? : (any/c any/c . -> . any/c) = equal? extract-key : (any/c . -> . any/c) = (lambda (x) x)
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.
Examples: | ||||||
|
procedure
(filter-map proc lst ...+) → list?
proc : procedure? lst : list?
Example: | ||
|
procedure
(count proc lst ...+) → exact-nonnegative-integer?
proc : procedure? lst : list?
Example: | ||
|
procedure
(partition pred lst) →
list? list? pred : procedure? lst : list?
The result is the same as
but pred is applied to each item in lst only once.
Example: | ||||
|
procedure
(append-map proc lst ...+) → list?
proc : procedure? lst : list?
Example: | ||
|
Example: | ||
|
Example: | ||
|
Examples: | ||||
|
Examples: | ||||
|
Examples: | ||||||||||
|
3.9.8 Immutable Cyclic Data
procedure
(make-reader-graph v) → any/c
v : any/c
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:
pairs
vectors, both mutable and immutable
boxes, both mutable and immutable
hash tables, both mutable and immutable
instances of a prefab structure type
placeholders created by make-placeholder and make-hash-placeholder
Due to these restrictions, make-reader-graph creates exactly the same sort of cyclic values as read.
Example: | ||||||
|
procedure
(placeholder? v) → boolean?
v : any/c
procedure
(make-placeholder v) → placeholder?
v : any/c
procedure
(placeholder-set! ph datum) → void?
ph : placeholder? datum : any/c
procedure
(placeholder-get ph) → any/c
ph : placeholder?
procedure
(hash-placeholder? v) → boolean?
v : any/c
procedure
(make-hash-placeholder assocs) → hash-placeholder?
assocs : (listof pair?)
procedure
(make-hasheq-placeholder assocs) → hash-placeholder?
assocs : (listof pair?)
procedure
(make-hasheqv-placeholder assocs) → hash-placeholder?
assocs : (listof pair?)