3.9 Pairs and Lists

Pairs and Lists in Guide: PLT Scheme 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

(pair? v) → boolean?

v : any/c

Returns #t if v is a pair, #f otherwise.

(null? v) → boolean?

v : any/c

Returns #t if v is the empty list, #f otherwise.

(cons a d) → pair?

a : any/c

d : any/c

Returns a pair whose first element is a and second element is d.

(car p) → any/c

p : pair?

Returns the first element of the pair p.

(cdr p) → any/c

p : pair?

Returns the second element of the pair p.

null : null?

The empty list.

(list? v) → boolean?

v : any/c

Returns #t if v is a list: either the empty list, or a pair whose second element is a list. This procedure takes amortized constant time.

(list v ...) → list?

v : any/c

Returns a newly allocated list containing the vs as its elements.

(list* v ... tail) → any/c

v : any/c

tail : any/c

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.

(build-list n proc) → list?

n : exact-nonnegative-integer?

proc : (exact-nonnegative-integer? . -> . any)

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).

Examples:

> (build-list 10 values)

(0 1 2 3 4 5 6 7 8 9)

> (build-list 5 (lambda (x) (* x x)))

(0 1 4 9 16)

3.9.2 List Operations

(length lst) → exact-nonnegative-integer?

lst : list?

Returns the number of elements in lst.

(list-ref lst pos) → any/c

lst : any/c

pos : exact-nonnegative-integer?

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.

(list-tail lst pos) → any/c

lst : any/c

pos : exact-nonnegative-integer?

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.

(append lst ...) → list?

lst : list?

(append lst ... v) → any/c

lst : list?

v : any/c

When given all list arguments, the result is a lists 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.”

(reverse lst) → list?

lst : list?

Returns a list that has the same elements as lst, but in reverse order.

3.9.3 List Iteration

(map proc lst ...+) → list?

proc : procedure?

lst : list?

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.

(andmap proc lst ...+) → any

proc : procedure?

lst : list?

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; or

• the result is that of proc applied to the last elements of the lstss; 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:

> (andmap positive? '(1 2 3))

#t

> (andmap positive? '(1 2 a))

positive?: expects argument of type <real number>; given a

> (andmap positive? '(1 -2 a))

#f

> (andmap + '(1 2 3) '(4 5 6))

9

(ormap proc lst ...+) → any

proc : procedure?

lst : list?

Similar to map, except that

• the result is #f if every application of proc produces #f; or

• the result of the first applciation of proc to produces a value other than #f, in which case proc is not applied to later 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 #f is returned.

Examples:

> (ormap eq? '(a b c) '(a b c))

#t

> (ormap positive? '(1 2 a))

#t

> (ormap + '(1 2 3) '(4 5 6))

5

(for-each proc lst ...+) → void?

proc : procedure?

lst : list?

Similar to map, but proc is called only for its effect, and its result (which can be any number of values) is ignored.

(foldl proc init lst ...+) → list?

proc : procedure?

init : any/c

lst : list?

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).

Examples:

> (foldl cons '() '(1 2 3 4))

(4 3 2 1)

> (foldl + 0 '(1 2 3 4))

10

(foldr proc init lst ...+) → list?

proc : procedure?

init : any/c

lst : list?

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).

Examples:

> (foldr cons '() '(1 2 3 4))

(1 2 3 4)

> (foldr (lambda (v l) (cons (add1 v) l)) '() '(1 2 3 4))

(2 3 4 5)

3.9.4 List Filtering

(filter pred lst) → list?

pred : procedure?

lst : list?

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.

(remove v lst [proc]) → list?

v : any/c

lst : list?

proc : procedure? = equal?

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).

(remq v lst) → list?

v : any/c

lst : list?

Returns (remove v lst eq?).

(remv v lst) → list?

v : any/c

lst : list?

Returns (remove v lst eqv?).

(remove* v-lst lst [proc]) → list?

v-lst : list?

lst : list?

proc : procedure? = equal?

Like remove, but removes from lst every instance of every element of v-lst.

(remq* v-lst lst) → list?

v-lst : list?

lst : list?

Returns (remove* v-lst lst eq?).

(remv* v-lst lst) → list?

v-lst : list?

lst : list?

Returns (remove* v-lst lst eqv?).

(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

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 than (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")

> (sort '(("aardvark") ("dingo") ("cow") ("bear"))           #:key car string<?)

(("aardvark") ("bear") ("cow") ("dingo"))

3.9.5 List Searching

(member v lst) → (or/c list? false/c)

v : any/c

lst : list?

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.

(memv v lst) → (or/c list? false/c)

v : any/c

lst : list?

Like member, but finds an element using eqv?.

(memq v lst) → (or/c list? false/c)

v : any/c

lst : list?

Like member, but finds an element using eq?.

(memf proc lst) → (or/c list? false/c)

proc : procedure?

lst : list?

Like member, but finds an element using the predicate proc; an element is found when proc applied to the element returns a true value.

(findf proc lst) → any/c

proc : procedure?

lst : list?

Like memf, but returns the element or #f instead of a tail of lst or #f.

(assoc v lst) → (or/c pair? false/c)

v : any/c

lst : (listof