2.40.6.8 Searching

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

Proper ilists

The standard, canonical behavior happens in this case.

Dotted ilists

It is an error to pass these procedures a dotted ilist 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 ilist. However, this SRFI does not specify anything at all about the behavior of these procedures when passed a dotted ilist containing an element satisfying the search criteria. It may finish successfully, signal an error, or perform some third action. Different implementations may provide different functionality in this case; code which is compliant with this SRFI may not rely on any particular behavior. Future SRFIs may refine this SRFI to define specific behavior in this case.

In brief, compliant code may not pass a dotted ilist argument to these procedures.

Here are some examples, using the ifind and iany procedures as canonical representatives:

;; Proper ilist: success
(ifind even? (iq 1 2 3))	⇒ 2
(iany  even? (iq 1 2 3))	⇒ #t

;; proper ilist: failure
(ifind even? (iq 1 7 3))	⇒ #f
(iany  even? (iq 1 7 3))	⇒ #f

;; Failure is error on a dotted ilist.
(ifind even? (ipair (1 (ipair 3 x)))	error→ invalid argument
(iany  even? (ipair (1 (ipair 3 x)))	error→ invalid argument

;; The dotted ilist contains an element satisfying the search.
;; This case is not specified: it could be success, an error,
;; or some third possibility.
(ifind even? (ipair (1 (ipair 2 x)))
⇒ error/undefined
(iany  even? (ipair (1 (ipair 2 x))))
⇒ error/undefined ; success, error or other

Function: value ifind pred ilist

Return the first element of ilist that satisfies predicate pred; return #f if no element does.

(ifind even? (iq 3 1 4 1 5 9)) ⇒ 4

Note that ifind has an ambiguity in its lookup semantics: if ifind returns #f, you 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 ilist being searched is known not to contain any #f elements, or the ilist is guaranteed to have an element satisfying pred. However, in cases where this ambiguity can arise, you should use ifind-tail instead of ifind: ifind-tail has no such ambiguity:

(cond ((ifind-tail pred lis)
       => (lambda (ipair) ...)) ; Handle (icar ipair)
      (else ...))               ; Search failed

Function: value ifind-tail pred ilist

Return the first ipair of ilist whose icar satisfies pred. If no ipair does, return #f.

ifind-tail can be viewed as a general–predicate variant of the imember function.

Examples:

(ifind-tail even? (iq 3 1 37 -8 -5 0 0)) ⇒ (-8 -5 0 0)
(ifind-tail even? (iq 3 1 37 -5))        ⇒ #f

;; IMEMBER X LIS:
(ifind-tail (lambda (elt) (equal? x elt)) lis)

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

Function: ilist itake-while pred ilist

Return the longest initial prefix of ilist whose elements all satisfy the predicate pred.

(itake-while even? (iq 2 18 3 10 22 9)) ⇒ (2 18)

Function: ilist idrop-while pred ilist

Drop the longest initial prefix of ilist whose elements all satisfy the predicate pred, and returns the rest of the ilist.

(idrop-while even? (iq 2 18 3 10 22 9)) ⇒ (3 10 22 9)

Function: ilist ilist ispan pred ilist

Function: ilist ilist ibreak pred ilist

ispan splits the ilist into the longest initial prefix whose elements all satisfy pred, and the remaining tail. ibreak inverts the sense of the predicate: the tail commences with the first element of the input ilist that satisfies the predicate.

In other words: ispan finds the initial span of elements satisfying pred, and ibreak breaks the ilist at the first element satisfying pred.

ispan is equivalent to.

(values (itake-while pred ilist)
        (idrop-while pred ilist))

(ispan even? (iq 2 18 3 10 22 9))
⇒ (2 18) (3 10 22 9)

(ibreak even? (iq 3 1 4 1 5 9))
⇒ (3 1) (4 1 5 9)

Function: value iany pred ilist1 ilist2 …

Applies the predicate across the ilists, returning true if the predicate returns true on any application.

If there are n ilist arguments: then pred must be a procedure taking n arguments and returning a boolean result.

iany applies pred to the first elements of the ilist parameters. If this application returns a true value, iany immediately returns that value. Otherwise, it iterates, applying pred to the second elements of the ilist parameters, then the third, and so forth. The iteration stops when a true value is produced or one of the ilists runs out of values; in the latter case, iany returns #f. The application of pred to the last element of the ilists is a tail call.

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

Like ievery, iany’s name 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.

(iany integer? (iq a 3 b 2.7))   ⇒ #t
(iany integer? (iq a 3.1 b 2.7)) ⇒ #f
(iany < (iq 3 1 4 1 5)
        (iq 2 7 1 8 2))
⇒ #t

Function: value ievery pred ilist1 ilist2 …

Applies the predicate across the ilists, returning true if the predicate returns true on every application.

If there are n ilist arguments: pred must be a procedure taking n arguments and returning a boolean result.

ievery applies pred to the first elements of the ilist parameters. If this application returns #f: ievery immediately returns #f. Otherwise, it iterates, applying pred to the second elements of the ilist parameters, then the third, and so forth. The iteration stops when a #f value is produced or one of the ilists runs out of values. In the latter case, ievery returns the true value produced by its final application of pred. The application of pred to the last element of the ilists is a tail call.

If one of the ilist has no elements: ievery simply returns #f.

Like iany, ievery’s name 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: value ilist-index pred ilist1 ilist2 …

Return the index of the leftmost element that satisfies pred.

If there are n ilist arguments: pred must be a function taking n arguments and returning a boolean result.

ilist-index applies pred to the first elements of the ilist parameters. If this application returns true, ilist-index immediately returns zero; otherwise, it iterates, applying pred to the second elements of the ilisti parameters, then the third, and so forth. When it finds a tuple of ilist elements that cause pred to return true, it stops and returns the zero–based index of that position in the ilists.

The iteration stops when one of the ilists runs out of values; in this case: ilist-index returns #f.

(ilist-index even? (iq 3 1 4 1 5 9)) ⇒ 2
(ilist-index < (iq 3 1 4 1 5 9 2 5 6) (iq 2 7 1 8 2)) ⇒ 1
(ilist-index = (iq 3 1 4 1 5 9 2 5 6) (iq 2 7 1 8 2)) ⇒ #f

Function: ilist imember x ilist

Function: ilist imember x ilist =

Function: ilist imemq x ilist

Function: ilist imemv x ilist

These procedures return the first sub–ilist of ilist whose icar is x, where the sub–ilists of ilist are the non–empty ilists returned by (idrop ilist i) for i less than the length of ilist. If x does not occur in ilist: #f is returned. imemq uses eq? to compare x with the elements of ilist, while imemv uses eqv?, and imember uses equal?.

(imemq 'a (iq a b c))           ⇒  (a b c)
(imemq 'b (iq a b c))           ⇒  (b c)
(imemq 'a (iq b c d))           ⇒  #f
(imemq (ilist 'a) (iq b (a) c)) ⇒  #f
(imember (ilist 'a)
         (iq b (a) c))          ⇒  ((a) c)
(imemq 101 (iq 100 101 102))    ⇒  *unspecified*
(imemv 101 (iq 100 101 102))    ⇒  (101 102)

The comparison procedure is used to compare the elements ei of ilist to the key x in this way:

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

that is, the first argument is always x, and the second argument is one of the ilist elements. Thus one can reliably find the first element of ilist that is greater than five with (imember 5 ilist <).

Note that fully general ilist searching may be performed with the ifind-tail and ifind procedures, e.g.

(ifind-tail even? ilist) ; Find the first elt with an even key.