CODEWITHSUNDEEP
recursioncommon-lisp
bB12
bB12

Reputation: 1

How to Recursively iterate through 2 lists

For my homework problem, I have to remove the duplicates in a list if part of the list is inside another. The expected outcome is supposed to be this:

(remove-redundant '((R (1 2 3 8 e 4 7 6 5))
                    (U (e 2 3 1 8 4 7 6 5))
                    (D (1 2 3 7 8 4 e 6 5)))

                  '((D (1 2 3 e 8 4 7 6 5))
                    (L (e 2 3 1 8 4 7 6 5))
                    (U (2 e 3 1 8 4 7 6 5))
                    (U (2 8 3 1 e 4 7 6 5))))

Returns:

((R (1 2 3 8 e 4 7 6 5)) (D (1 2 3 7 8 4 e 6 5)))

It is supposed to check to see if the list inside each list, for the 1st parameter appears anywhere in the 2nd. If it does appear, then remove that from the 1st list. Basically, if (1 2 3 e 8 4 7 6 5) matches something in the 1st list, remove it from the 1st list. I need to do this recursively, it is supposed to be a functional program.

I have already tried recursing through the list, but it doesn't reset (i.e. it will check the second list for the beginning of the first list but then will return.

(defun same-state (l1 l2)
   (if (equal (cadr l1) (cadr l2)) t nil))

(defun remove-redundant (l1 l2)
  (cond
     ((null l2) l1)
     ((null l1) nil)
     ((same-state (car l1) (car l2)) (remove-redundant (cdr l1) (cdr l2))
     (T (remove-redundant l1 (cdr l2)))))

Upvotes: 0

Views: 278

Answers (2)

Rorschach
Rorschach

Reputation: 32466

You're close, but there should be some accumulation of the cells you want to keep in the t case of your cond form, eg.

;; ...
(t
 (cons (car l1) (remove-redundant (cdr l1) (cdr l2))))

and when you check if the first element of l1 exists in l2 there should be another loop or recursion to check against all the elements in l2, eg.

(defun same-state (l1 l2)
  (find l1 l2 :key #'cadr :test #'equal))

(defun remove-redundant (l1 l2)
  (cond
    ((null l2) l1)
    ((null l1) nil)
    ((same-state (cadar l1) l2)
     (remove-redundant (cdr l1) (cdr l2)))
    (t (cons (car l1)
             (remove-redundant (cdr l1) (cdr l2))))))
;; => ((R (1 2 3 8 e 4 7 6 5)) (D (1 2 3 7 8 4 e 6 5)))

Upvotes: 1

Svante
Svante

Reputation: 51531

You will need two loops: one to go through the first list, and then one per element of that to find matches in the second list.

Upvotes: 0

Related Questions