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

Examples:

> (list? '(1 2))

#t

> (list? (cons 1 (cons 2 '())))

#t

> (list? (cons 1 2))

#f

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

The last argument need not be a list, in which case the result is an “improper list.”

Examples:

> (append (list 1 2) (list 3 4))

'(1 2 3 4)

> (append (list 1 2) (list 3 4) (list 5 6) (list 7 8))

'(1 2 3 4 5 6 7 8)

Example:

> (reverse (list 1 2 3 4))

'(4 3 2 1)

3.9.3 List Iteration

Examples:

> (map (lambda (number)            (+ 1 number))          '(1 2 3 4))

'(2 3 4 5)

> (map (lambda (number1 number2)            (+ number1 number2))          '(1 2 3 4)          '(10 100 1000 10000))

'(11 102 1003 10004)

• 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:

> (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

• 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:

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

#t

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

#t

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

5

Example:

> (for-each (lambda (arg)                 (printf "Got ~a\n" arg)                 23)               '(1 2 3 4))

Got 1   Got 2   Got 3   Got 4

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

> (foldl (lambda (a b result)              (* result (- a b)))            1            '(1 2 3)            '(4 5 6))

-27

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

Example:

> (filter positive? '(1 -2 3 4 -5))

'(1 3 4)

Example:

> (remove 2 (list 1 2 3 2 4))

'(1 3 2 4)

Example:

> (remq* (list 1 2) (list 1 2 3 2 4 5 2))

'(3 4 5)

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

Examples:

> (member 2 (list 1 2 3 4))

'(2 3 4)

> (member 9 (list 1 2 3 4))

#f

Examples:

> (memq 2 (list 1 2 3 4))

'(2 3 4)

> (memq 9 (list 1 2 3 4))

#f

Example:

> (memf (lambda (arg)             (> arg 9))           '(7 8 9 10 11))

'(10 11)

3.9.6 Pair Accessor Shorthands