bug#50928: remove-dups

bug#50928: remove-dups

[Tak Kunihiro]

I wanted to delete duplicated items from a list non-destructively.
It took me a while to find out how to do so.

(cl-remove-duplicates list :test 'equal)
(delete-dups (copy-sequence list))

I think it is handy to have something like below in subr.el.
Too obvious?

#+begin_src emacs-lisp
(defun remove-dups (list)
  "Remove 'equal' duplicates from LIST non-destructively.
Note that `delete-dups' deletes duplicates destructively."
  (delete-dups (copy-sequence list)))
#+end_src

bug#50928: remove-dups

[Lars Ingebrigtsen]

Tak Kunihiro <tkk@misasa.okayama-u.ac.jp> writes:

> I wanted to delete duplicated items from a list non-destructively.
> It took me a while to find out how to do so.
>
> (cl-remove-duplicates list :test 'equal)
> (delete-dups (copy-sequence list))
>
> I think it is handy to have something like below in subr.el.
> Too obvious?
>
> #+begin_src emacs-lisp
> (defun remove-dups (list)
>   "Remove 'equal' duplicates from LIST non-destructively.
> Note that `delete-dups' deletes duplicates destructively."
>   (delete-dups (copy-sequence list)))
> #+end_src

This is basically seq-uniq:

---
seq-uniq is an autoloaded compiled Lisp function in ‘seq.el’.

(seq-uniq SEQUENCE &optional TESTFN)
---

The seq library has a pretty full set of sequence functions, some of
which overlaps with the older functions like `delete-dups'.

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

bug#50928: remove-dups

[Dmitry Gutov]

On 01.10.2021 15:45, Lars Ingebrigtsen wrote:
> This is basically seq-uniq:
> 
> ---
> seq-uniq is an autoloaded compiled Lisp function in ‘seq.el’.
> 
> (seq-uniq SEQUENCE &optional TESTFN)
> ---
> 
> The seq library has a pretty full set of sequence functions, some of
> which overlaps with the older functions like `delete-dups'.

seq-uniq is O(N^2), though, so it's going to be less efficient than

   (delete-dups (copy-sequence list))

I think the idea was to add specialized faster implementations for 
different data types, but that hasn't happened, so far.

And its signature (accepting testfn) might make the obvious optimization 
which delete-dups uses (caching the "known" set in a hash table) not 
feasible. Maybe we could use a hash table for a limited set of testfn's.

bug#50928: [External] : bug#50928: remove-dups

[Drew Adams]

FWIW, I use this.  I don't recall whether I borrowed
it from somewhere or just wrote it from scratch.

(defun my-remove-dups (sequence &optional test)
  "Copy of SEQUENCE with duplicate elements removed.
Optional arg TEST is the test function.  If nil, test with `equal'.
See `make-hash-table' for possible values of TEST."
  (setq test  (or test  #'equal))
  (let ((htable  (make-hash-table :test test)))
    (loop 
     for elt in sequence
     unless (gethash elt htable)
     do     (puthash elt elt htable)
     finally return (loop for i being the hash-values in htable collect i))))

bug#50928: [External] : bug#50928: remove-dups

[Thierry Volpiatto]

Drew Adams <drew.adams@oracle.com> writes:

> FWIW, I use this.  I don't recall whether I borrowed
> it from somewhere or just wrote it from scratch.
>
> (defun my-remove-dups (sequence &optional test)
>   "Copy of SEQUENCE with duplicate elements removed.
> Optional arg TEST is the test function.  If nil, test with `equal'.
> See `make-hash-table' for possible values of TEST."
>   (setq test  (or test  #'equal))
>   (let ((htable  (make-hash-table :test test)))
>     (loop 
>      for elt in sequence
>      unless (gethash elt htable)
       collect (puthash elt elt htable))))

Looks like a old version of `helm-fast-remove-dups`, no need to loop
again in hash-table and using cl-loop is better.

-- 
Thierry

bug#50928: remove-dups

[Tak Kunihiro]

> Tak Kunihiro <tkk@misasa.okayama-u.ac.jp> writes:
> 
>> I wanted to delete duplicated items from a list non-destructively.
>> It took me a while to find out how to do so.
>>
>> (cl-remove-duplicates list :test 'equal)
>> (delete-dups (copy-sequence list))
>>
>> I think it is handy to have something like below in subr.el.
>> Too obvious?
>>
>> (defun remove-dups (list)
>>   "Remove 'equal' duplicates from LIST non-destructively.
>> Note that `delete-dups' deletes duplicates destructively."
>>   (delete-dups (copy-sequence list)))
> 
> This is basically seq-uniq:

Thank you to let me know.  Now I can find its existence in (info
"(elisp) Sequence Functions").  I wonder how I could have reached to
the function by myself.

How did you find it? (apropos-documentation "duplicate")?

bug#50928: remove-dups

[Lars Ingebrigtsen]

Tak Kunihiro <tkk@misasa.okayama-u.ac.jp> writes:

> Thank you to let me know.  Now I can find its existence in (info
> "(elisp) Sequence Functions").  I wonder how I could have reached to
> the function by myself.
>
> How did you find it? (apropos-documentation "duplicate")?

I just...  knew about seq.el.  The cross-referencing between the older
sequence functions and seq.el is rather lacking -- basically all these
older functions should probably reference something in seq.el in their
doc strings.

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

bug#50928: remove-dups

[Tak Kunihiro]

>> Now I can find its existence in (info
>> "(elisp) Sequence Functions").  I wonder how I could have reached to
>> the function by myself.
>>
>> How did you find it? (apropos-documentation "duplicate")?
> 
> I just...  knew about seq.el.  The cross-referencing between the older
> sequence functions and seq.el is rather lacking -- basically all these
> older functions should probably reference something in seq.el in their
> doc strings.

How about something like below?

commit xxx
Author: yyy
Date:   zzz

    Add references to a newer function `seq-uniq' in seq.el
    
    * lisp/subr.el (delete-dups):
    * doc/lispref/lists.texi (Sets And Lists):
    * doc/lispref/lists.texi (delete-dups):  Refer to `seq-uniq' (bug#50928).

diff --git a/lisp/subr.el b/lisp/subr.el
index e4819c4b2b..228d2e0c22 100644
--- a/lisp/subr.el
+++ b/lisp/subr.el
@@ -696,7 +696,7 @@ delete-dups
   "Destructively remove `equal' duplicates from LIST.
 Store the result in LIST and return it.  LIST must be a proper list.
 Of several `equal' occurrences of an element in LIST, the first
-one is kept."
+one is kept.  See `seq-uniq' for non-destructive operation."
   (let ((l (length list)))
     (if (> l 100)
         (let ((hash (make-hash-table :test #'equal :size l))

diff --git a/doc/lispref/lists.texi b/doc/lispref/lists.texi
index 75641256b6..66c556ecd0 100644
--- a/doc/lispref/lists.texi
+++ b/doc/lispref/lists.texi
@@ -1227,13 +1227,13 @@ Sets And Lists
 @cindex lists as sets
 @cindex sets
 
-  A list can represent an unordered mathematical set---simply consider a
-value an element of a set if it appears in the list, and ignore the
-order of the list.  To form the union of two sets, use @code{append} (as
-long as you don't mind having duplicate elements).  You can remove
-@code{equal} duplicates using @code{delete-dups}.  Other useful
-functions for sets include @code{memq} and @code{delq}, and their
-@code{equal} versions, @code{member} and @code{delete}.
+  A list can represent an unordered mathematical set---simply consider
+a value an element of a set if it appears in the list, and ignore the
+order of the list.  To form the union of two sets, use @code{append}
+(as long as you don't mind having duplicate elements).  You can remove
+@code{equal} duplicates using @code{delete-dups} or @code{seq-uniq}.
+Other useful functions for sets include @code{memq} and @code{delq},
+and their @code{equal} versions, @code{member} and @code{delete}.
 
 @cindex CL note---lack @code{union}, @code{intersection}
 @quotation
@@ -1489,7 +1489,8 @@ Sets And Lists
 This function destructively removes all @code{equal} duplicates from
 @var{list}, stores the result in @var{list} and returns it.  Of
 several @code{equal} occurrences of an element in @var{list},
-@code{delete-dups} keeps the first one.
+@code{delete-dups} keeps the first one.  See @code{seq-uniq} for
+non-destructive operation.
 @end defun
 
   See also the function @code{add-to-list}, in @ref{List Variables},

bug#50928: remove-dups

[Lars Ingebrigtsen]

Tak Kunihiro <tkk@misasa.okayama-u.ac.jp> writes:

> How about something like below?

Thanks; applied to Emacs 28.

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