bug#26540: 25.2; [PATCH] Add cl-set-equal to test for set equality

bug#26540: 25.2; [PATCH] Add cl-set-equal to test for set equality

[Damien Cassou]

[-- Attachment #1: Type: text/plain, Size: 355 bytes --]

 
This patch adds cl-seq-equal to test whether two lists have the 
same elements. I.e., if every element of LIST1 also appears in 
LIST2 and if every element of LIST2 also appears in LIST1. 

-- 
Damien Cassou
http://damiencassou.seasidehosting.st

"Success is the ability to go from one failure to another without
losing enthusiasm." --Winston Churchill

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: 0001-Add-cl-set-equal-to-test-for-set-equality.patch --]
[-- Type: text/x-patch, Size: 3841 bytes --]

From 2f00c34ecec39c5c90e6c3ef2f5ab40fa60979e9 Mon Sep 17 00:00:00 2001
From: Damien Cassou <damien@cassou.me>
Date: Mon, 17 Apr 2017 11:01:39 +0200
Subject: [PATCH] Add cl-set-equal to test for set equality

* lisp/emacs-lisp/cl-seq.el (cl-set-equal): Add function to compare
  two lists as if they were sets.

* test/lisp/emacs-lisp/cl-seq-tests.el (cl-set-equal): Add test for
  cl-set-equal.
---
 doc/misc/cl.texi                     |  6 ++++++
 etc/NEWS                             |  3 +++
 lisp/emacs-lisp/cl-seq.el            | 10 ++++++++++
 test/lisp/emacs-lisp/cl-seq-tests.el | 16 ++++++++++++++++
 4 files changed, 35 insertions(+)

diff --git a/doc/misc/cl.texi b/doc/misc/cl.texi
index 2339d57..aa64ae2 100644
--- a/doc/misc/cl.texi
+++ b/doc/misc/cl.texi
@@ -3917,6 +3917,12 @@ Lists as Sets
 also appears in @var{list2}.
 @end defun
 
+@defun cl-set-equal list1 list2 @t{&key :test :key}
+This function checks whether every element of @var{list1} also appears
+in @var{list2} and if every element of @var{list2} also appears in
+@var{list1}.
+@end defun
+
 @node Association Lists
 @section Association Lists
 
diff --git a/etc/NEWS b/etc/NEWS
index 76c9dbc..e22a440 100644
--- a/etc/NEWS
+++ b/etc/NEWS
@@ -874,6 +874,9 @@ instead of its first.
 \f
 * Lisp Changes in Emacs 26.1
 
+** New function 'cl-set-equal' to check if every element of LIST1 also
+appears in LIST2 and if every element of LIST2 also appears in LIST1.
+
 +++
 ** Emacs now supports records for user-defined types, via the new
 functions 'make-record', 'record', and 'recordp'.  Records are now
diff --git a/lisp/emacs-lisp/cl-seq.el b/lisp/emacs-lisp/cl-seq.el
index 67ff1a0..db4a145 100644
--- a/lisp/emacs-lisp/cl-seq.el
+++ b/lisp/emacs-lisp/cl-seq.el
@@ -923,6 +923,16 @@ cl-subsetp
 	     (null cl-list1)))))
 
 ;;;###autoload
