What is the Scheme function to find an element in a list?

Question

I have a list of elements '(a b c) and I want to find if (true or false) x is in it, where x can be 'a or 'd, for instance. Is there a built in function for this?

Solution 1

If you need to compare using one of the build in equivalence operators, you can use memq, memv, or member, depending on whether you want to look for equality using eq?, eqv?, or equal?, respectively.

> (memq 'a '(a b c))
'(a b c)
> (memq 'b '(a b c))
'(b c)
> (memq 'x '(a b c))
#f

As you can see, these functions return the sublist starting at the first matching element if they find an element. This is because if you are searching a list that may contain booleans, you need to be able to distinguish the case of finding a #f from the case of not finding the element you are looking for. A list is a true value (the only false value in Scheme is #f) so you can use the result of memq, memv, or member in any context expecting a boolean, such as an if, cond, and, or or expression.

> (if (memq 'a '(a b c))
     "It's there! :)"
     "It's not... :(")
"It's there! :)"

What is the difference between the three different functions? It's based on which equivalence function they use for comparison. eq? (and thus memq) tests if two objects are the same underlying object; it is basically equivalent to a pointer comparison (or direct value comparison in the case of integers). Thus, two strings or lists that look the same may not be eq?, because they are stored in different locations in memory. equal? (and thus member?) performs a deep comparison on lists and strings, and so basically any two items that print the same will be equal?. eqv? is like eq? for almost anything but numbers; for numbers, two numbers that are numerically equivalent will always be eqv?, but they may not be eq? (this is because of bignums and rational numbers, which may be stored in ways such that they won't be eq?)

> (eq? 'a 'a)
#t
> (eq? 'a 'b)
#f
> (eq? (list 'a 'b 'c) (list 'a 'b 'c))
#f
> (equal? (list 'a 'b 'c) (list 'a 'b 'c))
#t
> (eqv? (+ 1/2 1/3) (+ 1/2 1/3))
#t

(Note that some behavior of the functions is undefined by the specification, and thus may differ from implementation to implementation; I have included examples that should work in any R⁵RS compatible Scheme that implements exact rational numbers)

If you need to search for an item in a list using an equivalence predicate different than one of the built in ones, then you may want find or find-tail from SRFI-1:

> (find-tail? (lambda (x) (> x 3)) '(1 2 3 4 5 6))
'(4 5 6)

Solution 2

Here's one way:

> (cond ((member 'a '(a b c)) '#t) (else '#f))
#t
> (cond ((member 'd '(a b c)) '#t) (else '#f))
#f

member returns everything starting from where the element is, or #f. A cond is used to convert this to true or false.

Comments

[Rainer Joswig]

Use the language reference to find it: schemers.org/Documents/Standards/R5RS//HTML/…

[Rainer Joswig]

The question was about Scheme, not Common Lisp.

[Rainer Joswig]

Read the title: 'What is the SCHEME function to find an element in a list?'. Scheme is a dialect in the family of Lisp languages.

[Iulius Curt]

#t is fine also, instead of '#t

[Freewind]

What is the function name memq short for?

[Brian Campbell]

memq is one of the member family of functions, finding an item in a list based on some kind of equivalence (like the others mentioned, member and memv). The q, v, or full name connect it to the three equivalence functions that they each use; memq uses eq? to test equivalence, memv uses eqv? to test equivalence, and member uses equal? to test equivalence. See the linked documentation on equivalence functions for the difference between them.

[Freewind]

Thank you! So memq can be considered as mem-q, and memv as mem-v