A more understandable IComparable

"Any fool can write code that a computer can understand. Good programmers write code that humans can understand." - Martin Fowler

In the .NET framework the IComparable<T> interface is used to compare values:

public interface IComparable<T> {
  int CompareTo(T other);
}

The comparison is done with the CompareTo method. It returns zero if the current object is equal to the passed in parameter; a negative number if it's less than the parameter; and a positive number if it's greater than it. That's a very non-intuitive return value, reminiscent of the C strcmp function. I know that this scheme is already ingrained in our brains, but it creates code that's not directly decipherable:

static int BinarySearch<T>(IList<T> list, T target) where T : IComparable<T> {
  if (list == null) throw new ArgumentNullException("list");
  int lower = 0;
  int upper = list.Count - 1;
  while (lower <= upper) {
    int middle = lower + (upper - lower) / 2;
    int compare = target.CompareTo(list[middle]);
    if (compare == 0) return middle;
    if (compare < 0) upper = middle - 1;
    else lower = middle + 1;
  }
  return -1;
}

...

  int[] mySortedArray = ...

  int indexOfTheAnswer = BinarySearch(mySortedArray, 42);

(Note: this is just an example, there're already binary searches implementations in classes Array and List<T>.)

Wouldn't it be nicer to use the comparison operators instead of the clumsy CompareTo method? C# doesn't support extension operators, so in order to provide the operators to any IComparable<T>, a wrapper type must be used:

public class ComparableWithOperators<T> where T : IComparable<T> {
  T _comparable;
  public ComparableWithOperators(T comparable) {
    if (comparable == null) throw new ArgumentNullException("comparable");
    _comparable = comparable;
  }

  public static implicit operator ComparableWithOperators<T>(T comparable) {
    return new ComparableWithOperators<T>(comparable);
  }
  public static bool operator <(ComparableWithOperators<T> left, ComparableWithOperators<T> right) {
    return left._comparable.CompareTo(right._comparable) < 0;
  }
  public static bool operator >(ComparableWithOperators<T> left, ComparableWithOperators<T> right) {
    return left._comparable.CompareTo(right._comparable) > 0;
  }
  public static bool operator <=(ComparableWithOperators<T> left, ComparableWithOperators<T> right) {
    return left._comparable.CompareTo(right._comparable) <= 0;
  }
  public static bool operator >=(ComparableWithOperators<T> left, ComparableWithOperators<T> right) {
    return left._comparable.CompareTo(right._comparable) >= 0;
  }
  public static bool operator ==(ComparableWithOperators<T> left, ComparableWithOperators<T> right) {
    return left._comparable.CompareTo(right._comparable) == 0;
  }
  public static bool operator !=(ComparableWithOperators<T> left, ComparableWithOperators<T> right) {
    return left._comparable.CompareTo(right._comparable) != 0;
  }

  ...
}

This class implements the comparison operators for itself, and since there's also an implicit cast operator from a T, which is constrained to be an IComparable<T>, it can also compare itself to any IComparable<T>. So, the binary search example can now be changed to this:

static int BinarySearch<T>(IList<T> list, ComparableWithOperators<T> target) where T : IComparable<T> {
  if (list == null) throw new ArgumentNullException("list");
  int lower = 0;
  int upper = list.Count - 1;
  while (lower <= upper) {
    int middle = lower + (upper - lower) / 2;
    var candidate = list[middle];
    if (target == candidate) return middle;
    if (target < candidate) upper = middle - 1;
    else lower = middle + 1;
  }
  return -1;
}

...

  int[] mySortedArray = ...

  int indexOfTheAnswer = BinarySearch<int>(mySortedArray, 42);

But now the caller must provide the type parameter to the method, because the compiler's type inference can't figure it out. Also, sometimes you already have an IComparable<T>, and to use the operators in the same context, you'd need to convert it to the wrapper class:

IComparable<T> comparable = ...
ComparableWithOperators<T> comparableWithOperators = comparable;

To make this statement read better, a converter extension method can be used:

public static class ComparableExtensions {
  public static ComparableWithOperators<T> WithOperators<T>(this T self) where T : IComparable<T> {
    if (self == null) throw new ArgumentNullException();
    return self;
  }
}

Now the statement will read:

IComparable<T> comparable = ...
var comparableWithOperators = comparable.WithOperators();

And the binary search can be implemented like this:

static int BinarySearch<T>(IList<T> list, T target) where T : IComparable<T> {
  if (list == null) throw new ArgumentNullException("list");
  int lower = 0;
  int upper = list.Count - 1;
  while (lower <= upper) {
    int middle = lower + (upper - lower) / 2;
    var candidate = list[middle].WithOperators();
    if (target == candidate) return middle;
    if (target < candidate) upper = middle - 1;
    else lower = middle + 1;
  }
  return -1;
}

This solution also alleviates the requirements for new classes that implement IComparable<T>. They don't need to provide the comparison operators by themselves anymore, which would add a lot of boilerplate code. The same logic can be used to tackle the IEquatable<T> interface as well.

Note that F# has a (meta) generic type constraint, named comparison, which gives us the desired syntax out of the box:

let BinarySearch<'a when 'a : comparison>(list: IList<'a>, target: 'a) =
  if list = null then raise(ArgumentNullException("list"))
  let rec Loop(lower, upper) =
    if (lower <= upper) then
      let middle = lower + (upper - lower) / 2
      let candidate = list.[middle]
      if (candidate = target) then middle
      elif (target < candidate) then Loop(lower, middle - 1)
      else Loop(middle + 1, upper)
    else -1
  Loop(0, list.Count - 1)