Next: srfi list spec delete, Previous: srfi list spec filter, Up: srfi list spec [Index]
The following procedures all search lists for a leftmost element 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:
The standard, canonical behavior happens in this case.
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.
However, this SRFI does not specify anything at all about the behavior of these procedures when passed a dotted list 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 SRFI’s may refine SRFI-1 to define specific behavior in this case.
In brief, SRFI-1 compliant code may not pass a dotted list argument to these procedures.
It is an error to pass these procedures a circular list that does not contain an element satisfying the search criteria. Note that the procedure is not required to detect this case; it may 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.
Here are some examples, using the find and any procedures
as canonical representatives:
;; Proper list -- success (find even? '(1 2 3)) => 2 (any even? '(1 2 3)) => #t ;; proper list -- failure (find even? '(1 7 3)) => #f (any even? '(1 7 3)) => #f ;; Failure is error on a dotted list. (find even? '(1 3 . x)) => error (any even? '(1 3 . x)) => error ;; The dotted list contains an element satisfying the search. ;; This case is not specified -- it could be success, an error, ;; or some third possibility. (find even? '(1 2 . x)) => error/undefined (any even? '(1 2 . x)) => error/undefined ; success, error or other. ;; circular list -- success (find even? (circular-list 1 6 3)) => 6 (any even? (circular-list 1 6 3)) => #t ;; circular list -- failure is error. Procedure may diverge. (find even? (circular-list 1 3)) => error (any even? (circular-list 1 3)) => error
Return the first element of clist that satisfies predicate
pred; return #f if no element does.
(find even? '(3 1 4 1 5 9)) => 4
Note that find has an ambiguity in its lookup semantics: if
find 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 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, you should use
find-tail instead of find, find-tail has no such
ambiguity:
(cond [(find-tail pred lis) => (lambda (pair) ...)] ; Handle (CAR PAIR)
[else ...]) ; Search failed.
Return the first pair of clist 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 ;; MEMBER X LIS: (find-tail (lambda (elt) (equal? x elt)) lis)
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.
Return the longest initial prefix of clist whose elements all satisfy the predicate pred.
take-while! is the linear–update variant. It is allowed, but
not required, to alter the argument list to produce the result.
Example:
(take-while even? '(2 18 3 10 22 9)) => (2 18)
Drops the longest initial prefix of clist whose elements all satisfy the predicate pred, and returns the rest of the list.
Example:
(drop-while even? '(2 18 3 10 22 9)) => (3 10 22 9)
The circular–list case may be viewed as “rotating” the list.
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 the linear–update variants. They
are allowed, but not required, to alter the argument list to produce the
result.
Examples:
(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)
Apply the predicate across the lists, returning true if the predicate returns true on any application.
If there are n list arguments clist1 ... clistn, then pred must be a procedure taking n arguments and returning a boolean result.
any applies pred to the first elements of the clisti
parameters. If this application returns a true value, any
immediately returns that value. Otherwise, it iterates, applying pred
to the second elements of the clisti parameters, then the third,
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.
Like every, any’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.
Examples:
(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
Apply the predicate across the lists, returning true if the predicate returns true on every application.
If there are n list arguments clist1 ... clistn, then pred must be a procedure taking n arguments and returning a boolean result.
every applies pred to the first elements of the
clisti parameters. If this application returns #f,
every immediately returns #f. Otherwise, it iterates,
applying pred to the second elements of the clisti
parameters, then the third, 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 clisti has no elements, every simply returns
#t.
Like any, every’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.
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.
list-index applies pred to the first elements of the
clisti parameters. If this application returns true,
list-index immediately returns zero. Otherwise, it iterates,
applying pred to the second elements of the clisti
parameters, then the third, 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.
Examples:
(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
R5RS+ These procedures return the first sublist of list whose
car is x, where the sublists of list are the non–empty lists
returned by (drop list i) for i less than the length of
list. If x does not occur in list, then #f is
returned.
memq uses eq? to compare x with the elements of
list, while memv uses eqv?, and member uses
equal?.
Examples:
(memq 'a '(a b c)) => (a b c)
(memq 'b '(a b c)) => (b c)
(memq 'a '(b c d)) => #f
(memq (list 'a) '(b (a) c)) => #f
(member (list 'a)
'(b (a) c)) => ((a) c)
(memq 101 '(100 101 102)) => *unspecified*
(memv 101 '(100 101 102)) => (101 102)
member is extended from its R5RS definition to allow the
client to pass in an optional equality procedure = used to compare
keys.
The comparison procedure is used to compare the elements ei of list to the key x in this way:
(= x ei) ; list is (E1 ... En)
that is, the first argument is always x, 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 list <).
Note that fully general list searching may be performed with the
find-tail and find procedures:
(find-tail even? list) ; Find the first elt with an even key.
Next: srfi list spec delete, Previous: srfi list spec filter, Up: srfi list spec [Index]