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

Previous Next

To add a comment to this bug, you must first unarchive it, by sending
a message to control AT debbugs.gnu.org, with unarchive 26540 in the body.
You can then email your comments to 26540 AT debbugs.gnu.org in the normal way.

Toggle the display of automated, internal messages from the tracker.

Message #5 received at submit <at> debbugs.gnu.org (full text, mbox):

From: Damien Cassou <damien <at> cassou.me>
To: bug-gnu-emacs <at> gnu.org
Subject: 25.2; [PATCH] Add cl-set-equal to test for set equality
Date: Mon, 17 Apr 2017 11:16:10 +0200

[Message part 1 (text/plain, inline)]

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

[0001-Add-cl-set-equal-to-test-for-set-equality.patch (text/x-patch, attachment)]

Message #8 received at 26540 <at> debbugs.gnu.org (full text, mbox):

From: Drew Adams <drew.adams <at> oracle.com>
To: Damien Cassou <damien <at> cassou.me>, 26540 <at> debbugs.gnu.org
Subject: RE: bug#26540: 25.2; [PATCH] Add cl-set-equal to test for set equality
Date: Mon, 17 Apr 2017 06:55:20 -0700 (PDT)

> 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

Message #11 received at 26540 <at> debbugs.gnu.org (full text, mbox):

From: Damien Cassou <damien <at> cassou.me>
To: Drew Adams <drew.adams <at> oracle.com>
Cc: 26540 <at> debbugs.gnu.org
Subject: Re: bug#26540: 25.2; [PATCH] Add cl-set-equal to test for set equality
Date: Tue, 18 Apr 2017 13:21:41 +0200

Drew Adams <drew.adams <at> 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

Message #14 received at 26540 <at> debbugs.gnu.org (full text, mbox):

From: Drew Adams <drew.adams <at> oracle.com>
To: Damien Cassou <damien <at> cassou.me>
Cc: 26540 <at> debbugs.gnu.org
Subject: RE: bug#26540: 25.2; [PATCH] Add cl-set-equal to test for set equality
Date: Tue, 18 Apr 2017 07:00:52 -0700 (PDT)

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

Message #17 received at 26540 <at> debbugs.gnu.org (full text, mbox):

From: Damien Cassou <damien <at> cassou.me>
To: Drew Adams <drew.adams <at> oracle.com>
Cc: 26540 <at> debbugs.gnu.org
Subject: RE: bug#26540: 25.2; [PATCH] Add cl-set-equal to test for set equality
Date: Tue, 18 Apr 2017 16:40:19 +0200

[Message part 1 (text/plain, inline)]

Drew Adams <drew.adams <at> 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

[0001-Add-cl-set-equal-to-test-for-set-equality.patch (text/x-patch, attachment)]

Message #20 received at 26540 <at> debbugs.gnu.org (full text, mbox):

From: John Mastro <john.b.mastro <at> gmail.com>
To: 26540 <at> debbugs.gnu.org
Cc: Damien Cassou <damien <at> cassou.me>
Subject: Re: bug#26540: 25.2; [PATCH] Add cl-set-equal to test for set equality
Date: Tue, 18 Apr 2017 13:13:46 -0700

Damien Cassou <damien <at> 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

Message #23 received at 26540 <at> debbugs.gnu.org (full text, mbox):

From: Drew Adams <drew.adams <at> oracle.com>
To: Damien Cassou <damien <at> cassou.me>
Cc: 26540 <at> debbugs.gnu.org
Subject: RE: bug#26540: 25.2; [PATCH] Add cl-set-equal to test for set equality
Date: Tue, 18 Apr 2017 14:49:35 -0700 (PDT)

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

Message #26 received at 26540 <at> debbugs.gnu.org (full text, mbox):

From: Drew Adams <drew.adams <at> oracle.com>
To: John Mastro <john.b.mastro <at> gmail.com>, 26540 <at> debbugs.gnu.org
Cc: Damien Cassou <damien <at> cassou.me>
Subject: RE: bug#26540: 25.2; [PATCH] Add cl-set-equal to test for set equality
Date: Tue, 18 Apr 2017 14:53:50 -0700 (PDT)

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

Message #29 received at 26540 <at> debbugs.gnu.org (full text, mbox):

From: Nicolas Petton <nicolas <at> petton.fr>
To: John Mastro <john.b.mastro <at> gmail.com>, 26540 <at> debbugs.gnu.org
Cc: Damien Cassou <damien <at> cassou.me>
Subject: Re: bug#26540: 25.2; [PATCH] Add cl-set-equal to test for set equality
Date: Wed, 19 Apr 2017 11:39:00 +0200

[Message part 1 (text/plain, inline)]

John Mastro <john.b.mastro <at> 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

[signature.asc (application/pgp-signature, inline)]

Message #32 received at 26540 <at> debbugs.gnu.org (full text, mbox):

From: Damien Cassou <damien <at> cassou.me>
To: Nicolas Petton <nicolas <at> petton.fr>, John Mastro <john.b.mastro <at> gmail.com>,
 26540 <at> debbugs.gnu.org
