Chapter 23

list.ss: List Utilities

To load: (require (lib "list.ss"))

The procedures second, third, fourth, fifth, sixth, seventh, and eighth access the corresponding element from a list.

(assf f l)      PROCEDURE

Applies f to the car of each element of l (from left to right) until f returns a true value, in which case that element is returned. If f does not return a true value for the car of any element of l, #f is returned.

(cons? v)      PROCEDURE

Returns #t if v is a value created with cons, #f otherwise.

empty      EMPTY LIST

The empty list.

(empty? v)      PROCEDURE

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

(filter f l)      PROCEDURE

Applies f to each element in l (from left to right) and returns a new list that is the same as l, but omitting all the elements for which f returned #f.

(findf f l)      PROCEDURE

Applies f to each element of l (from left to right) until f returns a true value for some element, in which case that element is returned. If f does not return a true value for any element of l, #f is returned.

(first l)      PROCEDURE

Returns the first element of the list l. (The first procedure is a synonym for car.)

(foldl f init l ···¹)      PROCEDURE

Like map, foldl applies a procedure f to the elements of one or more lists. While map combines the return values into a list, foldl combines the return values in an arbitrary way that is determined by f. Unlike foldr, foldl processes l in constant space (plus the space for each call to f).

If foldl is called with n lists, the f procedure takes n+1 arguments. The extra value is the combined return values so far. The f procedure is initially invoked with the first item of each list; the final argument is init. In subsequent invocations of f, the last argument is the return value from the previous invocation of f. The input lists are traversed from left to right, and the result of the whole foldl application is the result of the last application of f. (If the lists are empty, the result is init.)

For example, reverse can be defined in terms of foldl:

  (define reverse
    (lambda (l)
      (foldl cons '() l)))

(foldr f init l ···¹)      PROCEDURE

Like foldl, but the lists are traversed from right to left. Unlike foldl, foldr processes l in space proportional to the length of l (plus the space for each call to f).

For example, a restricted map (that works only on single-argument procedures) can be defined in terms of foldr:

  (define simple-map
    (lambda (f list)
      (foldr (lambda (v l) (cons (f v) l)) '() list)))

(last-pair list)      PROCEDURE

Returns the last pair in list, raising an error if list is not a pair (but list does not have to be a proper list).

(memf f l)      PROCEDURE

Applies f to each element of l (from left to right) until f returns a true value for some element, in which case the tail of l starting with that element is returned. If f does not return a true value for any element of l, #f is returned.

(sort list less-than?)      PROCEDURE

Sorts list using the comparison procedure less-than?. This implementation is stable (i.e., if two elements in the input are ``equal,'' their relative positions in the output will be the same).

(sort! list less-than?)      PROCEDURE

The destructive version of sort. (Actually, sort is implemented by copying the list and using sort! on the copy.)

(merge-sorted-lists! list1 list2 less-than?)      PROCEDURE

Merges the two sorted input lists by modifying cdr fields, to create a single sorted output list. The merged result is stable: equal items in both lists stay in the same order, and these in list1 precede list2. This is used by sort!, but is also useful by itself.

(merge-sorted-lists list1 list2 less-than?)      PROCEDURE

The non-destructive version of merge-sorted-lists!.

(mergesort list less-than?)      PROCEDURE

Deprecated: use sort instead.

This is a different name for sort, provided for backward compatibility.

(quicksort list less-than?)      PROCEDURE

Deprecated: use sort instead.

Sorts list using the comparison procedure less-than?. This implementation is not stable (i.e., if two elements in the input are ``equal,'' their relative positions in the output may be reversed). Kept for backward compatibility, it is slower than sort above.

(remove item list [equal?])      PROCEDURE

Returns list without the first instance of item, where an instance is found by comparing item to the list items using equal?. The default value for equal? is equal?. When equal? is invoked, item is the first argument.

(remove* items list [equal?])      PROCEDURE

Like remove, except that the first argument is a list of items to remove instead of a single item, and all instances of these items are removed rather than just the first.

(remq item list)      PROCEDURE

Calls remove with eq? as the comparison procedure.

(remq* items list)      PROCEDURE

Calls remove* with eq? as the comparison procedure.

(remv item list)      PROCEDURE

Calls remove with eqv? as the comparison procedure.

(remv* items list)      PROCEDURE

Calls remove* with eqv? as the comparison procedure.

(rest l)      PROCEDURE

Returns a list that contains all but the first element of the non-empty list l. (The rest procedure is a synonym for cdr.)

(set-first! l v)      PROCEDURE

Destructively modifies l so that its first element is v. (The set-first! procedure is a synonym for set-car!.)

(set-rest! l1 l2)      PROCEDURE

Destructively modifies l1 so that the rest of the list (after the first element) is l2. (The set-rest! procedure is a synonym for set-cdr!.)