`remove-duplicates'

`remove-duplicates'

[Lars Magne Ingebrigtsen]

Would anybody mind if I add a simple version of `remove-duplicates' to
subr.el?  I'm tired of rewriting the same loop...

It'll be one of those

(if (null (featurep 'cl))
    (progn
(defun remove-duplicates ...)

things.

-- 
(domestic pets only, the antidote for overdose, milk.)
  bloggy blog http://lars.ingebrigtsen.no/

Re: `remove-duplicates'

[Juanma Barranquero]

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))

    Juanma

Re: `remove-duplicates'

[David Kastrup]

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

RE: `remove-duplicates'

[Drew Adams]

One comment wrt adding another Emacs-Lisp function (e.g. `remove-duplicates')
that has the same name as an existing Emacs-Lisp function provided by cl.el:
Please don't do it; instead, change the name so there is no clash.

It's too late to rename the cl.el function by adding a `*' suffix or something,
unless you want to break backward compatibility.

The problem with having the same name, which already happens in a couple of
cases, is that the functions have different behavior (e.g. keywords), or at a
minimum different doc.  This is a source of confusion, if not errors (which may
not be immediately obvious).

If you call your new function `remove-dups' or something there will be no
problem.  But I'm really not trying to say anything particular about what the
proper solution is; just pointing to a potential problem that is worth avoiding.

Re: `remove-duplicates'

[Stefan Monnier]

> Would anybody mind if I add a simple version of `remove-duplicates' to
> subr.el?  I'm tired of rewriting the same loop...

We have delete-dups which seems to be good enough for most uses so far.


        Stefan

Re: `remove-duplicates'

[Lars Magne Ingebrigtsen]

Stefan Monnier <monnier@iro.umontreal.ca> writes:

> We have delete-dups which seems to be good enough for most uses so far.

Ah, right.  I'll use that instead.

-- 
(domestic pets only, the antidote for overdose, milk.)
  bloggy blog http://lars.ingebrigtsen.no/