Re: `remove-duplicates'

[David Kastrup <dak@gnu.org>]

Juanma Barranquero <lekktu@gmail.com> writes:

> On Sun, Jul 10, 2011 at 17:05, Lars Magne Ingebrigtsen <larsi@gnus.org> wrote:
>
>> Would anybody mind if I add a simple version of `remove-duplicates' to
>> subr.el?  I'm tired of rewriting the same loop...
>
> I think there are also quite a few cases in the sources of destructive
> deleting of *consecutive* duplicates. I once proposed this:
>
> (defun uniqify (list)
>  "Destructively remove consecutive `equal' duplicates from LIST.
> Store the result in LIST and return it.  LIST must be a proper list."
>  (let ((l list))
>    (while (cdr l)
>      (if (equal (car l) (cadr l))
>          (setcdr l (cddr l))
>        (setq l (cdr l))))
>    list))

I have something like this here:

(defun uniquify (list predicate)
  (let* ((p list) lst (x1 (make-symbol "x1"))
	 (x2 (make-symbol "x2")))
    (while p
      (push p lst)
      (setq p (cdr p)))
;;;    (princ lst)(princ "\n")
    (setq lst
	  (sort lst `(lambda(,x1 ,x2)
		       (funcall ',predicate (car ,x1) (car ,x2)))))
;;; lst now contains all sorted sublists, with equal cars being
;;; sorted in order of increasing length (from end of list to start).
;;

    (while (cdr lst)
      (unless (funcall predicate (car (car lst)) (car (cadr lst)))
	(setcar (car lst) x1))
      (setq lst (cdr lst)))
    (delq x1 list)))

One could turn the predicate into an optional argument.  The idea is
that with an order relation (in this case "less"), the behavior can be
turned from O(n^2) to O(n log n).  Another possibility would be to
remove duplicates by using hashes.

-- 
David Kastrup