+(defun cl-set-equal (cl-list1 cl-list2 &rest cl-keys)
+  "Return true if LIST1 and LIST2 have same elements.
+I.e., if every element of LIST1 also appears in LIST2 and if
+every element of LIST2 also appears in LIST1.
+\nKeywords supported: :test :key \n(fn LIST1 LIST2
+[KEYWORD VALUE]...)"
+  (and (apply 'cl-subsetp cl-list1 cl-list2 cl-keys)
+       (apply 'cl-subsetp cl-list2 cl-list1 cl-keys)))
+
+;;;###autoload
 (defun cl-subst-if (cl-new cl-pred cl-tree &rest cl-keys)
   "Substitute NEW for elements matching PREDICATE in TREE (non-destructively).
 Return a copy of TREE with all matching elements replaced by NEW.
diff --git a/test/lisp/emacs-lisp/cl-seq-tests.el b/test/lisp/emacs-lisp/cl-seq-tests.el
index 61e3d72..0347ca4 100644
--- a/test/lisp/emacs-lisp/cl-seq-tests.el
+++ b/test/lisp/emacs-lisp/cl-seq-tests.el
@@ -292,6 +292,22 @@ cl-seq--with-side-effects
     (should (= 1 (cl-search (nthcdr 2 list) (nthcdr 2 list2))))
     (should (= 3 (cl-search (nthcdr 2 list) list2)))))
 
+;; keywords supported: :test :key
+(ert-deftest cl-set-equal ()
+  (should     (cl-set-equal '(1 2 3) '(1 2 3)))
+  (should     (cl-set-equal '(1 2 3) '(3 2 1)))
+  (should     (cl-set-equal '(3 2 1) '(1 2 3)))
+  (should-not (cl-set-equal '(2 3) '(3 2 1)))
+  (should-not (cl-set-equal '(1 2 3) '(2 3)))
+  (should-not (cl-set-equal '("1" "2") '("2" "1") :test #'eq))
+  (should     (cl-set-equal '("1" "2") '("2" "1") :test #'equal))
+  (should-not (cl-set-equal '(1 2) '(-1 -2)))
+  (should     (cl-set-equal '(1 2) '(-1 -2) :key #'abs))
+  (should-not (cl-set-equal '(("1" 1) ("2" 1)) '(("1" 2) ("2" 2))))
+  (should-not (cl-set-equal '(("1" 1) ("2" 1)) '(("1" 2) ("2" 2)) :key #'car))
+  (should-not (cl-set-equal '(("1" 1) ("2" 1)) '(("1" 2) ("2" 2)) :test #'equal))
+  (should     (cl-set-equal '(("1" 1) ("2" 1)) '(("1" 2) ("2" 2)) :key #'car :test #'equal)))
+
 (ert-deftest cl-seq-test-bug24264 ()
   "Test for http://debbugs.gnu.org/24264 ."
   (let ((list  (append (make-list 8000005 1) '(8)))
-- 
2.9.3

bug#26540: 25.2; [PATCH] Add cl-set-equal to test for set equality

[Drew Adams]

> This patch adds cl-seq-equal to test whether two lists have the
> same elements. I.e., if every element of LIST1 also appears in
> LIST2 and if every element of LIST2 also appears in LIST1.

Common Lisp (and the Emacs emulation) already has set
functions that do this - `[cl-]set-exclusive-or', for
example.

https://www.cs.cmu.edu/Groups/AI/html/cltl/clm/node152.html

bug#26540: 25.2; [PATCH] Add cl-set-equal to test for set equality

[Damien Cassou]

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

>> This patch adds cl-seq-equal to test whether two lists have the 
>> same elements. I.e., if every element of LIST1 also appears in 
>> LIST2 and if every element of LIST2 also appears in LIST1. 
> 
> Common Lisp (and the Emacs emulation) already has set functions 
> that do this - `[cl-]set-exclusive-or', for example. 
> 
> https://www.cs.cmu.edu/Groups/AI/html/cltl/clm/node152.html 

are you saying that (1) I should propose an implementation of 
set-equal based on set-exclusive-or (I guess it's just a `not` 
call away) or (2) not propose set-equal all together? I understand 
(1), but not the reasoning behind (2). 

-- 
Damien Cassou
http://damiencassou.seasidehosting.st

"Success is the ability to go from one failure to another without
losing enthusiasm." --Winston Churchill

bug#26540: 25.2; [PATCH] Add cl-set-equal to test for set equality

[Drew Adams]

> >> This patch adds cl-seq-equal to test whether two lists have the
> >> same elements. I.e., if every element of LIST1 also appears in
> >> LIST2 and if every element of LIST2 also appears in LIST1.
> >
> > Common Lisp (and the Emacs emulation) already has set
> > functions that do this - `[cl-]set-exclusive-or', for
> > example.
> 
> are you saying that (1) I should propose an implementation of
> set-equal based on set-exclusive-or (I guess it's just a `not`
> call away) or (2) not propose set-equal all together? I understand
> (1), but not the reasoning behind (2).

I'm just pointing out that a function we already have,
and one that is used more widely by users of Common
Lisp, does the same thing - unless I'm missing something.

If people think that some users might not think to use
`set-exclusive-or' to test set equality then we could
add a `set-equal' function.  Common Lisp didn't think
so, and neither do I, but I wouldn't oppose adding it.

If we do add it, I'd imagine that the implementation
should be the same (adding `not', as you say), for
clarity and consistency - unless other things are not
equal for some reason (i.e., unless there is a good
reason not to use the existing implementation).

In sum, I don't oppose adding it.  I'm just pointing
out that we already have it, in another form.

bug#26540: 25.2; [PATCH] Add cl-set-equal to test for set equality

[Damien Cassou]

[-- Attachment #1: Type: text/plain, Size: 1113 bytes --]

Drew Adams <drew.adams@oracle.com> writes:
> I'm just pointing out that a function we already have, and one 
> that is used more widely by users of Common Lisp, does the same 
> thing - unless I'm missing something. 


I agree (except that one has opposite result).
 
> If people think that some users might not think to use 
> `set-exclusive-or' to test set equality then we could add a 
> `set-equal' function.  Common Lisp didn't think so, and neither 
> do I, but I wouldn't oppose adding it. 


At least I didn't think about using exclusive-or. Searching for 
"equal" or "same elements" in the info page (info "(cl) Lists as 
Sets") didn't help.
 
> If we do add it, I'd imagine that the implementation should be 
> the same (adding `not', as you say), for clarity and consistency 
> - unless other things are not equal for some reason (i.e., 
> unless there is a good reason not to use the existing 
> implementation). 


I updated the patch.

-- 
Damien Cassou
http://damiencassou.seasidehosting.st

"Success is the ability to go from one failure to another without
losing enthusiasm." --Winston Churchill

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: 0001-Add-cl-set-equal-to-test-for-set-equality.patch --]
[-- Type: text/x-patch, Size: 3795 bytes --]

From f3f46edeb47178ebe6dbdcbe72bf150788167dcf Mon Sep 17 00:00:00 2001
From: Damien Cassou <damien@cassou.me>
Date: Mon, 17 Apr 2017 11:01:39 +0200
Subject: [PATCH] Add cl-set-equal to test for set equality

* lisp/emacs-lisp/cl-seq.el (cl-set-equal): Add function to compare
  two lists as if they were sets.

* test/lisp/emacs-lisp/cl-seq-tests.el (cl-set-equal): Add test for
  cl-set-equal.
---
 doc/misc/cl.texi                     |  6 ++++++
 etc/NEWS                             |  3 +++
 lisp/emacs-lisp/cl-seq.el            |  9 +++++++++
 test/lisp/emacs-lisp/cl-seq-tests.el | 16 ++++++++++++++++
 4 files changed, 34 insertions(+)

diff --git a/doc/misc/cl.texi b/doc/misc/cl.texi
index 2339d57..aa64ae2 100644
--- a/doc/misc/cl.texi
+++ b/doc/misc/cl.texi
@@ -3917,6 +3917,12 @@ Lists as Sets
 also appears in @var{list2}.
 @end defun
 
+@defun cl-set-equal list1 list2 @t{&key :test :key}
+This function checks whether every element of @var{list1} also appears
+in @var{list2} and if every element of @var{list2} also appears in
+@var{list1}.
+@end defun
+
 @node Association Lists
 @section Association Lists
 
diff --git a/etc/NEWS b/etc/NEWS
index 76c9dbc..e22a440 100644
--- a/etc/NEWS
+++ b/etc/NEWS
@@ -874,6 +874,9 @@ instead of its first.
 \f
 * Lisp Changes in Emacs 26.1
 
+** New function 'cl-set-equal' to check if every element of LIST1 also
+appears in LIST2 and if every element of LIST2 also appears in LIST1.
+
 +++
 ** Emacs now supports records for user-defined types, via the new
 functions 'make-record', 'record', and 'recordp'.  Records are now
diff --git a/lisp/emacs-lisp/cl-seq.el b/lisp/emacs-lisp/cl-seq.el
index 67ff1a0..9467d41 100644
--- a/lisp/emacs-lisp/cl-seq.el
+++ b/lisp/emacs-lisp/cl-seq.el
@@ -923,6 +923,15 @@ cl-subsetp
 	     (null cl-list1)))))
 
 ;;;###autoload
+(defun cl-set-equal (cl-list1 cl-list2 &rest cl-keys)
+  "Return true if LIST1 and LIST2 have same elements.
+I.e., if every element of LIST1 also appears in LIST2 and if
+every element of LIST2 also appears in LIST1.
+\nKeywords supported: :test :key \n(fn LIST1 LIST2
+[KEYWORD VALUE]...)"
+  (not (apply 'cl-set-exclusive-or cl-list1 cl-list2 cl-keys)))
+
+;;;###autoload
 (defun cl-subst-if (cl-new cl-pred cl-tree &rest cl-keys)
   "Substitute NEW for elements matching PREDICATE in TREE (non-destructively).
 Return a copy of TREE with all matching elements replaced by NEW.
diff --git a/test/lisp/emacs-lisp/cl-seq-tests.el b/test/lisp/emacs-lisp/cl-seq-tests.el
index 61e3d72..0347ca4 100644
--- a/test/lisp/emacs-lisp/cl-seq-tests.el
+++ b/test/lisp/emacs-lisp/cl-seq-tests.el
@@ -292,6 +292,22 @@ cl-seq--with-side-effects
     (should (= 1 (cl-search (nthcdr 2 list) (nthcdr 2 list2))))
     (should (= 3 (cl-search (nthcdr 2 list) list2)))))
 
+;; keywords supported: :test :key
+(ert-deftest cl-set-equal ()
+  (should     (cl-set-equal '(1 2 3) '(1 2 3)))
+  (should     (cl-set-equal '(1 2 3) '(3 2 1)))
+  (should     (cl-set-equal '(3 2 1) '(1 2 3)))
+  (should-not (cl-set-equal '(2 3) '(3 2 1)))
+  (should-not (cl-set-equal '(1 2 3) '(2 3)))
+  (should-not (cl-set-equal '("1" "2") '("2" "1") :test #'eq))
+  (should     (cl-set-equal '("1" "2") '("2" "1") :test #'equal))
+  (should-not (cl-set-equal '(1 2) '(-1 -2)))
+  (should     (cl-set-equal '(1 2) '(-1 -2) :key #'abs))
+  (should-not (cl-set-equal '(("1" 1) ("2" 1)) '(("1" 2) ("2" 2))))
+  (should-not (cl-set-equal '(("1" 1) ("2" 1)) '(("1" 2) ("2" 2)) :key #'car))
+  (should-not (cl-set-equal '(("1" 1) ("2" 1)) '(("1" 2) ("2" 2)) :test #'equal))
+  (should     (cl-set-equal '(("1" 1) ("2" 1)) '(("1" 2) ("2" 2)) :key #'car :test #'equal)))
+
 (ert-deftest cl-seq-test-bug24264 ()
   "Test for http://debbugs.gnu.org/24264 ."
   (let ((list  (append (make-list 8000005 1) '(8)))
-- 
2.9.3

bug#26540: 25.2; [PATCH] Add cl-set-equal to test for set equality

[Drew Adams]

> > If we do add it, I'd imagine that the implementation should be
> > the same (adding `not', as you say), for clarity and consistency
> > - unless other things are not equal for some reason (i.e.,
> > unless there is a good reason not to use the existing
> > implementation).
> 
> I updated the patch.

Maybe there is a good reason not to use the existing fn.

I didn't check the patch or the implementation of
`cl-set-exclusive-or', but that function is designed not
just to test for equality but also to return the list (set)
of elements that are in only one of the argument lists.

A naive guess is that when the sets are unequal this would
be slower than just a check for equality.  You might want
to take a look.  If that's the case then a simple equality
implementation would be better (e.g. throw to a catch as
soon as we know they are unequal).

bug#26540: 25.2; [PATCH] Add cl-set-equal to test for set equality

[John Mastro]

Damien Cassou <damien@cassou.me> wrote:
>
> This patch adds cl-seq-equal to test whether two lists have the same
> elements. I.e., if every element of LIST1 also appears in LIST2 and if every
> element of LIST2 also appears in LIST1.

This is admittedly bikeshedding, for which I apologize, but I'd like to
mention the possibility of adding this to `seq' as an alternative to
adding it to `cl-lib'.

My two arguments for adding it to `seq' are:
  - This function doesn't exist in Common Lisp, so `cl-lib' seems like
    a somewhat arbitrary place for it, other than that its
    implementation uses `cl-set-exclusive-or'.
  - It could use seq.el's type dispatch

As a downside, (besides the fact that the patch adding it to `cl-lib' is
already available), `seq' doesn't have a direct equivalent to
`cl-set-exclusive-or', so adding it to `seq' is more work.

        John

bug#26540: 25.2; [PATCH] Add cl-set-equal to test for set equality

[Drew Adams]

> This is admittedly bikeshedding, for which I apologize, but I'd like to
> mention the possibility of adding this to `seq' as an alternative to
> adding it to `cl-lib'.
> 
> My two arguments for adding it to `seq' are:
>   - This function doesn't exist in Common Lisp, so `cl-lib' seems like
>     a somewhat arbitrary place for it, other than that its
>     implementation uses `cl-set-exclusive-or'.

Agreed.  This is not Common Lisp emulation.  It does not
belong in a cl*.el library and should not have the `cl-'
prefix.

bug#26540: 25.2; [PATCH] Add cl-set-equal to test for set equality

[Nicolas Petton]

[-- Attachment #1: Type: text/plain, Size: 792 bytes --]

John Mastro <john.b.mastro@gmail.com> writes:


> This is admittedly bikeshedding, for which I apologize, but I'd like to
> mention the possibility of adding this to `seq' as an alternative to
> adding it to `cl-lib'.
>
> My two arguments for adding it to `seq' are:
>   - This function doesn't exist in Common Lisp, so `cl-lib' seems like
>     a somewhat arbitrary place for it, other than that its
>     implementation uses `cl-set-exclusive-or'.
>   - It could use seq.el's type dispatch
>
> As a downside, (besides the fact that the patch adding it to `cl-lib' is
> already available), `seq' doesn't have a direct equivalent to
> `cl-set-exclusive-or', so adding it to `seq' is more work.
>

I'd also put it in seq.el, I think it's the place where it makes the
most sense.

Cheers,
Nico

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 472 bytes --]

bug#26540: 25.2; [PATCH] Add cl-set-equal to test for set equality

[Damien Cassou]

Nicolas Petton <nicolas@petton.fr> writes:
> John Mastro <john.b.mastro@gmail.com> writes: 
>> This is admittedly bikeshedding, for which I apologize, but I'd 
>> like to mention the possibility of adding this to `seq' as an 
>> alternative to adding it to `cl-lib'. 
> 
> I'd also put it in seq.el, I think it's the place where it makes 
> the most sense. 

it makes sense and I will try this way. Nevertheless, it also 
means giving up on the :key feature. I guess it's ok. 

-- 
Damien Cassou
http://damiencassou.seasidehosting.st

"Success is the ability to go from one failure to another without
losing enthusiasm." --Winston Churchill

bug#26540: 25.2; [PATCH] Add cl-set-equal to test for set equality

[Damien Cassou]

[-- Attachment #1: Type: text/plain, Size: 356 bytes --]

Damien Cassou <damien@cassou.me> writes:
> it makes sense and I will try this way. Nevertheless, it also 
> means giving up on the :key feature. I guess it's ok.  

here it is. Any feedback? 

-- 
Damien Cassou
http://damiencassou.seasidehosting.st

"Success is the ability to go from one failure to another without
losing enthusiasm." --Winston Churchill

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: 0001-Add-seq-set-equal-to-test-for-set-equality.patch --]
[-- Type: text/x-patch, Size: 4620 bytes --]

From b30eaba87be980c8fbaea3c124c3cadd9aec6fe0 Mon Sep 17 00:00:00 2001
From: Damien Cassou <damien@cassou.me>
Date: Mon, 17 Apr 2017 11:01:39 +0200
Subject: [PATCH] Add seq-set-equal to test for set equality

* lisp/emacs-lisp/seq.el (seq-set-equal): Add function to compare
  two lists as if they were sets.

* test/lisp/emacs-lisp/seq-tests.el (test-seq-set-equal): Add test for
  seq-set-equal.
---
 doc/lispref/sequences.texi        | 28 ++++++++++++++++++++++++++++
 etc/NEWS                          |  3 +++
 lisp/emacs-lisp/seq.el            |  8 ++++++++
 test/lisp/emacs-lisp/seq-tests.el | 25 +++++++++++++++++++++++++
 4 files changed, 64 insertions(+)

diff --git a/doc/lispref/sequences.texi b/doc/lispref/sequences.texi
index 93e8fa8..2f6fb1d 100644
--- a/doc/lispref/sequences.texi
+++ b/doc/lispref/sequences.texi
@@ -792,6 +792,34 @@ Sequence Functions
 
 @end defun
 
+@defun seq-set-equal sequence1 sequence2 &optional testfn
+This function checks whether every element of @var{sequence1} also
+appears in @var{sequence2} and if every element of @var{sequence2}
+also appears in @var{sequence1}.  If the optional argument
+@var{testfn} is non-@code{nil}, it is a function of two arguments to
+use instead of the default @code{equal}.
+
+@example
+@group
+(seq-set-equal '(a b c) '(c b a))
+@result{} t
+@end group
+@group
+(seq-set-equal '(a b c) '(c b))
+@result{} nil
+@end group
+@group
+(seq-set-equal '("a" "b" "c") '("c" "b" "a"))
+@result{} t
+@end group
+@group
+(seq-set-equal '("a" "b" "c") '("c" "b" "a") #'eq)
+@result{} nil
+@end group
+@end example
+
+@end defun
+
 @defun seq-position sequence elt &optional function
   This function returns the index of the first element in
 @var{sequence} that is equal to @var{elt}.  If the optional argument
diff --git a/etc/NEWS b/etc/NEWS
index 76c9dbc..9b6c89d 100644
--- a/etc/NEWS
+++ b/etc/NEWS
@@ -874,6 +874,9 @@ instead of its first.
 \f
 * Lisp Changes in Emacs 26.1
 
+** New function 'seq-set-equal' to check if every element of LIST1 also
+appears in LIST2 and if every element of LIST2 also appears in LIST1.
+
 +++
 ** Emacs now supports records for user-defined types, via the new
 functions 'make-record', 'record', and 'recordp'.  Records are now
diff --git a/lisp/emacs-lisp/seq.el b/lisp/emacs-lisp/seq.el
index 10de248..40f2988 100644
--- a/lisp/emacs-lisp/seq.el
+++ b/lisp/emacs-lisp/seq.el
@@ -355,6 +355,14 @@ seq-sort-by
                 e))
             sequence))
 
+(cl-defgeneric seq-set-equal (sequence1 sequence2 &optional testfn)
+  "Return true if SEQUENCE1 and SEQUENCE2 have same elements.
+I.e., if every element of SEQUENCE1 also appears in SEQUENCE2 and if
+every element of SEQUENCE2 also appears in SEQUENCE1.
+Equality is defined by TESTFN if non-nil or by `equal' if nil."
+  (and (seq-every-p (lambda (item1) (seq-contains sequence2 item1 testfn)) sequence1)
+       (seq-every-p (lambda (item2) (seq-contains sequence1 item2 testfn)) sequence2)))
+
 (cl-defgeneric seq-position (sequence elt &optional testfn)
   "Return the index of the first element in SEQUENCE that is equal to ELT.
 Equality is defined by TESTFN if non-nil or by `equal' if nil."
diff --git a/test/lisp/emacs-lisp/seq-tests.el b/test/lisp/emacs-lisp/seq-tests.el
index 788524b..9cc54d8 100644
--- a/test/lisp/emacs-lisp/seq-tests.el
+++ b/test/lisp/emacs-lisp/seq-tests.el
@@ -197,6 +197,31 @@ test-sequences-oddp
     (should (seq-every-p #'identity seq))
     (should (seq-every-p #'test-sequences-evenp seq))))
 
+(ert-deftest test-seq-set-equal ()
+  (with-test-sequences (seq1 '(1 2 3))
+    (should (seq-set-equal seq1 seq1))
+    (should (seq-set-equal seq1 seq1 #'eq))
+
+    (with-test-sequences (seq2 '(3 2 1))
+      (should (seq-set-equal seq1 seq2))
+      (should (seq-set-equal seq2 seq1))
+      (should (seq-set-equal seq1 seq2 #'eq))
+      (should (seq-set-equal seq2 seq1 #'eq)))
+
+    (with-test-sequences (seq2 '(3 1))
+      (should-not (seq-set-equal seq1 seq2))
+      (should-not (seq-set-equal seq2 seq1))))
+
+  (should (seq-set-equal '("a" "b" "c")
+                         '("c" "b" "a")))
+  (should-not (seq-set-equal '("a" "b" "c")
+                             '("c" "b" "a") #'eq))
+  (should-not (seq-set-equal '(("a" 1) ("b" 1) ("c" 1))
+                             '(("c" 2) ("b" 2) ("a" 2))))
+  (should (seq-set-equal '(("a" 1) ("b" 1) ("c" 1))
+                         '(("c" 2) ("b" 2) ("a" 2))
+                         (lambda (i1 i2) (equal (car i1) (car i2))))))
+
 (ert-deftest test-seq-empty-p ()
   (with-test-sequences (seq '(0))
     (should-not (seq-empty-p seq)))
-- 
2.9.3

bug#26540: 25.2; [PATCH] Add cl-set-equal to test for set equality

[Nicolas Petton]

[-- Attachment #1: Type: text/plain, Size: 943 bytes --]

Damien Cassou <damien@cassou.me> writes:

> +(cl-defgeneric seq-set-equal (sequence1 sequence2 &optional testfn)
                  ^^^^^^^^^^^^^
                  What about `seq-set-equal-p'?

> +  "Return true if SEQUENCE1 and SEQUENCE2 have same elements.
             ^^^^
             We say non-nil
             
> +I.e., if every element of SEQUENCE1 also appears in SEQUENCE2 and if
> +every element of SEQUENCE2 also appears in SEQUENCE1.

What do you think about the following instead?

  Return non-nil if SEQUENCE1 and SEQUENCE2 contain the same elements,
  regardless of the order.

> diff --git a/test/lisp/emacs-lisp/seq-tests.el b/test/lisp/emacs-lisp/seq-tests.el
> index 788524b..9cc54d8 100644
> --- a/test/lisp/emacs-lisp/seq-tests.el
> +++ b/test/lisp/emacs-lisp/seq-tests.el

All your contributions are very well tested, thank you always taking the
effort to add unit tests! :-)

Cheers,
Nico

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 472 bytes --]

bug#26540: 25.2; [PATCH] Add cl-set-equal to test for set equality

[Damien Cassou]

[-- Attachment #1: Type: text/plain, Size: 468 bytes --]

Nicolas Petton <nicolas@petton.fr> writes:
> Damien Cassou <damien@cassou.me> writes:
>> +(cl-defgeneric seq-set-equal (sequence1 sequence2 &optional 
>> testfn)
>                   ^^^^^^^^^^^^^
>                   What about `seq-set-equal-p'?
> [...]


I applied your changes and attach a new patch.


-- 
Damien Cassou
http://damiencassou.seasidehosting.st

"Success is the ability to go from one failure to another without
losing enthusiasm." --Winston Churchill

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: 0001-Add-seq-set-equal-p-to-test-for-set-equality.patch --]
[-- Type: text/x-patch, Size: 4568 bytes --]

From f63a0b5aff1a065a17169dfbd622cc7e91648195 Mon Sep 17 00:00:00 2001
From: Damien Cassou <damien@cassou.me>
Date: Mon, 17 Apr 2017 11:01:39 +0200
Subject: [PATCH] Add seq-set-equal-p to test for set equality

* lisp/emacs-lisp/seq.el (seq-set-equal-p): Add function to compare
  two lists as if they were sets.

* test/lisp/emacs-lisp/seq-tests.el (test-seq-set-equal-p): Add test
  for seq-set-equal-p.
---
 doc/lispref/sequences.texi        | 27 +++++++++++++++++++++++++++
 etc/NEWS                          |  3 +++
 lisp/emacs-lisp/seq.el            |  6 ++++++
 test/lisp/emacs-lisp/seq-tests.el | 25 +++++++++++++++++++++++++
 4 files changed, 61 insertions(+)

diff --git a/doc/lispref/sequences.texi b/doc/lispref/sequences.texi
index 93e8fa8..c7cf9f5 100644
--- a/doc/lispref/sequences.texi
+++ b/doc/lispref/sequences.texi
@@ -792,6 +792,33 @@ Sequence Functions
 
 @end defun
 
+@defun seq-set-equal-p sequence1 sequence2 &optional testfn
+This function checks whether @var{sequence1} and @var{sequence2}
+contain the same elements, regardless of the order. If the optional
+argument @var{testfn} is non-@code{nil}, it is a function of two
+arguments to use instead of the default @code{equal}.
+
+@example
+@group
+(seq-set-equal-p '(a b c) '(c b a))
+@result{} t
+@end group
+@group
+(seq-set-equal-p '(a b c) '(c b))
+@result{} nil
+@end group
+@group
+(seq-set-equal-p '("a" "b" "c") '("c" "b" "a"))
+@result{} t
+@end group
+@group
+(seq-set-equal-p '("a" "b" "c") '("c" "b" "a") #'eq)
+@result{} nil
+@end group
+@end example
+
+@end defun
+
 @defun seq-position sequence elt &optional function
   This function returns the index of the first element in
 @var{sequence} that is equal to @var{elt}.  If the optional argument
diff --git a/etc/NEWS b/etc/NEWS
index 410e681..6d0ee9b 100644
--- a/etc/NEWS
+++ b/etc/NEWS
@@ -894,6 +894,9 @@ instead of its first.
 \f
 * Lisp Changes in Emacs 26.1
 
+** New function 'seq-set-equal-p' to check if SEQUENCE1 and SEQUENCE2
+contain the same elements, regardless of the order.
+
 +++
 ** Emacs now supports records for user-defined types, via the new
 functions 'make-record', 'record', and 'recordp'.  Records are now
diff --git a/lisp/emacs-lisp/seq.el b/lisp/emacs-lisp/seq.el
index 10de248..963a1dd 100644
--- a/lisp/emacs-lisp/seq.el
+++ b/lisp/emacs-lisp/seq.el
@@ -355,6 +355,12 @@ (cl-defgeneric seq-contains (sequence elt &optional testfn)
                 e))
             sequence))
 
+(cl-defgeneric seq-set-equal-p (sequence1 sequence2 &optional testfn)
+  "Return non-nil if SEQUENCE1 and SEQUENCE2 contain the same elements, regardless of order.
+Equality is defined by TESTFN if non-nil or by `equal' if nil."
+  (and (seq-every-p (lambda (item1) (seq-contains sequence2 item1 testfn)) sequence1)
+       (seq-every-p (lambda (item2) (seq-contains sequence1 item2 testfn)) sequence2)))
+
 (cl-defgeneric seq-position (sequence elt &optional testfn)
   "Return the index of the first element in SEQUENCE that is equal to ELT.
 Equality is defined by TESTFN if non-nil or by `equal' if nil."
diff --git a/test/lisp/emacs-lisp/seq-tests.el b/test/lisp/emacs-lisp/seq-tests.el
index 788524b..495cf1e 100644
--- a/test/lisp/emacs-lisp/seq-tests.el
+++ b/test/lisp/emacs-lisp/seq-tests.el
@@ -197,6 +197,31 @@ (ert-deftest test-seq-every-p ()
     (should (seq-every-p #'identity seq))
     (should (seq-every-p #'test-sequences-evenp seq))))
 
+(ert-deftest test-seq-set-equal-p ()
+  (with-test-sequences (seq1 '(1 2 3))
+    (should (seq-set-equal-p seq1 seq1))
+    (should (seq-set-equal-p seq1 seq1 #'eq))
+
+    (with-test-sequences (seq2 '(3 2 1))
+      (should (seq-set-equal-p seq1 seq2))
+      (should (seq-set-equal-p seq2 seq1))
+      (should (seq-set-equal-p seq1 seq2 #'eq))
+      (should (seq-set-equal-p seq2 seq1 #'eq)))
+
+    (with-test-sequences (seq2 '(3 1))
+      (should-not (seq-set-equal-p seq1 seq2))
+      (should-not (seq-set-equal-p seq2 seq1))))
+
+  (should (seq-set-equal-p '("a" "b" "c")
+                           '("c" "b" "a")))
+  (should-not (seq-set-equal-p '("a" "b" "c")
+                               '("c" "b" "a") #'eq))
+  (should-not (seq-set-equal-p '(("a" 1) ("b" 1) ("c" 1))
+                               '(("c" 2) ("b" 2) ("a" 2))))
+  (should (seq-set-equal-p '(("a" 1) ("b" 1) ("c" 1))
+                           '(("c" 2) ("b" 2) ("a" 2))
+                           (lambda (i1 i2) (equal (car i1) (car i2))))))
+
 (ert-deftest test-seq-empty-p ()
   (with-test-sequences (seq '(0))
     (should-not (seq-empty-p seq)))
-- 
2.9.3

bug#26540: 25.2; [PATCH] Add cl-set-equal to test for set equality

[Nicolas Petton]

[-- Attachment #1: Type: text/plain, Size: 157 bytes --]

Damien Cassou <damien@cassou.me> writes:

> I applied your changes and attach a new patch.

Thanks!

I installed your patch in Emacs and ELPA.

Cheers,
Nico

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 472 bytes --]

bug#26540: 25.2; [PATCH] Add cl-set-equal to test for set equality

[Michael Heerdegen]

Damien Cassou <damien@cassou.me> writes:

> Damien Cassou <damien@cassou.me> writes:

> > it makes sense and I will try this way. Nevertheless, it also means
> > giving up on the :key feature. I guess it's ok.

OTOH I see no reason not to support it.  There is no reason to provide a
function in a library specializing on sequences with less features than
in some other lib.  Just my personal opinion.  Of course you can get the
effect of :key by adopting the TESTFN, but also note my other comment:

> here it is. Any feedback? 

It might be worth it to try to optimize things a bit for the most usual
TESTFNs `eq' and `equal'.  For example, try

#+begin_src emacs-lisp
(let ((s1 (number-sequence 1 10000))
      (s2 (number-sequence 1 10000)))
  (seq-set-equal s1 s2))
#+end_src

vs.

#+begin_src emacs-lisp
(let ((s1 (number-sequence 1 10000))
      (s2 (number-sequence 1 10000)))
  (seq-set-equal-2 s1 s2))
#+end_src

with this implementation using hash-tables:

#+begin_src emacs-lisp
(defun seq-set-equal-2 (sequence1 sequence2)
  (let ((table1 (make-hash-table :size (length sequence1)))
        (table2 (make-hash-table :size (length sequence2))))
    (seq-doseq (elt sequence1) (puthash elt t table1))
    (seq-doseq (elt sequence2) (puthash elt t table2))
    (and (seq-every-p (lambda (elt) (gethash elt table2)) sequence1)
         (seq-every-p (lambda (elt) (gethash elt table1)) sequence2))))
#+end_src

I guess other functions in seq.el could be optimized as well,
e.g. `seq-difference'.


Regards,

Michael.

bug#26540: 25.2; [PATCH] Add cl-set-equal to test for set equality

[Damien Cassou]

Hi Michael,

Michael Heerdegen <michael_heerdegen@web.de> writes:
> Damien Cassou <damien@cassou.me> writes: 
>> it makes sense and I will try this way. Nevertheless, it also 
>> means giving up on the :key feature. I guess it's ok. 
> 
> OTOH I see no reason not to support it.  There is no reason to 
> provide a function in a library specializing on sequences with 
> less features than in some other lib.


I agree with you that having :key would be nice. Nevertheless, my 
implementation currently relies on functions of seq.el (i.e., 
seq-contains) which would have to be adapted to support :key. I 
didn't want to do that.


> [...] with this implementation using hash-tables: 
>[] 
> #+begin_src emacs-lisp (defun seq-set-equal-2 (sequence1 
> sequence2) 
>   (let ((table1 (make-hash-table :size (length sequence1))) 
>         (table2 (make-hash-table :size (length sequence2)))) 
>     (seq-doseq (elt sequence1) (puthash elt t table1)) 
>     (seq-doseq (elt sequence2) (puthash elt t table2)) (and 
>     (seq-every-p (lambda (elt) (gethash elt table2)) sequence1) 
>          (seq-every-p (lambda (elt) (gethash elt table1)) 
>          sequence2)))) 
> #+end_src 

as far as I can tell, little effort has been put in optimizing 
seq.el the way you describe it so I guess such an implementation 
of seq-set-equal would feel a bit alien in the current code 
base. Moreover, is your implementation faster on very small sets? 
Finally, making your implementation of seq-set-equal accepting a 
TESTFN parameter would be a bit complex as you would have to pass 
that to `make-hash-table` which also requires a hash function. 

-- 
Damien Cassou
http://damiencassou.seasidehosting.st

"Success is the ability to go from one failure to another without
losing enthusiasm." --Winston Churchill

bug#26540: 25.2; [PATCH] Add cl-set-equal to test for set equality

[Michael Heerdegen]

Damien Cassou <damien@cassou.me> writes:

> > [...] with this implementation using hash-tables: [] #+begin_src
> > emacs-lisp (defun seq-set-equal-2 (sequence1 sequence2)   (let
> > ((table1 (make-hash-table :size (length sequence1)))         (table2
> > (make-hash-table :size (length sequence2))))     (seq-doseq (elt
> > sequence1) (puthash elt t table1))     (seq-doseq (elt sequence2)
> > (puthash elt t table2)) (and     (seq-every-p (lambda (elt) (gethash
> > elt table2)) sequence1)          (seq-every-p (lambda (elt) (gethash
> > elt table1))          sequence2)))) #+end_src 
>
> as far as I can tell, little effort has been put in optimizing seq.el
> the way you describe it so I guess such an implementation of
> seq-set-equal would feel a bit alien in the current code
> base. Moreover, is your implementation faster on very small sets?

Probably not.  It was just a demonstration.

> Finally, making your implementation of seq-set-equal accepting a
> TESTFN parameter would be a bit complex as you would have to pass that
> to `make-hash-table` which also requires a hash function. 

Yes, we would have to limit TESTFN to functions that are implemented as
hash table test functions.

I took the idea from `delete-dups' btw, which is optimized with hash
tables for large lists.  We allow arbitrary TESTFNs in
`seq-set-equal-p', though, in practice and with :key functions allowed,
I would expect that supporting `eq' and `equal' would cover most use
cases.  For the rest, we could still fall back to the current
implementation.


Michael.