23.10 Searching

The following procedures search lists for the leftmost elements satisfying some criteria; this means they do not always examine the entire list; thus, there is no efficient way for them to reliably detect and signal an error when passed a dotted or circular list. Here are the general rules describing how these procedures work when applied to different kinds of lists:

Proper lists

The standard, canonical behavior happens in this case.

Dotted lists

It is an error to pass these procedures a dotted list that does not contain an element satisfying the search criteria. That is, it is an error if the procedure has to search all the way to the end of the dotted list. In this case the result is undefined.

Circular lists

It is an error to pass these procedures a circular list that does not contain an element satisfying the search criteria. Note that the procedures do not detect this case, they will simply diverge. It is, however, acceptable to search a circular list if the search is successful; that is, if the list contains an element satisfying the search criteria.

Function: take-while pred circ

Function: take-while! pred circ

Return the longest initial prefix of circ whose elements all satisfy pred. take-while! is allowed to alter the argument list to produce the result.

(take-while even? '(2 18 3 10 22 9))
⇒ (2 18)

Function: drop-while pred circ

Drop the longest initial prefix of circ whose elements all satisfy pred and return the rest of the list.

(drop-while even? '(2 18 3 10 22 9))
⇒ (3 10 22 9)

The circular–list case may be viewed as “rotating” the list.

Function: span pred circ

Function: span! pred ell

Function: break pred circ

Function: break! pred ell

span splits the list into the longest initial prefix whose elements all satisfy pred and the remaining tail. break inverts the sense of the predicate: The tail commences with the first element of the input list that satisfies the predicate.

In other words: span finds the intial span of elements satisfying pred, and break breaks the list at the first element satisfying pred.

span is equivalent to:

(values (take-while pred clist)
        (drop-while pred clist))

span! and break! are allowed to alter the argument list to produce the result.

(span even? '(2 18 3 10 22 9))
⇒ (2 18) (3 10 22 9)

(break even? '(3 1 4 1 5 9))
⇒ (3 1) (4 1 5 9)

Function: any pred ell0 ell ...

Function: any* pred circ0 circ ...

Apply the predicate across the lists, returning true if the predicate returns true on any application. If there are N list arguments, then pred must be a procedure taking N arguments and returning a boolean result. If all the list arguments are empty: The return value is #f.

The list arguments of any must have the same length; any* accepts lists of different length.

any applies pred to the first elements of the list arguments, if this application return true, any immediately returns that value; otherwise, it iterates, applying pred to the second elements of the lits arguments and so forth. The iteration stops when a true value is produced or one of the lists runs out of values; in the latter case, any returns #f. The application of pred to the last element of the lists is a tail call.

Note the difference between find and any: find returns the element that satisfied the predicate; any returns the true value that the predicate produced.

The identifier any does not end with a question mark: This is to indicate that it does not return a simple boolean (#t or #f), but a general value.

(any integer? '(a 3 b 2.7))
⇒ #t

(any integer? '(a 3.1 b 2.7))
⇒ #f

(any < '(3 1 4 1 5)
       '(2 7 1 8 2))
⇒ #t

Function: every pred ell0 ell ...

Function: every* pred circ0 circ ...

Apply the predicate across the lists, returning true if the predicate returns true on every application. If there are N list arguments, then pred must be a procedure taking N arguments and returning a boolean result. If all the list arguments are empty: The return value is #t.

The list arguments of every must have the same length; every* accepts lists of different length.

every applies pred to the first elements of the list arguments, if this application returns #f, every immediately returns #f; otherwise, it iterates, applying pred to the second elements of the list arguments and so forth. The iteration stops when a #f value is produced or one of the lists runs out of values. In the latter case, every returns the true value produced by its final application of pred. The application of pred to the last element of the lists is a tail call.

If one of the list arguments has no elements, every simply returns #t.

The identifier every does not end with a question mark: This is to indicate that it does not return a simple boolean (#t or #f), but a general value.

Function: list-index pred ell0 ell ...

Function: list-index* pred circ0 circ ...

Return the index of the leftmost element that satisfies pred. If there are N list arguments, then pred must be a function taking N arguments and returning a boolean result.

The list arguments of list-index must have the same length; list-index* accepts lists of different length.

list-index applies pred to the first elements of the list arguments, if this application returns true, list-index immediately returns zero; otherwise, it iterates, applying pred to the second elements of the list arguments and so forth. When it finds a tuple of list elements that cause pred to return true, it stops and returns the zero–based index of that position in the lists.

The iteration stops when one of the lists runs out of values; in this case, list-index returns #f.

(list-index even? '(3 1 4 1 5 9))
⇒ 2

(list-index < '(3 1 4 1 5 9 2 5 6) '(2 7 1 8 2))
⇒ 1

(list-index = '(3 1 4 1 5 9 2 5 6) '(2 7 1 8 2))
⇒ #f

Function: position obj ell

Function: position/stx obj ell

Return the index of the leftmost obj in ell. If obj is not present in ell, return #f.

Function: member* obj ell

Function: member* obj ell item=

Return the first sublist of ell whose car is obj, where the sublists of ell are the non–empty lists returned by (drop ell i) for i less than the length of ell. If obj does not occur in ell, then #f is returned.

Examples:

(member* '(a) '(b (a) c))
⇒ ((a) c)

member* extends the R6RS definition of member to allow the client to pass in an optional equality procedure item= used to compare keys. item= defaults to equal?.

The comparison procedure is used to compare the elements Ei of list to the key obj in this way:

(= x ei) ; list is (E1 ... En)

that is, the first argument is always obj, and the second argument is one of the list elements. Thus one can reliably find the first element of list that is greater than five with:

(member* 5 ell <)

Note that fully general list searching may be performed with the find-tail and find procedures.

Function: find-tail pred circ

Return the first pair of circ whose car satisfies pred. If no pair does, return #f. find-tail can be viewed as a general–predicate variant of the member* function.

Examples:

(find-tail even? '(3 1 37 -8 -5 0 0))
⇒ (-8 -5 0 0)

(find-tail even? '(3 1 37 -5))
⇒ #f

In the circular–list case, this procedure “rotates” the list.

find-tail is essentially drop-while, where the sense of the predicate is inverted: find-tail searches until it finds an element satisfying the predicate; drop-while searches until it finds an element that doesn’t satisfy the predicate.

NOTE The find function defined by R6RS has an ambiguity in its lookup semantics: if find returns #f, we cannot tell (in general) if it found a #f element that satisfied pred, or if it did not find any element at all.

In many situations, this ambiguity cannot arise: either the list being searched is known not to contain any #f elements, or the list is guaranteed to have an element satisfying pred.

However, in cases where this ambiguity can arise, we should use find-tail instead of find, find-tail has no such ambiguity.