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

• memq
• memv
• member

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 #t or #f according to the result of some test. But predicate names by convention have a trailing question mark, which memq, memv and member do not have. This is not an inconsistency but rather indicates that the function does not return #t or #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.

Filtering Lists¶

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 filter or delete to a list

filter¶

(filter <predicate> <list>)

filter applies <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 #f.

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 car 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 equal?.

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

delete has its companion procedures delq and delv which use eq? and 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)