Lisp function: union

Question

I have lisp homework. I have a hard time with this.

I need to write a function that performs a join operation. The function accepts 2 inputs, either in the form of either an atom or a list, and combines each element, keeping order and cutting off all levels of parentheses.

Output for function:

(my-union 'a 'b) ;; (ab) (my-union 'a '(b)) ;; (ab) (my-union '(ab) '(bc)) ;; (abc) (my-union '(((a))) '(b(c((de))a))) ;; (abcde) 

I am new to lisp. Here is what I wrote so far and only works for the third example:

 (defun new-union (ab) (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 without worrying about performance and making good use of the CL tools:

Common Lisp already has a function that removes duplicates: remove-duplicates . Using it with :from-end keyword argument will "keep order". Now imagine that you have a flatten function that aligns arbitrary nested lists. Then the solution to your question will 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 additional restrictions are given, and there is no real reason to worry about performance. Use as much of this toolkit as possible and do not reinvent the wheels if necessary.

If you come up with a problem like this, it comes down to writing a flatten function, which I will leave as an exercise for you. This is not too complicated, one simple option is to write a recursive function, approaching such a problem:

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

This should be a good exercise for you, and it can be done with just a few lines of code.

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

Now, if you wrote flatten :

 > (defun new-union (list1 list2) (remove-duplicates (flatten (list list1 list2)) :from-end t)) NEW-UNION > (new-union 'a 'b) (AB) > (new-union 'a '(b)) (AB) > (new-union '(ab) '(bc)) (ABC) > (new-union '(((a))) '(b (c ((de)) a))) (ABCDE) 

Answer 2

One way to get closer to this is to separate your concerns. One of them is flattened; another - duplication - deletion; the other is the result.

Starting with an empty list as a result, add the elements of the first list to it, skipping those elements that are already in the result.

Then do the same with the second list items, adding them to the same list of results.

 (defun my-union (ab &aux (res (list 1)) (p res)) (nadd-elts pa) (nadd-elts pb) (cdr res)) 

nadd-elts will add a destructive update to its last cell (indicated by p ) at the end of the list, using, for example, rplacd . An example is here .

To add elements, nadd-elts will emulate a smooth procedure and add each leaf element to p after res check for duplicates.

---

Working in a functional style without a destructive update, the general approach remains the same: start with an empty list of results, add the first list to it - without duplicates - then the second.

 (defun my-union (ab &aux res) (setq res (add-into res a)) (setq res (add-into res b)) res) 

Now we have to implement the add-into function.

 (defun add-into (res a &aux r1 r2) (cond ((atom a) .... ) (T (setq r1 (add-into res (car a))) (setq r2 (............ (cdr a))) r2))) 

The above can be rewritten without auxiliary variables and without set primitives. Try to figure out how ... OK, what I meant:

 (defun my-union (ab) (add-into NIL (cons ab))) (defun add-into (res a) (cond ((atom a) .... ) (T (add-into (add-into res (car a)) (cdr a))))) 

Answer 3

If you are not allowed to use a hash table (for some reason I came across this as a requirement before), you can create an ordering function that helps you create the result set in the path that you put on. Repeat the search again and again.

Also, since nested lists are resolved, your problem scales to removing only duplicates in the tree (since you can simply add as many lists as you like before proceeding to process them.

Now I will try to show some examples of how you could do this:

 ;; Large difference between best and worst case. ;; Lists containing all the same items will be processed ;; in square time (defun union-naive (list &rest lists) (when lists (setf list (append list lists))) (let (result) (labels ((%union-naive (tree) (if (consp tree) (progn (%union-naive (car tree)) (when (cdr tree) (%union-naive (cdr tree)))) (unless (member tree result) (setq result (cons tree result)))))) (%union-naive list) result))) ;; Perhaps the best solution, it is practically linear time (defun union-hash (list &rest lists) (when lists (setf list (append list lists))) (let ((hash (make-hash-table)) result) (labels ((%union-hash (tree) (if (consp tree) (progn (%union-hash (car tree)) (when (cdr tree) (%union-hash (cdr tree)))) (setf (gethash tree hash) t)))) (%union-hash list)) (maphash #'(lambda (ab) (declare (ignore b)) (push a result)) hash) result)) ;; This will do the job in more time, then the ;; solution with the hash-map, but it requires ;; significantly less memory. Memory is, in fact ;; a more precious resource some times, but you ;; have to decide what algo to use based on the ;; data size (defun union-flatten (list &rest lists) (when lists (setf list (append list lists))) (labels ((%flatten (tree) (if (consp tree) (if (cdr tree) (nconc (%flatten (car tree)) (%flatten (cdr tree))) (%flatten (car tree))) (list tree)))) ;; the code below is trying to do something ;; that you could've done using ;; (remove-duplicates (%flatten list)) ;; however sorting and then removing duplicates ;; may prove to be more efficient (reduce #'(lambda (ab) (cond ((atom a) (list a)) ((eql (car a) b) b) (t (cons ba)))) (sort (%flatten list) #'(lambda (ab) (string< (symbol-name a) (symbol-name b))))))) (union-naive '(((a))) '(b(c((de))a))) (union-hash '(((a))) '(b(c((de))a))) (union-flatten '(((a))) '(b(c((de))a))) 

Please note that the function I used to organize the elements is not universal, but you can probably come up with an alternative function for any data. Any quick hash function would do at all, I used it for simplicity.