Lisp function: union

Question

I have a lisp homework I am having a hard time with it.

I have to write a function that perform a union operation. The function takes 2 inputs, either in the form of either atom or list and unions every element, preserving the order and stripping off all levels of parenthesis.

The output for the function:

(my-union 'a 'b)                         ;; (a b)
(my-union 'a '(b))                       ;; (a b)
(my-union '(a b) '(b c))                 ;; (a b c)
(my-union '(((a))) '(b(c((d e))a)))      ;; (a b c d e)

I am fairly new to lisp. Here is what I have written so far and it works only for the third example:

(defun new-union (a b)
 (if (not b)
      a
      (if (member (car b) a)
        (new-union a (cdr b))
        (new-union (append a (list (car b))) (cdr b)))))

Any help would be appreciated!

Answer 1

Since this is your first homework, and you are new to Lisp, here is a very simple top-down approach, not worrying about performance, and making good use of the tools CL offers:

In Common Lisp, there is already a function which removes duplicates: remove-duplicates. Using it with the :from-end keyword-argument will "preserve order". Now, imagine you had a function flatten, which flattens arbitrarily nested lists. Then the solution to your question would be:

(defun new-union (list1 list2)
  (remove-duplicates (flatten (list list1 list2)) :from-end t))

This is how I would approach the problem when no further restrictions are given, and there is no real reason to worry much about performance. Use as much of the present toolbox as possible and do not reinvent wheels unless necessary.

If you approach the problem like this, it boils down to writing the flatten function, which I will leave as an exercise for you. It is not too hard, one easy option is to write a recursive function, approaching the problem like this:

If the first element of the list to be flattened is itself a list, append the flattened first element to the flattened rest. If the first element is not a list, just prepend it to the flattened rest of the list. If the input is not a list at all, just return it.

That should be a nice exercise for you, and can be done in just a few lines of code.

(If you want to be very correct, use a helper function to do the work and check in the wrapping function whether the argument really is a list. Otherwise, flatten will work on atoms, too, which may or may not be a problem for you.)

Now, assuming you have written flatten:

> (defun new-union (list1 list2)
    (remove-duplicates (flatten (list list1 list2)) :from-end t))
NEW-UNION
> (new-union 'a 'b)
(A B)
> (new-union 'a '(b))
(A B)
> (new-union '(a b) '(b c))
(A B C)
> (new-union '(((a))) '(b (c ((d e)) a)))
(A B C D E)