Recursive 'member-of'

Discussion of Common Lisp

Recursive 'member-of'

Postby 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? :?
anta40
 
Posts: 18
Joined: Fri Oct 10, 2008 10:27 pm

Re: Recursive 'member-of'

Postby 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.
User avatar
nuntius
 
Posts: 498
Joined: Sat Aug 09, 2008 10:44 am
Location: Burlington, MA

Re: Recursive 'member-of'

Postby 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))
Wodin
 
Posts: 56
Joined: Sun Jun 29, 2008 8:16 am


Return to Common Lisp

Who is online

Users browsing this forum: Google [Bot] and 3 guests

cron