CODEWITHSUNDEEP
listmergelispcommon-lisp
MadPhysicist
MadPhysicist

Reputation: 5841

Merging Two Lists in Common Lisp

Is there an efficient way to merge two lists in Lisp so that if they had common elements, those elements would be present in the resulting list only once?

At the moment, I have the following code:

(defun divisible-by-5 (num)
  (zerop (mod num 5)))

(defun divisible-by-3 (num)
  (zerop (mod num 3)))

(remove-if-not #'dividable-by-5 '(loop for i from 1 upto 10 collect i))
(remove-if-not #'divisible-by-3 '(loop for i from 1 upto 10 collect i))

I would like to merge the two lists returned by the bottom forms to be merged into on in a manner described above.

Upvotes: 0

Views: 3419

Answers (1)

Joshua Taylor
Joshua Taylor

Reputation: 85913

You're already collecting the lists (1 ... n) twice, and then creating new lists with certain elements removed, and then you're combining those lists. If you're looking for efficient, you should probably combine the process of generating the initial list and testing and the collection:

(flet ((by-5 (n)
         (zerop (mod n 5)))
       (by-3 (n)
         (zerop (mod n 3))))
  (loop for x from 1 to 50
     unless (and (by-3 x)
                 (by-5 x))
     collect x))

But if you really want to collect the lists separately and then merge them, you can do that with UNION:

(flet ((by-5 (n)
         (zerop (mod n 5)))
       (by-3 (n)
         (zerop (mod n 3))))
  (let ((fives (loop for x from 1 to 50 unless (by-5 x) collect x))
        (threes (loop for x from 1 to 50 unless (by-5 x) collect x)))
    (union fives threes)))

Now, union isn't guaranteed to preserve order, but in this case, since you know that your lists are already ordered, you could merge them a bit more efficiently, since you can compare the elements, and know that after a certain point, you wouldn't encounter a duplicate:

(defun merge-unique (l1 l2 predicate)
  "Returns the result of merging L1 and L2, with no duplicates.
L1 and L2 should already be sets (that is, containing no duplicates), 
and should be ordered according to PREDICATE.  The tail of the result
may be shared with with either L1 or L2."
  (labels ((test (x y)
             (funcall predicate x y))
           (%merge (l1 l2 result)
             "Tail recursive merge procedure.  This could be converted
              to an iterative DO-loop without too much touble."
             (cond
               ((endp l1)
                (nreconc result l2))
               ((endp l2)
                (nreconc result l1))
               ((destructuring-bind (x . xs) l1
                  (destructuring-bind (y . ys) l2
                    (cond
                      ((test x y)
                       (%merge xs l2 (list* x result)))
                      ((test y x)
                       (%merge l1 ys (list* y result)))
                      (t
                       (%merge xs ys (list* x result))))))))))
    (%merge l1 l2 '())))

Here's an example of its use:

(merge-unique '(1 3 5 6) '(1 4 5 6) '<)
;;=> (1 3 4 5 6)

Upvotes: 3

Related Questions