"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)

## No comments:

## Post a Comment