Next: , Previous: , Up: lists   [Index]

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

Next: , Previous: , Up: lists   [Index]