Partager via

Object oriented programming and binary functions

  • Article

Ran into an interesting problem while trying to implement the latest function on my ICollection interface:

        /// <summary>

        ///

        /// </summary>

        /// <param name="element"></param>

        /// <returns></returns>

        bool Contains(A element);

Seemed like a pretty understandable operation to have on a collection.  I started writing the documentation for it and had something similar to:

true if item is found in the Collection; otherwise, false.

However i realized that that definition wasn't sufficient.  What did it mean to be “in” the collection.  I tried to write it using simple logical statement.  i.e.

S.Contains(a) <==> “There exists an x in S such that x == a”

However, i came up with several definitions:

1. S.Contains(a) <==> “There exists an x in S such that x == a”

2. S.Contains(a) <==> “There exists an x in S such that x.Equals(a)”

3. S.Contains(a) <==> “There exists an x in S such that a.Equals(x)”

4. S.Contains(a) <==> “There exists an x in S such that object.Equals(a, x)”

5. S.Contains(a) <==> “There exists an x in S such that object.Equals(x, a)”

Each of these definitions are fairly reasonable, and yet have extremely different semantic meanings.  One could argue that 4 and 5 have the same meaning when you use well behaved objects.  I.e. objects that respect the Equals invariant: “x.Equals(y) returns the same value as y.Equals(x).”  However 1 is completely different from 2-5, and 2-3 have issues with null checks.  Because i don't want to place any restrictions on null (as I view it as a perfectly valid collections value) then i didn't want to deal with the NullReferenceExceptions issues that could come from 2/3.  This left me 1/4/5.  However, i felt uneasy picking amongst them.  What if someone wanted to implement an IdentityCollection.  That is a collection which used reference identity to perform it's operations.  The issue here is that i want to define “Contains” in the following manner

S.Contains(a) <==> “There exists an x in S and a function “bool Equals(a,b)” such that Equals(x, a)”

Which woudl imply that Contains should be written:

bool Contains(A element, BinaryEquality equals);

Where BinaryEquality is a delegate of the form “bool BinaryEquality<A>(A a, A b)”

However, this gets very clunky.  Just to test containment I need to pass this delegate around.  It also means that in order to preserve invariants about the collection the consumer needs to hold onto the right delegate.  So it seems like this delegate is something that should be internalized into the collection.  i.e. ArrayCollection would now take as a parameter that delegate.  However, if one wasn't specified it would presumably default to one of the sensible defaults listed above.  This would allow for the flexible definition of Equals, while allowing simple access to the collection.

Comments

  • Anonymous
    May 18, 2004
    Why not let the user pass an IComparer to your constructor? If one isn't specified, default to either option 4 or 5 (and if anyone writes code where it makes a difference which one you pick, they've got bigger problems than your collection).
  • Anonymous
    May 18, 2004
    Joe: because I'm defining the interface. The interface can't put constraints on your constructor.
  • Anonymous
    May 20, 2004
    How about another meaning:
    S.Contains(a) <==> “There exists an x in S such that object.ReferenceEquals(x, a)”
    This means that there's never a value comparison, but only a reference comparison.
  • Anonymous
    May 20, 2004
    The comment has been removed
  • Anonymous
    July 19, 2004
    The comment has been removed