stable-union lisp

Question

Need to write a union function in lisp that takes two lists as arguments and returns a list that is the union of the two with no repeats. Order should be consistent with those of the input lists

For example: if inputs are '(a b c) and '(e c d) the result should be '(a b c e d)

Here is what I have so far

(defun stable-union (x y)
  (cond
   ((null x) y)
   ((null y) x))
  (do ((i y (cdr i))
       (lst3 x (append lst3 
                       (cond
                        ((listp i) 
                         ((null (member (car i) lst3)) (cons (car i) nil) nil))
                        (t (null (member i lst3)) (cons i nil) nil)))))
        ((null (cdr i)) lst3)))

My error is that there is an "illegal function object" with the segment (null (member (car i) lst3))

Advice?

Answer 1

The error is because you're trying to execute the result of evaluating (null (member (car i) lst3)). In your cond expression, if i is a list, then it attempts to evaluate the expression

((null (member (car i) lst3)) (cons (car i) nil) nil))

And return the result. The first element in an expression should be a function, but

(null (member (car i) lst3))

Is going to return a boolean value. Hence the failure. The structure of your code needs some attention. What you've missed is that you need an inner cond, there.

Incidentally, this would be a much cleaner function if you did it recursively.

I'm a Schemer rather than a Lisper, but I had a little think about it. Here's the skeleton of a recursive implementation:

(defun stable-union (x y)
  (cond
    ((null x) y)
    ((null y) x)
    ((listp y)
     (cond 
       ((member (car y) x) (stable-union ??? (???))) 
       (t (stable-union (append x (??? (???))) (cdr y)))))
    ((not (member y x)) (append x (list y)))
    (t x)))

(Edited to correct simple tyop in second-last line, thanks to Will Ness for spotting it)

Answer 2

You've got your parens all jumbled-up:

(defun stable-union (x y)
  (cond
   ((null x) y)
   ((null y) x)  )     END OF COND form - has no effect

  (do ((i y (cdr i))
      ^^
       (lst3 x (append lst3 
                       (cond
                        ((listp i) 
                         (  (null (member (car i) lst3)) 
                         ^^ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~ called as a function
                             (cons (car i) nil)           with two arguments
                             nil  ) )
                                 ^^ 
                        (t                         NEXT 3 forms have no effect
                           (null (member i lst3))
                           (cons i nil)
                           nil           )))) )
                                             ^^
        ((null (cdr i)) lst3)))

Here's your code as you probably intended it to be, with corrected parenthesization and some ifs added where needed:

(defun stable-union (x y)
  (cond
   ((null x) y)
   ((null y) x)
   (t
    (do ((i y (cdr i))
         (lst3 x (append lst3 
                   (cond
                     ((listp i) 
                       (if (null (member (car i) lst3))
                           (cons (car i) nil)
                           nil))
                     (t 
                       (if (null (member i lst3))
                           (cons i nil)
                           nil))))))
        ((null (cdr i)) lst3)))))

There are still problems with this code. Your do logic is wrong, it skips the first element in y if it contains just one element. And you call append all the time whether it is needed or not. Note that calling (append lst3 nil) makes a copy of top-level cons cells in lst3, entirely superfluously.

Such long statements as you have there are usually placed in do body, not inside the update form for do's local variable.

---

But you can use more specialized forms of do, where appropriate. Here it is natural to use dolist. Following "wvxvw"'s lead on using hash-tables for membership testing, we write:

(defun stable-union (a b &aux (z (list nil)))
  (let ((h (make-hash-table))
        (p z))
    (dolist (i a)
      (unless (gethash i h)
        (setf (cdr p) (list i) p (cdr p))
        (setf (gethash i h) t)))
    (dolist (i b (cdr z))
      (unless (gethash i h)
        (setf (cdr p) (list i) p (cdr p))
        (setf (gethash i h) t)))))

using a technique which I call "head-sentinel" (z variable pre-initialized to a singleton list) allows for a great simplification of the code for the top-down list building at a cost of allocating one extra cons cell.

Answer 3

Because you started off with do, and because a recursive solution would be even worse, here's what you could've done:

(defun union-stable (list-a list-b)
  (do ((i list-b (cdr i))
       filtered back-ref)
      ((null i) (append list-a back-ref))
    (unless (member (car i) list-a)
      (if back-ref
          (setf (cdr filtered) (list (car i))
                filtered (cdr filtered))
          (setf back-ref (list (car i))
                filtered back-ref)))))

This is still quadratic time, and the behaviour is such that if the first list has duplicates, or the second list has duplicates, which are not in the first list - they will stay. I'm not sure how fair it is to call this function a "union", but you'd have to define what to do with the lists if they have duplicates before you try to unify them.

And this is what you might've done if you were interested in the result, rather than just exercising. Note that it will ensure that elements are unique, even if the elements repeat in the input lists.

(defun union-stable-hash (list-a list-b)
  (loop for c = (car (if list-a list-a list-b))
     with back-ref
     with hash = (make-hash-table)
     for key = (gethash c hash)
     with result
     do (unless key
          (if back-ref
              (setf (cdr result) (list c)
                    result (cdr result))
              (when (or list-a list-b)
                (setf back-ref (list c)
                      result back-ref)))
          (setf (gethash c hash) t))
     do (if list-a (setf list-a (cdr list-a))
            (setf list-b (cdr list-b)))
     do (unless (or list-a list-b)
          (return back-ref))))

Answer 4

(remove-duplicates (append '(a b c) '(e c d)) :from-end t)