Recursive 'member-of'

Discussion of Common Lisp
Post Reply
anta40
Posts: 19
Joined: Fri Oct 10, 2008 10:27 pm
Contact:

Recursive 'member-of'

Post by anta40 » Sat Mar 14, 2009 9:11 am

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? :?

nuntius
Posts: 538
Joined: Sat Aug 09, 2008 10:44 am
Location: Newton, MA

Re: Recursive 'member-of'

Post by nuntius » Sat Mar 14, 2009 9:55 am

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.

Wodin
Posts: 56
Joined: Sun Jun 29, 2008 8:16 am

Re: Recursive 'member-of'

Post by Wodin » Sun Mar 15, 2009 9:01 am

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

Post Reply