Bug in sets module? Equal sets aren't equal

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
6 messages Options
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Bug in sets module? Equal sets aren't equal

Hugo Mills-2
   I've just turned up this little problem:

hrm@ruth:~/nightglass/software/childe$ erl
Erlang/OTP 18 [erts-7.2] [source] [64-bit] [smp:2:2] [async-threads:10] [kernel-poll:false]
3> sets:from_list([[2, 2], [2, -2]]) =:= sets:from_list([[2, -2], [2, 2]]).
false

   Is this expected behaviour, or a bug in the sets module?

   How should I compare sets for equality? There's no equality
comparison function in the module. (I can see any number of solutions
I could roll myself, but they're all a bit ugly).

   Hugo.

--
Hugo Mills             | I am an opera lover from planet Zog. Take me to your
hugo@... carfax.org.uk | lieder.
http://carfax.org.uk/  |
PGP: E2AB1DE4          |

_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions

signature.asc (853 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Bug in sets module? Equal sets aren't equal

Alex S.

20 февр. 2017 г., в 16:58, Hugo Mills <[hidden email]> написал(а):

sets:from_list([[2, 2], [2, -2]]) =:= sets:from_list([[2, -2], [2, 2]]).

The onyl way to compare them for equality would be elementwise anyway, i.e. I'd roll with sets:to_list, it’s about as optimal as it gets.

_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Bug in sets module? Equal sets aren't equal

Hugo Mills-2
On Mon, Feb 20, 2017 at 05:11:25PM +0300, Alex S. wrote:
>
> > 20 февр. 2017 г., в 16:58, Hugo Mills <[hidden email]> написал(а):
> >
> > sets:from_list([[2, 2], [2, -2]]) =:= sets:from_list([[2, -2], [2, 2]]).
>
> The onyl way to compare them for equality would be elementwise anyway, i.e. I'd roll with sets:to_list, it’s about as optimal as it gets.

   No, that's not going to work:

1> sets:to_list(sets:from_list([[2, 2], [2, -2]])).
[[2,2],[2,-2]]
2> sets:to_list(sets:from_list([[2, -2], [2, 2]])).
[[2,-2],[2,2]]

   It looks like the best you can do is this:

sets:size(A) =:= sets:size(B) and sets:is_subset(A, B).

   Hugo.

--
Hugo Mills             | Great films about cricket: Umpire of the Rising Sun
hugo@... carfax.org.uk |
http://carfax.org.uk/  |
PGP: E2AB1DE4          |

_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions

signature.asc (853 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Bug in sets module? Equal sets aren't equal

Ladislav Lenart
In reply to this post by Hugo Mills-2
Hello.

What about this:

sets:size(S1) == sets:size(S2) andalso sets:is_subset(S1, S2)

?

This seems rather elegant, at least to me :-)

Note however that I am not sure what the function sets:is_subset/2 returns for two empty sets (I do not have Erlang available at the moment to test it).

HTH,

Ladislav Lenart


______________________________________________________________

> Od: "Alex S." <[hidden email]>
> Komu: Hugo Mills <[hidden email]>
> Datum: 20.02.2017 15:11
> Předmět: Re: [erlang-questions] Bug in sets module? Equal sets aren't equal
>
> CC: <[hidden email]>
>
>> 20 февр. 2017 г., в 16:58, Hugo Mills <[hidden email]> написал(а):
>>
>> sets:from_list([[2, 2], [2, -2]]) =:= sets:from_list([[2, -2], [2, 2]]).
>
>The onyl way to compare them for equality would be elementwise anyway, i.e. I'd roll with sets:to_list, it’s about as optimal as it gets.
>
>----------
>
>_______________________________________________
>erlang-questions mailing list
>[hidden email]
>http://erlang.org/mailman/listinfo/erlang-questions
>
>
_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Bug in sets module? Equal sets aren't equal

Hugo Mills-2
On Mon, Feb 20, 2017 at 03:32:56PM +0100, [hidden email] wrote:
> Hello.
>
> What about this:
>
> sets:size(S1) == sets:size(S2) andalso sets:is_subset(S1, S2)
>
> ?
>
> This seems rather elegant, at least to me :-)

   It was my fallback solution, too.

> Note however that I am not sure what the function sets:is_subset/2 returns for two empty sets (I do not have Erlang available at the moment to test it).

1> sets:is_subset(sets:new(), sets:new()).
true

so that edge case works, too.

   Hugo.

> HTH,
>
> Ladislav Lenart
>
>
> ______________________________________________________________
> > Od: "Alex S." <[hidden email]>
> > Komu: Hugo Mills <[hidden email]>
> > Datum: 20.02.2017 15:11
> > Předmět: Re: [erlang-questions] Bug in sets module? Equal sets aren't equal
> >
> > CC: <[hidden email]>
> >
> >> 20 февр. 2017 г., в 16:58, Hugo Mills <[hidden email]> написал(а):
> >>
> >> sets:from_list([[2, 2], [2, -2]]) =:= sets:from_list([[2, -2], [2, 2]]).
> >
> >The onyl way to compare them for equality would be elementwise anyway, i.e. I'd roll with sets:to_list, it’s about as optimal as it gets.
> >
> >----------
> >
> >_______________________________________________
> >erlang-questions mailing list
> >[hidden email]
> >http://erlang.org/mailman/listinfo/erlang-questions
> >
> >
--
Hugo Mills             | Great films about cricket: Umpire of the Rising Sun
hugo@... carfax.org.uk |
http://carfax.org.uk/  |
PGP: E2AB1DE4          |

_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions

signature.asc (853 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Bug in sets module? Equal sets aren't equal

Richard A. O'Keefe-2
In reply to this post by Hugo Mills-2


On 21/02/17 2:58 AM, Hugo Mills wrote:

About a problem that occurs in practically every programming language
that has a built-in structural equality, going back to Lisp.

The problem is that we have an ABSTRACT data type A
with a CONCRETE representation C such that

for all x in C there is a unique y in A such that x represents y

for all y in A there is some x in C such that x represents y

-- if we didn't have these laws C wouldn't be a concrete
representation for A --

BUT

exists y in A such that #{x in C | x represents y} > 1

some abstract value has multiple representations.

Perhaps the simplest example of this is the queue-as-back-to-back
lists example, where A = sequence of T and
C = { list(T), list(T) } such that {X,Y} represents X ++ reverse(Y).

Then trivially {[],[1]} and {[1],[]} represent the same sequence.

If you have a typed language like Haskell or an OO language like
Smalltalk so that you can redefine equality for C to match equality
for A, you're away laughing.

If there is a built-in structural equality like EQUAL in Lisp
or = (==) in Prolog, or the analogue in Erlang, then your
program is ALWAYS using equality of representations.

That means that when you have such a data type, you HAVE to
write your own equality function for it, and you HAVE to remember
to call that function instead of the built-in equality.

Sometimes C may be a canonical representation for A.
For example, if A is set of T and C is strictly increasing
list of T, then representations are unique and we don't need
to distinguish between equality wrt A and equality wrt C.



To put it another way, it is a DEFECT in Erlang's set module
that there is no sets:equal(S1, S2).

The same defect is present in ordsets, there is no
ordsets:equal(S1, S2).  Wait, didn't I just say that the
ordered representation is canonical?  Yes, if done right,
but ordsets is defined to use ==, so [1] and [1.0] are,
as far as ordsets is concerned, the same set.

1> X = ordsets:from_list([1]).
[1]
2> Y = ordsets:from_list([1.0]).
[1.0]
3> ordsets:is_subset(X, Y).
true
4> ordsets:is_subset(Y, X).
true
5> X == Y.
true
6> X =:= Y.
false

If you were thinking of having a set of ordsets, think again.

The same defect applies to gb_sets where there is no
gb_sets:equal(S1, S2).

>    Is this expected behaviour, or a bug in the sets module?

In a sense, both.  It is expected behaviour that equality of
concrete representations is a refinement of equality of
abstract values.  It is a bug that there is no sets:equal/2
to both solve the problem and by its presence in the interface
remind you that the problem exists.

_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions
Loading...