.comment -*-  Mode:TEXT; -*-
.comment MEMQ, MEMBER
.document MEMQ - Checking for membership in a list using MEMQ and MEMBER.
.tag MEMQ
Lesson Searching Constructs MEMQ and MEMBER, Version 2
						     Kent M. Pitman, 5/27/79
                                          revised by Victoria Pigman, 9/1/82

By the time you read this lesson, let's hope you understand something about 
what a list is and how to play with it in some basic ways. Now let's discuss 
some of the more interesting kinds of things that you can do with lists.

To begin with, it's nice to be able to find if a certain symbol occurs in a 
list. This can be done with the function MEMQ. MEMQ takes two arguments. The
first should be a symbol and the second a list, so a typical call to MEMQ
could look like:
          (MEMQ SYMBOL SOME-LIST)
The above form will return NIL if SYMBOL cannot be found as a member of 
SOME-LIST. If it is found, MEMQ returns the portion of SOME-LIST that starts
with the first occurrence of SYMBOL. It uses EQ to test for equivalence, so is 
mainly useful for testing the membership of symbols in the list.

Try these examples:

	(MEMQ 'A '(C D E))

	(MEMQ 'A '(A B C))

	(MEMQ 'B '(A B C A B C))
.try
MEMQ is only for testing membership in the top level of a list. For instance,
arg 1 will not be found in the second arg if it is buried in it by other list 
structure. Try these examples:

	(MEMQ 'A '(FOO (A B C) BAR))

	(MEMQ 'A '(FOO (A B C) A B C))
.try
Since MEMQ uses the EQ test, which will not say two lists are the same unless 
they are pointers to the same instance of a list, It will fail in most cases 
to find a list in the second list. Try these examples:

	(MEMQ '(A B) '(FOO (A B) BAR))
.try
But notice we said 'in most cases' ... In fact, if you are looking for a 
pointer to exactly the same list, you will find it. Here's an example:

	(SETQ A '(FOO BAR))

Returns =>  (FOO BAR)

	(SETQ B (LIST 'A A 'B))

Returns =>  (A (FOO BAR) B)

	(MEMQ A B)

Returns =>  ((FOO BAR) B)

because a pointer to the same instance of the list A was found in the list you 
were looking in. This will never happen unless you do something to force it to 
happen (such as how we constructed B above). Normally two lists are created out
of completely unrelated pieces. (We have set up A and B for you in this way,
if you'd like to check this out for yourself.)
.eval
(SETQ A '(FOO BAR) B (LIST 'A A 'B))
.try
It should have been apparent that the extra (...)'s hide the existence of A in 
the list. In most practical programming problems this will be what you want 
anyway. It is not a misfeature as it may seem at first because it is [1] much 
more efficient to do and [2] much more useful.

The function MEMQ could be defined using other functions in Lisp. (It isn't --
for efficiency, since it is used often, it's written in assembly code, but it 
needn't be). This is how MEMQ could be defined in Lisp:

.pp
(DEFUN MYMEMQ (ELEMENT LIST-TO-LOOK-IN)
  (COND ((NULL LIST-TO-LOOK-IN)
	 NIL)
	((EQ (CAR LIST-TO-LOOK-IN) ELEMENT)
	 LIST-TO-LOOK-IN)
	(T
	 (MYMEMQ ELEMENT (CDR LIST-TO-LOOK-IN)))))

Now let's try another function which is very much like MEMQ but will look for 
non-symbols (ie, numbers or lists) in a list. This function is called MEMBER. 
It is just like MEMQ except it uses the EQUAL predicate instead of the EQ test 
for checking equality. (It is, of course, slower than MEMQ - generality costs.)

Try this example:

	(MEMQ '(A B) '(FOO (A B) BAR))

	(MEMBER '(A B) '(FOO (A B) BAR))
.try
MEMBER is also useful for finding numbers in a list. (NOTE: Due to an 
implementation-dependent feature of Maclisp, most small FIXNUM's in Maclisp 
are EQ and can be found by an EQ test. Do not rely on this! It is not a 
reliable feature.)

	(MEMQ 1 '(3 2 1))   ; This works by accident!
	(MEMBER 1 '(3 2 1)) ; This works because it should!

	(MEMQ 895 '(455 895 129))   ; This doesn't work!
	(MEMBER 895 '(455 895 129)) ; This works because it should!

	(MEMQ '(A B) '((A B) (C D) (E F)))   ; This better not work!
	(MEMBER '(A B) '((A B) (C D) (E F))) ; This better work!
.try
.next ASSQ