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!

"For each element in list one, check if it is a member in list 2" — Daniel Jour
– Daniel Jour, Commented May 14, 2016 at 20:26

Peder Klingenberg · Accepted Answer · 2016-05-16 09:45:18Z

2

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

edited May 16, 2016 at 9:45

answered May 14, 2016 at 20:33

Peder Klingenberg

42.1k1 gold badge23 silver badges24 bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

Daniel Jour Over a year ago

I really like how you "explain without showing". That's one of the best answers I read in the last time :) (upvoted)

Sylwester Over a year ago

Actually a hash so that searching for each element from the first list in the second O(1) would be as important as making it tail recursive since both matters when the lists get big. CL doesn't have tco requirement so one should use loop.

Peder Klingenberg Over a year ago

@Sylwester: I'm not convinced that the benefits of O(1) lookup outweighs the costs of setting up the hashtable in the majority of uses. I guess the lists would have to be fairly big for that to be the case, and is that really the most common usecase for union? I would just go with the naive approach initially, and reimplement if warranted by profiling.

Sylwester Over a year ago

@PederKlingenberg I'm convinced you are right for very small lists, but as the size doubles the time squares for the naive approach you'll notice it above 4k elements for compiled code. btw: the built in function is called intersecition and the big-o differs between the implementations I have tested.

Peder Klingenberg Over a year ago

@Sylwester 4k elements are bigger than what I usually intersect. But I quite agree with you that a hash-table based approach may be better if the data warrants it. In the context of this question, though, I thought it would be too much information, I didn't want to explain hash tables. My hinting at tail recursion was because that is a likely next step for the OP, and mentioning built-in solutions was to try to ward off people hating on lisp because they were made to reimplement primitives badly in a school, without being told that the language provides better facilities.

Collectives™ on Stack Overflow

LISP common list function

1 Answer 1

5 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

5 Comments

Your Answer

Sign up or log in

Post as a guest

Related