LISP common list function

Question

Hey guys I have one last problem Im trying to solve for my semester. I need to create:

(myCommon L1 L2)
Evaluates to a list of elements that are common in both lists L1 and L2.
Assume L1 and L2 have no repeated elements.
eg.  (myCommon ‘(p a e g) ‘(a q r e))  →  (a e)

I can only use the following functions:

(atom X)            
(quote X)           
‘X          
(eq X Y)            
(cons X L)          
(car L)         
(cdr L)         
(list A B C)        
(if X Y Z)      .
(cond (C1 S1) (C2 S2) …… (Cn Sn))       
(lambda (P1 P2 …… Pn) E)        
(funcall F (P1 P2 …… Pn))   

I can also use the functions I have created within the assignment. So far I have created:

(defun myLast (L) 
  (if (eq (cdr L) '()) 
  (car L) 
  (myLast (cdr L))))               ;Evaluates to the last element of list L

(defun myCount (X L)
   (cond ((eq L '()) 0)
     ((eq X (car L))(+ 1 (myCount X (cdr L))))
     (+ (myCount X (cdr L)))))   ;Evaluates to number of occurrences of X in L

(defun myMember (X L)
   (cond ((eq L '()) '())
   ((eq X (car L)) t)
   (t (myMember X (cdr L)))))   ;Evaluates to true if X in L, false otherwise

The problem with this assignment is I cant meet up with the teacher to ask questions as hes gone, and has "limited email access" right now. I cant ask questions on how to solve this problem and I am very confused on even where to start for this function. I think I would have to use myMember on like the car of L1 and check if its in L2, if it is put it in a new list and recursively add to the list. I wasnt sure how to do this. Could anyone help me out so I can finally finish this semester? Thank you!

Answer 1

Your idea is a good one. You should look at the pattern you used in myCount. You can use nearly the same pattern for myCommon.

Think about how to bottom out of the recursion. You are building up a list, not a number, so instead of 0 as the terminal value, think about what the end of a list is.

For the recursion clauses, instead of using + 1 when you should include the item, use a function that adds an item to a list.

Remember to only recurse down one of the lists in myCommon. You should be looking at one element at a time, and compare that element to the complete second list, which for the purposes of myCommon should be a constant.

Hopefully this should help you along, in the spirit of your previous functions. But this is a very inefficient way of implementing a intersection-function.

A common trick which can help your compiler produce more efficient code is to use a helper function with a third parameter - an accumulator that you build up as you recurse down one of your input lists. (The accumulator trick lets you write your function in a style called tail recusive.)

And when you are not doing artificially restricted excercises to learn recursion, I would prefer to use iteration (loop or dolist) to solve this, especially when you are using common lisp, which doesn't mandate that the compiler produces efficient code even for the tail recursive calls. But then again, if you're not using a restricted version of common lisp, you could just call the built-in function intersection. :-)