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?

Delta

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

Answer 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)

Madel

What is the function name memq short for? – Passerby

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. – Madel

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

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

Martymartyn

#t is fine also, instead of '#t – Tool

Answer 3

 (define (member? x list)
     (cond ((null? list) #f)
           ((equal? x (car list)) #t)
           (else   (member? x (cdr list)))))

The procedure return #t (true) or #f (false)

(member? 10 '(4 2 3))

output is #f

Dressmaker

Answer 4

You are looking for "find"

Basics - The simplest case is just (find Entry List), usually used as a predicate: "is Entry in List?". If it succeeds in finding the element in question, it returns the first matching element instead of just "t". (Taken from second link.)

http://www.cs.cmu.edu/Groups/AI/html/cltl/clm/node145.html

-or-

http://www.apl.jhu.edu/~hall/Lisp-Notes/Higher-Order.html

Spunk

The question was about Scheme, not Common Lisp. – Marche

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. – Marche

Answer 5

I don't know if there is a built in function, but you can create one:

(define (occurrence x lst)
       (if (null? lst) 0    
            (if (equal? x (car lst))  (+ 1 (occurrence x (cdr lst)))
                                     (occurrence x (cdr lst)) 
            )
       )
) 

Ỳou will get in return the number of occurrences of x in the list. you can extend it with true or false too.

Handfasting