Page 1 of 1

Recursive 'member-of'

Posted: Sat Mar 14, 2009 9:11 am
by anta40
I'm trying to write a 'member-of' function, to check whether an element is a member of a list or not.

My first attempt, the iterative one, is pretty easy:

Code: Select all

(defun member-of (elem the-list)
  (if (eql elem (car (member elem the-list)))
	'T
	'NIL)
Now I want to make the recursive version.

Code: Select all

(defun member-of (elem the-list)
  (if (eql elem (car the-list))
	'T
	(member-of elem (cdr the-list))))
Of course that only works if the element is indeed a member of the list.
If the element isn't, this function will not terminate.
How to fix this? :?

Re: Recursive 'member-of'

Posted: Sat Mar 14, 2009 9:55 am
by nuntius
also terminate when the list is empty? and your "iterative" version doesn't really count; it just wraps (oddly) a preexisting function. and don't quote T or NIL.

I would try using DOLIST to write a proper iterative version. Then the recursive version should be straightforward.

Re: Recursive 'member-of'

Posted: Sun Mar 15, 2009 9:01 am
by Wodin
anta40 wrote:

Code: Select all

(defun member-of (elem the-list)
  (if (eql elem (car the-list))
	'T
	(member-of elem (cdr the-list))))
Of course that only works if the element is indeed a member of the list.
If the element isn't, this function will not terminate.
How to fix this? :?
The problem is that when you get to the end of the list, you call:

Code: Select all

(member-of elem (cdr '(last-elem)))
where (cdr '(last-elem)) returns NIL.

Then you test (eql elem (car NIL)), but (car NIL) is NIL and (eql elem NIL) is false, so you get down to:

Code: Select all

(member-of elem (cdr NIL))
But (cdr NIL) is also NIL (just as (cdr '(last-elem)) is NIL), so you get into an infinite loop.

As nuntius said, you need to check first to see if the list is empty before doing the other checks.

By the way, your first version could be written like this:

Code: Select all

(defun member-of (elem the-list)
  (when (member elem the-list)
    t))