IComparable Implies Transitivity
Lately, I've been doing comparisons of DateTimes and TimeSpans, and I've been sorely missing functionality for working with ranges, selecting the minimum and maximum, etc. Since both types implement IComparable<T>, I got to think about if I should create a little helper library which could perform these operations on any IComparable type. While a practical consideration tells me that I wouldn't find it worthwhile to have to reference an external library each time I have to make a simple comparison, there's also a more theoretical consideration.
The documentation of IComparable<T> almost says it: "[The interface can be used for] purposes such as sorting" (my emphasis), which seem to imply that there's a hidden requirement that any type implementing the interface does so in a transitive way.
In case you've forgotten what transitivity means, let's relive a bit of simple algebra: A relation is said to be transitive if the following is true for all possible elements: If A relates to B, and B relates to C, then A relates to C. Operations such as greater than and less than are transitive.
What would happen if an IComparable<T> implementation isn't transitive? Let's look at the simple game of Rock, Paper, Scissors for an example (as a completely unrelated tangent, I have bad experiences with this game: When we had to name our child, my wife and I couldn't agree on the surname, so we finally decided to resolve it by Rock, Paper, Scissors - how mature is that? After five nerve-wracking plays, my wife won...). In this game, Rock beats Scissors, and Scissors beat Paper, but this does not imply that Rock beats Paper - quite the opposite is true.
Consider this rather crude implementation of the game:
public class RockPaperScissor : IComparable<RockPaperScissor>
{
private string value_;
public readonly static RockPaperScissor Rock =
new RockPaperScissor("Rock");
public readonly static RockPaperScissor Paper =
new RockPaperScissor("Paper");
public readonly static RockPaperScissor Scissors =
new RockPaperScissor("Scissors");
private RockPaperScissor(string value)
{
this.value_ = value;
}
public override string ToString()
{
return this.value_;
}
#region IComparable<RockPaperScissor> Members
public int CompareTo(RockPaperScissor other)
{
switch (this.value_)
{
case "Rock":
switch (other.value_)
{
case "Rock":
return 0;
case "Paper":
return -1;
case "Scissors":
return 1;
default:
break;
}
break;
case "Paper":
switch (other.value_)
{
case "Rock":
return 1;
case "Paper":
return 0;
case "Scissors":
return -1;
default:
break;
}
break;
case "Scissors":
switch (other.value_)
{
case "Rock":
return -1;
case "Paper":
return 1;
case "Scissors":
return 0;
default:
break;
}
break;
default:
break;
}
throw new ArgumentException();
}
#endregion
}
Due to the circulare nature of the relation between Rock, Paper and Scissors, this is a non-transitive implementation of IComparable<T>. Any time you compare two instances if this class with another instance, you get the expected result, but what happens when, say, you try to sort them?
List<RockPaperScissor> l = new List<RockPaperScissor>();
l.Add(RockPaperScissor.Paper);
l.Add(RockPaperScissor.Rock);
l.Add(RockPaperScissor.Scissors);
l.Sort();
In this case, the sorted sequence becomes: Scissors, Rock, Paper. On a binary basis, the relation still holds true: Scissors are beaten by Rock, and Rock is beaten by Paper, but we still must not conclude that Scissors are beaten by Paper, although the list seems to imply this.
Additionally, if I change the initial sequence, the sorted list is also different:
List<RockPaperScissor> l = new List<RockPaperScissor>();
l.Add(RockPaperScissor.Rock);
l.Add(RockPaperScissor.Paper);
l.Add(RockPaperScissor.Scissors);
l.Sort();
In this case, the sorted sequence is Rock, Paper, Scissors, which is different than before. Although the binary relations still hold true, the list now implies that Rock is the lowest value, and Scissors the highest.
At least, we should be thankful that the Sort method doesn't throw an exception - or should we? In fact, I would have preferred an exception, as this would very clearly have indicated to me that I was trying to perform an operation that is logically incorrect, but how would the Sort method know that the RockPaperScissor class is intransitive?
The moral of the story is this: Only implement IComparable<T> if your type is transitive; otherwise, you may run into some unexpected behavior when you use it.
Comments
- Anonymous
July 31, 2006
Actually, transitivity is part of the contract of IComparable<T> and IComparable.
From the MSDN documentation for the CompareTo method (http://msdn2.microsoft.com/en-us/library/43hc6wht.aspx):
"If A.CompareTo(B) returns a value x that is not equal to zero, and B.CompareTo(C) returns a value y of the same sign as x, then A.CompareTo(C) is required to return a value of the same sign as x and y." - Anonymous
July 31, 2006
Ah, yes, and so it is. Thank you for pointing that out :)