Subject: Re: bug#26540: 25.2; [PATCH] Add cl-set-equal to test for set equality
Date: Wed, 19 Apr 2017 12:43:59 +0200

Nicolas Petton <nicolas <at> petton.fr> writes:
> John Mastro <john.b.mastro <at> 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

Message #35 received at 26540 <at> debbugs.gnu.org (full text, mbox):

From: Damien Cassou <damien <at> cassou.me>
To: Nicolas Petton <nicolas <at> petton.fr>, John Mastro <john.b.mastro <at> gmail.com>,
 26540 <at> debbugs.gnu.org
Subject: Re: bug#26540: 25.2; [PATCH] Add cl-set-equal to test for set equality
Date: Wed, 19 Apr 2017 13:39:11 +0200

[Message part 1 (text/plain, inline)]

Damien Cassou <damien <at> 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

[0001-Add-seq-set-equal-to-test-for-set-equality.patch (text/x-patch, attachment)]

Message #38 received at 26540 <at> debbugs.gnu.org (full text, mbox):

From: Nicolas Petton <nicolas <at> petton.fr>
To: Damien Cassou <damien <at> cassou.me>, John Mastro <john.b.mastro <at> gmail.com>,
 26540 <at> debbugs.gnu.org
Subject: Re: bug#26540: 25.2; [PATCH] Add cl-set-equal to test for set equality
Date: Wed, 19 Apr 2017 16:41:17 +0200

[Message part 1 (text/plain, inline)]

Damien Cassou <damien <at> 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

[signature.asc (application/pgp-signature, inline)]

Message #41 received at 26540 <at> debbugs.gnu.org (full text, mbox):

From: Michael Heerdegen <michael_heerdegen <at> web.de>
To: Damien Cassou <damien <at> cassou.me>
Cc: John Mastro <john.b.mastro <at> gmail.com>, Nicolas Petton <nicolas <at> petton.fr>,
 26540 <at> debbugs.gnu.org
Subject: Re: bug#26540: 25.2; [PATCH] Add cl-set-equal to test for set equality
Date: Wed, 19 Apr 2017 23:19:03 +0200

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

> Damien Cassou <damien <at> 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.

Message #44 received at 26540 <at> debbugs.gnu.org (full text, mbox):

From: Damien Cassou <damien <at> cassou.me>
To: Nicolas Petton <nicolas <at> petton.fr>, John Mastro <john.b.mastro <at> gmail.com>,
 26540 <at> debbugs.gnu.org
Subject: Re: bug#26540: 25.2; [PATCH] Add cl-set-equal to test for set equality
Date: Wed, 03 May 2017 15:02:28 +0200

[Message part 1 (text/plain, inline)]

Nicolas Petton <nicolas <at> petton.fr> writes:
> Damien Cassou <damien <at> 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

[0001-Add-seq-set-equal-p-to-test-for-set-equality.patch (text/x-patch, attachment)]

Message #47 received at 26540 <at> debbugs.gnu.org (full text, mbox):

From: Damien Cassou <damien <at> cassou.me>
To: Michael Heerdegen <michael_heerdegen <at> web.de>
Cc: John Mastro <john.b.mastro <at> gmail.com>, Nicolas Petton <nicolas <at> petton.fr>,
 26540 <at> debbugs.gnu.org
Subject: Re: bug#26540: 25.2; [PATCH] Add cl-set-equal to test for set equality
Date: Wed, 03 May 2017 15:12:05 +0200

Hi Michael,

Michael Heerdegen <michael_heerdegen <at> web.de> writes:
> Damien Cassou <damien <at> 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

Message #50 received at 26540 <at> debbugs.gnu.org (full text, mbox):

From: Nicolas Petton <nicolas <at> petton.fr>
To: Damien Cassou <damien <at> cassou.me>, John Mastro <john.b.mastro <at> gmail.com>,
 26540 <at> debbugs.gnu.org
Cc: 26540-done <at> debbugs.gnu.org
Subject: Re: bug#26540: 25.2; [PATCH] Add cl-set-equal to test for set equality
Date: Thu, 04 May 2017 11:41:00 +0200

[Message part 1 (text/plain, inline)]

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

> I applied your changes and attach a new patch.

Thanks!

I installed your patch in Emacs and ELPA.

Cheers,
Nico

[signature.asc (application/pgp-signature, inline)]

Message #58 received at 26540 <at> debbugs.gnu.org (full text, mbox):

From: Michael Heerdegen <michael_heerdegen <at> web.de>
To: Damien Cassou <damien <at> cassou.me>
Cc: John Mastro <john.b.mastro <at> gmail.com>, Nicolas Petton <nicolas <at> petton.fr>,
 26540 <at> debbugs.gnu.org
Subject: Re: bug#26540: 25.2; [PATCH] Add cl-set-equal to test for set equality
Date: Thu, 11 May 2017 21:42:46 +0200

Damien Cassou <damien <at> 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.

Previous Next

GNU bug tracking system
Copyright (C) 1999 Darren O. Benham, 1997,2003 nCipher Corporation Ltd, 1994-97 Ian Jackson.