System.Object.Equals must be Reflexive, Symmetry and Transitive

norman — Fri, 20 Apr 2007 07:25:00 GMT

You just override System.Object.Equals, or create some other method to check whether member-wise-values of two objects are the same, how would you ensure your implementation of equivalent in the method is correct? You should go back to mathematical definition of Equivalence Relation. You should do some kind of formal methods. I’ll bring back your memory on what Equivalence Relation is and show you simple code to test your equivalent relation implementation.

Distinguishing objects by Equivalence

Just now, a friend of mine asked how to compare the values (values of members) of two different instances of the same .NET class (class means reference type). In other words, he wants to know how to compare the two instances of a reference type as if they are value type. He just wants to compare their values. He has tried the “Equals” method, but it always returns “False” whenever he give two instances with the same values. What happened?

In .NET, objects can be distinguished by Identity and by Equivalence. To distinguish by identity, you use the static method System.Object.ReferenceEquals. This method will compare the address of two object references, doesn’t care what the type is. This method will return true if the two references actually refer to the exactly same object.

While to distinguish by equivalence, you use System.Object.Equals. For value type (such as struct), as identity means nothing, this method simply compare two objects by member-wise comparison. But for reference type, it will also compare the identity! That’s why my friends always got “False” whenever he passes two instances of a reference type that member-wise values are the same.

So, he cannot use System.Object.Equals but he must override this method to check the member values one by one. Actually, this check can be done outside of the class, but it results ugly code. You may have this “check code” all over the place. So, put this responsibility in your class would be more elegant. If you don’t want to override System.Object.Equals, and prefer to make another method let say named “IsEqual” is up to you.

The operations to check equivalence is up to you. It depends on your business logic/domain problems. You may want to compare all member values or whatever. Here I only interest on how you would ensure the equivalent implementation you make is correct, that is meet the mathematical definition of Equivalence Relation.

Note that if you’re overriding System.Object.Equals you should override System.Object.GetHashCode. Again, I’m not going to talk about it either.

Equivalence Relation

Equivalence Relation is defined as Relation that is Reflexive, Symmetric and Transitive. J What?

Well, just move on reading…

Let say we have a non empty set S. A relation R on S is an equivalent relation if:

1. For every a member S, aRa (Reflexive).

2. For a and b both members of S, if aRb, then bRa (Symmetric).

3. For a, b and c are members of S, if aRb and bRc, then aRc (Transitive).

In short, equivalence relation is classification of objects which they are in some way “alike”.

Here’s some examples to give you a better understanding:

1. “=”, yes the old “sama dengan” that you learn since you’re a kid. J

a=a for every a member S. (Reflexive)

If a=b, then b=a. (Symmetric)

If a=b and b=c then a=c. (Transitive)

So, "=" is an equivalence relation.

2. “Is the same species as” in the classification of animals by species is also an equivalent relation in the set of animals.

3. “subset”. “subset” is reflexive and transitive. But not symmetric. So, “subset” relation is NOT an equivalent relation.

a is subset of a (reflexive).

If a is subset of b, and b is subset of c, then a subset of c. (Transitive)

if a is subset of b does not imply b is subset of a. (NOT symmetric)

So, got the point what “equivalence” means? In the above example, the “subset” relation does not meet the property to be recognized as an Equivalence Relation.

Now, we’d like to see whether “Equals” method that you make are Reflexive, Symmetry and Transitive. Let’s see the code.

The Code

Let say I have a class as follow:

public class MyClass

{

public string MyMember;

public string MyOtherMember;

public int AnotherOneMember;

public override bool Equals(object obj)

{

MyClass mc = (MyClass)obj;

return

this.MyMember == mc.MyMember &&

this.MyOtherMember == mc.MyOtherMember &&

this.AnotherOneMember == mc.AnotherOneMember;

}

public override int GetHashCode()

{

return base.GetHashCode();

}

Here I override the System.Object.Equals method. I simply compare the value of each member of the two objects. You may define your own operations within the method depends on your domain problem. But your implementation of “equals” should pass this test:

class Program

{

static void Main(string[] args)

{

MyClass mc1 = new MyClass();

mc1.MyMember = "1";

mc1.MyOtherMember = "1";

mc1.AnotherOneMember = 1;

MyClass mcsatu = new MyClass();

mcsatu.MyMember = "1";

mcsatu.MyOtherMember = "1";

mcsatu.AnotherOneMember = 1;

MyClass mcone = new MyClass();

mcone.MyMember = "1";

mcone.MyOtherMember = "1";

mcone.AnotherOneMember = 1;

EquivalentRelationChecker checker =

new EquivalentRelationChecker(mc1, mcsatu, mcone);

checker.AssertEquivalentRelation();

}

Where EquivalentRelationChecker is this class below:

public class EquivalentRelationChecker

{

object o1, o2, o3;

public EquivalentRelationChecker(object o1, object o2, object o3)

{

if(o1!=null && o2!=null & o3!=null)

{

this.o1 = o1;

this.o2 = o2;

this.o3 = o3;

}

public void AssertEquivalentRelation()

{

AssertReflexive();

AssertSymmetric();

AssertTransitive();

}

private void AssertReflexive()

{

Debug.Assert(o1.Equals(o1));

}

private void AssertSymmetric()

{

if(o1.Equals(o2))

Debug.Assert(o2.Equals(o1));

}

private void AssertTransitive()

{

if(o1.Equals(o2) && o2.Equals(o3))

Debug.Assert(o1.Equals(o3));

}

Note the methods: AssertReflexive, AssertSymmetric and AssertTransitive.

You can use this class to check whether your implementation of “equals” fits the definition of Equivalence Relation.

The Rant

My implementation in overriding the Equals method is damn simple as it’s just a toy illustration. Yours might be more complex. But still any implementation of System.Object.Equals must be Reflexive, Symmetric and Transitive. So you can test your implementation with the also simple EquivalentRelationChecker class above. The class might be simple, but the point here is you should really understand what equivalent means.

Formal Methods in programming is important. So, don’t throw away your Mathematical knowledge & skill. Keep your mathematical maturity even if you’re now only an Enterprise Developer. J Ha..ha..ha..

Share this post: | | | |

Norman Sasono : C#, System.Object, Equals

System.Object.Equals must be Reflexive, Symmetry and Transitive

Distinguishing objects by Equivalence

Equivalence Relation

The Code

The Rant