Searching and Filtering Lists¶
Often it is necessary to choose elements from list based on certain criteria, or in other words: to search and filter lists. As lists are the core of Scheme as a LISP language there are of course readily available tools for that purpose.
Searching for Elements in a List¶
To determine if an element is present in a list Scheme provides the triple
each representing one of the three equality modes. The functions are called as
(<function> <element> <list>) e.g. (memv 3 '(1 2 3 4 5))
Colloquially you could translate this into “check if
3 is a member of the list
'(1 2 3 4 5)” - which it is -, but actually the function works somewhat differently. From the introduction to data types you may recall that for that type of question one uses predicates, procedures that return
#f according to the result of some test. But predicate names by convention have a trailing question mark, which
member do not have. This is not an inconsistency but rather indicates that the function does not return
#f. Instead it returns the remainder of the list, starting with the first matched element, or
#f if the element is not found in the list. The result of the above example would therefore be the list
(3 4 5).
The fact that
member and friends return either
#f or a “true value” can be exploited to create elegant solutions in conditionals.
Sometimes it is necessary to produce a list resulting of all elements in a given list that match (or do not match) given criteria. This can be achieved through applying
delete to a list
(filter <predicate> <list>)
<predicate> to each element of
<list> and creates a new list consisting of each element satisfying the predicate.
<predicate> can be any procedure taking exactly one argument and returning a value. The predicate is “satisfied” whenever it returns a “true” value, that is anything except
I will make this clearer through an example. The easiest case is applying a type predicate, keeping all elements that match a certain type:
guile> (filter number? '(1 2 "d" 'e 4 '(2 . 3) 5)) (1 2 4 5)
In this case
filter applies the predicate
number? to each element of the list
'(1 2 "d" 'e 4 '(2 . 3) 5) and constructs the resulting list from all numbers in this list. Note that the pair
'(2 . 3) is not a number although it consists of only numbers.
In this basic form
filter is somewhat limited because it can only be used with procedures accepting a single argument, i.e. “predicates”. Although there are other procedures that match this requirement it is rarely useful to use them in a
filter expression. When interested in things like “all list elements that are numbers greater than 7” or “all list elements are pairs of numbers where the
cdr is greater than the
cdr” you will want to use custom procedures, which you'll learn to write in Defining Procedures.
delete and delete-duplicates¶
delete is somewhat like the opposite of
filter in so far as it returns a copy of a list with all elements that do not match the given criteria. The difference is that the match is not determined through a predicate but by comparing the elements with
guile>(delete 3 '(1 2 3 4 5 4 3 2)) (1 2 4 5 4 2)
The resulting list is the original list with all elements deleted that are “equal” to
delete has its companion procedures
delv which use
eqv? as comparison predicate.
A related procedure is
delete-duplicates, which returns a copy of the original list, stripped off any duplicate elements. The comparison is performed using
equal?, so for example strings with the same content are deleted as well:
guile> (delete-duplicates '("a" 2 3 "a" b 3)) ("a" 2 3 b)