recursion and then some

Discussion of Common Lisp

recursion and then some

Postby dstudentx » Mon Sep 19, 2011 4:31 pm

I'm trying to learn lisp and the task I'm trying to conquer is this .
I need to write a recursive function which checks for a given atom that occurs anywhere in an expression.

for example
function search 'a '(b a c)) returns T
search 'a '(k (g c a) h )) returns T

I'm lost please any help would be greatly appreciated
dstudentx
 
Posts: 1
Joined: Mon Sep 19, 2011 4:25 pm

Re: recursion and then some

Postby Duke » Mon Sep 19, 2011 7:00 pm

You should probably read On Lisp, or ANSI Common Lisp. They (I'm guessing both of them) go over the function in detail. You could also try grepping the source of your favorite Common Lisp implementation for "defun member" to see a real-life example.

But, it's good to figure these things out for yourself, too. Since you didn't post an attempt at solving it, I'm going to show you a simple way to write a recursive list copy function:

Code: Select all
CL-USER> (defun my-copy (list &optional acc)
           (cond ((null list) (reverse acc))
                 (t (my-copy (cdr list) (cons (car list) acc)))))

Member might work almost the same way, except that it doesn't accumulate a list, and has an extra case for testing EQUALity of a given value.

I think that's enough of a hint; give it a try.

Edit: With regards to atoms, you might want to make sure you're using the right equality predicate.
"If you want to improve, be content to be thought foolish and stupid." -Epictetus
Duke
 
Posts: 38
Joined: Sat Oct 17, 2009 10:40 pm

Re: recursion and then some

Postby Paul » Wed Sep 21, 2011 10:43 pm

Duke wrote:You should probably read On Lisp, or ANSI Common Lisp. They (I'm guessing both of them) go over the function in detail. You could also try grepping the source of your favorite Common Lisp implementation for "defun member" to see a real-life example.


Member doesn't look in sublists, and your copy function only copies the backbone...

dstudentx: given an 'object', check whether it's the one you're looking for, or a cons cell; if it's a cons, "search" its CAR and its CDR for the thing you're looking for.
Paul
 
Posts: 106
Joined: Tue Jun 02, 2009 6:00 am


Return to Common Lisp

Who is online

Users browsing this forum: No registered users and 8 guests

cron