CODEWITHSUNDEEP
lisp
Cláudio Ribeiro
Cláudio Ribeiro

Reputation: 1699

Lisp - Elements of a lisp occur in other list

i'm having a problem with this lisp function. I want to create a function that receives two lists, and verifies if the elements of the first list (all of them) occur in the second list, it returns True if this happens.

Currently i have the following code:

(defun ocorre-listas (l1 l2)
(dolist (elem1 l1)
    (dolist (elem2 l2)
        (if (equal elem1 elem2)
            t))))

It's not working, as expected. Should i try to do it just with a simple recursion? I'm really not getting how i can iterate both lists in search of equal elements.

I decided to try without the dolists. This is what i have now, it's still not working.

(defun ocorre-listas (l1 l2)
(cond ((null l1) nil)
        ((null l2) nil)
        ((if (/= (first l1)(first l2)) (ocorre-listas l1 (rest l2))))
        (t (if (= (first l1) (first l2)) (ocorre-listas (rest l1)(rest l2))))))

I get a warning saying that "t" is an undefined function. Also, every example i try returns null. What am i doing wrong ?

Upvotes: 1

Views: 623

Answers (6)

protist
protist

Reputation: 1220

While there are many ways to do this, I would recommend using a hash table to avoid O(n^2) complexity. Using a hash table, you can achieve O(n) complexity.

here is a union function

(defun my-union (a b)
  (let ((h (make-hash-table :test #'equal)))
    (mapcar (lambda (x) (setf (gethash x h) x)) a)
    (mapcan (lambda (x) (when (gethash x h) (list x))) b)))

here is a function testing for IDENTICAL elements in boths lists

(defun same-elements (a b)
  (apply #'= (mapcar #'length (list (my-union a b) a b))))

here is a function making sure a is a subset of b (what you asked)

(defun subset (a b)
  (same-elements (my-union a b) a))

Upvotes: 1

Jürgen Hötzel
Jürgen Hötzel

Reputation: 19757

See the common lisp subsetp predicate and its implementation:

CL-USER> (subsetp '(1 2 3) '(1 2 3 4)
T

Upvotes: 2

Rörd
Rörd

Reputation: 6681

So you need to check if every element of l1 is a member of l2. These are both functions in the Common Lisp standard library, so if you're allowed to use them, you can build a simple solution with them.

Upvotes: 2

Ed.
Ed.

Reputation: 1952

In the second piece of code, if the first list is empty then all of its elements are in the second one.

You don't need the ifs since you are inside a cond

After test if the lists are empty, you'll only need to test if the first element of the first list is in the second one and call the function again with the first list without this element

Upvotes: 2

finnw
finnw

Reputation: 48659

Instead of trying to do everything in one function, consider splitting it into two (or more) functions, e.g.

  • One that takes a number and the second list, and tests whether the number appears in the list
  • Another that iterates over the numbers in the first list, and for each one tests (using the first function) whether it appears in the second list.

As well as DOLIST, consider using MAPCAR and FIND-IF (assuming they are allowed in this assignment.)

Upvotes: 2

codeling
codeling

Reputation: 11438

To be able to work on both lists at the same time, the trick is probably to sort the lists before starting the recursion. Then it should be a simple matter of comparing the first element, and applying the same function to the rest of the list recursively, with some CAR/CDR magic added of course...

Upvotes: 1

Related Questions