Lisp union function

Question

I don't mind admitting that this is a homework task that has me stumped. Any push in the right direction would be useful.

I'm required to write a function that returns the union of the two given lists. I believe my logic is sound, but Lisp syntax is driving me up a wall.

My solution so far is this.

(defun inList (e L)
  (cond 
   ((null L) 
    nil) 
   ((equal (first L) e) 
    T) 
   (T 
    (inList e (rest L)))))

(defun union2 (L1 L2)
  (cond 
   ((null L2) 
    L1) 
   ((not (inList (first L2) L1)) 
    (append (union2 L1 (rest L2)) (first L2))) 
   (T 
    (union2 L1 (rest L2)))))

When I test the function with an empty list as the second argument, or with the second argument being a list in which every item is a member of the first list, it works correctly.

However, when tested with (union2 '(1 2 3) '(4 5 6)) I get 6 is not of type list.

I'm fairly certain that my error is in: (append (union2 L1 (rest L2)) (first L2)

As at that point, (first L2) is obviously not a list. However, writing it as ((first L2)) is giving me Badly formed lambda.

As I said, any tips or pointers would be appreciated.

Answer 1

You really need to indent your code. The following is understood by most Lisp users. It is automatically and properly indented and has no parentheses on their own lines.

(defun union2 (L1 L2)
  (cond 
   ((null L2) L1)
   ((not (inList (first L2) L1)) 
    (append (union2 L1 (rest L2))
            (first L2))) 
   (T (union2 L1 (rest L2)))))

So you think, (append ... (first L2)) is a problem?

append expects lists as arguments. The first element of l2 probably is not a list.

How do you make a list?

• (append l1 l2 ...) returns a list of the appended lists
• (cons item l1) returns a list with the item added to the front of l1.
• (list e1 ...) returns a list with the items e1 ... as elements. It takes zero or more arguments.

One of the above should help you to create a new list from an item.

Also note that appending to the end of a list is not an efficient list operation in Lisp. Adding elements to the front of a list is preferred.

Answer 2

Rainer Joswig's answer is correct, and since this is a homework assignment, it may be the most appropriate, since you might not be allowed to use certain functions. Otherwise you could just use Common Lisp's union function:

(union '(1 2 3) '(4 5 6))
;=> (3 2 1 4 5 6)

Using that, you could write a definition like the following (though you probably won't get credit for it, unless someone says, "Finally, a student who skimmed the standard library!"):

(defun easy-union (list1 list2)
  (union list1 list2))

However, in general, this might be a bit easier if you use the standard function adjoin which takes an element and adds it to a list unless the element is already in the list. Using it, you don't need to write an inList function (for which you could already have been using member):

(defun recursive-union (list1 list2)
  (if (endp list1)
      list2
      (recursive-union (rest list1)
                       (adjoin (first list1)
                               list2))))

(recursive-union '(1 2 3) '(4 5 6))
;=> (3 2 1 4 5 6)

(recursive-union '(1 2 3) '(2 3 4))
;=> (1 2 3 4)

That's tail recursive, you could also do the same thing iteratively (which might be a good idea if your particular implementation doesn't perform tail call optimization):

(defun iterative-union (list1 list2)
  (do ((list2 list2 (adjoin (first list1) list2))
       (list1 list1 (rest list1)))
      ((endp list1) list2)))

(iterative-union '(1 2 3) '(4 5 6))
;=> (3 2 1 4 5 6)

(iterative-union '(1 2 3) '(2 3 4))
;=> (1 2 3 4)

There are some other useful library functions that could help you out here, too, such as set-difference. For instance, based on the identity A ? B = (A / B) ? B, you might write:

(defun another-union (list1 list2)
  (nconc (set-difference list1 list2)
         list2))

You might be prohibited from using set-difference, of course, in which case remove-if and member are helpful for simulating it:

(defun yet-another-union (list1 list2)
  (nconc (remove-if #'(lambda (e)
                        (member e list2))
                    list1)
         list2))

Answer 3

FWIW, this iterative version is what I use most of the time. It is essentially the same as cl-union (formerly union) in Emacs cl-seq.el, but with no keyword treatment.

(defun icicle-set-union (list1 list2)
  "Combine LIST1 and LIST2 using a set-union operation.
The result list contains all items that appear in either LIST1 or
LIST2.  This is a non-destructive function; it copies the data if
necessary."
  (cond ((null list1)         list2)
        ((null list2)         list1)
        ((equal list1 list2)  list1)
        (t
         (unless (>= (length list1) (length list2))
           (setq list1  (prog1 list2 (setq list2  list1)))) ; Swap them.
         (while list2
           (unless (member (car list2) list1)  (setq list1  (cons (car list2) list1)))
           (setq list2  (cdr list2)))
         list1)))

Answer 4

 (defun my-union (x y)
    (cond ((null x) y)
          ((member (car x) y) (my-union (cdr x) y))
          (t (cons (car x) (my-union (cdr x) y)))))

CL-USER> (my-union '(1 3 5 7) '(2 4 6 8))
 0: (MY-UNION (1 3 5 7) (2 4 6 8))
   1: (MY-UNION (3 5 7) (2 4 6 8))
     2: (MY-UNION (5 7) (2 4 6 8))
       3: (MY-UNION (7) (2 4 6 8))
         4: (MY-UNION NIL (2 4 6 8))
         4: MY-UNION returned (2 4 6 8)
       3: MY-UNION returned (7 2 4 6 8)
     2: MY-UNION returned (5 7 2 4 6 8)
   1: MY-UNION returned (3 5 7 2 4 6 8)
 0: MY-UNION returned (1 3 5 7 2 4 6 8)
       (1 3 5 7 2 4 6 8)

This is my recursion-union code.

Hope it can help you or anybody

Answer 5

(defun set-member (set item)
  (cond
    ( (=(length set)0)nil)
    ((equal item (car set))t)
    (t (set-member (cdr set)item))))



(defun set-union (set-1 set-2)
  (cond
    ((= (length set-2)0) set-1)
    ((set-member set-1 (car set-2)) (set-union set-1 (cdr set-2)))
    (t (cons (car set-2)(set-union set-1 (cdr set-2))))
   ))

To find the union of two sets in lisp without using any built-in function, we need to define a function that checks if an item in the given list. We use it to find the union of two sets.

I am checking if the length of set-2 is 0, and return set-1 if it is. This condition is also helpful to terminate the recursion. Second line of the set-union function checks if first item of set-2 is in set-1 and repeats the recursion with set-1 and cdr(set-2). The else condition ( the last line) uses the cons to return the a element of set-2 ( which is not in set-1) and set-1 as list and uses the tail recursion until length set-2=0. The last line is an else condition.

I hope it is helpful for someone.