The Equivalence contravariant functor by Mark Seemann
An introduction to the Equivalence contravariant functor for object-oriented programmers.
This article is an instalment in an article series about contravariant functors. It assumes that you've read the introduction. In previous articles, you saw examples of the Command Handler and Specification contravariant functors. This article presents another example.
In a recent article I described how I experimented with removing the id property from a JSON representation in a REST API. I also mentioned that doing that made one test fail. In this article you'll see the failing test and how the Equivalence contravariant functor can improve the situation.
Baseline #
Before I made the change, the test in question looked like this:
[Theory] [InlineData(1049, 19, 00, "juliad@example.net", "Julia Domna", 5)] [InlineData(1130, 18, 15, "x@example.com", "Xenia Ng", 9)] [InlineData( 956, 16, 55, "kite@example.edu", null, 2)] [InlineData( 433, 17, 30, "shli@example.org", "Shanghai Li", 5)] public async Task PostValidReservationWhenDatabaseIsEmpty( int days, int hours, int minutes, string email, string name, int quantity) { var at = DateTime.Now.Date + new TimeSpan(days, hours, minutes, 0); var db = new FakeDatabase(); var sut = new ReservationsController( new SystemClock(), new InMemoryRestaurantDatabase(Grandfather.Restaurant), db); var dto = new ReservationDto { Id = "B50DF5B1-F484-4D99-88F9-1915087AF568", At = at.ToString("O"), Email = email, Name = name, Quantity = quantity }; await sut.Post(dto); var expected = new Reservation( Guid.Parse(dto.Id), at, new Email(email), new Name(name ?? ""), quantity); Assert.Contains(expected, db.Grandfather); }
You can find this test in the code base that accompanies my book Code That Fits in Your Head, although I've slightly simplified the initialisation of expected since I froze the code for the manuscript. I've already discussed this particular test in the articles Branching tests, Waiting to happen, and Parametrised test primitive obsession code smell. It's the gift that keeps giving.
It's a state-based integration test that verifies the state of the FakeDatabase after 'posting' a reservation to 'the REST API'. I'm using quotes because the test doesn't really perform an HTTP POST request (it's not a self-hosted integration test). Rather, it directly calls the Post method on the sut. In the assertion phase, it uses Back Door Manipulation (as xUnit Test Patterns terms it) to verify the state of the Fake db.
If you're wondering about the Grandfather property, it represents the original restaurant that was grandfathered in when I expanded the REST API to a multi-tenant service.
Notice, particularly, the use of dto.Id when defining the expected reservation.
Brittle assertion #
When I made the Id property internal, this test no longer compiled. I had to delete the assignment of Id, which also meant that I couldn't use a deterministic Guid to define the expected value. While I could create an arbitrary Guid, that would never pass the test, since the Post method also generates a new Guid.
In order to get to green as quickly as possible, I rewrote the assertion:
Assert.Contains( db.Grandfather, r => DateTime.Parse(dto.At, CultureInfo.InvariantCulture) == r.At && new Email(dto.Email) == r.Email && new Name(dto.Name ?? "") == r.Name && dto.Quantity == r.Quantity);
This passed the test so that I could move on. It may even be the simplest thing that could possibly work, but it's brittle and noisy.
It's brittle because it explicitly considers the four properties At, Email, Name, and Quantity of the Reservation class. What happens if you add a new property to Reservation? What happens if you have similar assertions scattered over the code base?
This is one reason that DRY also applies to unit tests. You want to have as few places as possible that you have to edit when making changes. Otherwise, the risk increases that you forget one or more.
Not only is the assertion brittle - it's also noisy, because it's hard to read. There's parsing, null coalescing and object initialisation going on in those four lines of Boolean operations. Perhaps it'd be better to extract a well-named helper method, but while I'm often in favour of doing that, I'm also a little concerned that too many ad-hoc helper methods obscure something essential. After all:
"Abstraction is the elimination of the irrelevant and the amplification of the essential"
The hardest part of abstraction is striking the right balance. Does a well-named helper method effectively communicate the essentials while eliminating only the irrelevant. While I favour good names over bad names, I'm also aware that good names are skin-deep. If I can draw on a universal abstraction rather than coming up with an ad-hoc name, I prefer doing that.
Which universal abstraction might be useful in this situation?
Relaxed comparison #
The baseline version of the test relied on the structural equality of the Reservation class:
public override bool Equals(object? obj) { return obj is Reservation reservation && Id.Equals(reservation.Id) && At == reservation.At && EqualityComparer<Email>.Default.Equals(Email, reservation.Email) && EqualityComparer<Name>.Default.Equals(Name, reservation.Name) && Quantity == reservation.Quantity; }
This implementation was auto-generated by a Visual Studio Quick Action. From C# 9, I could also have made Reservation a record, in which case the compiler would be taking care of implementing Equals.
The Reservation class already defines the canonical way to compare two reservations for equality. Why can't we use that?
The PostValidReservationWhenDatabaseIsEmpty test can no longer use the Reservation class' structural equality because it doesn't know what the Id is going to be.
One way to address this problem is to inject a hypothetical IGuidGenerator dependency into ReservationsController. I consider this a valid alternative, since the Controller already takes an IClock dependency. I might be inclined towards such a course of action for other reasons, but here I wanted to explore other options.
Can we somehow reuse the Equals implementation of Reservation, but relax its behaviour so that it doesn't consider the Id?
This would be what Ted Neward called negative variability - the ability to subtract from an existing feature. As he implied in 2010, normal programming languages don't have that capability. That strikes me as true in 2021 as well.
The best we can hope for, then, is to put the required custom comparison somewhere central, so that at least it's not scattered across the entire code base. Since the test uses xUnit.net, a class that implements IEqualityComparer<Reservation> sounds like just the right solution.
This is definitely doable, but it's odd having to define a custom equality comparer for a class that already has structural equality. In the context of the PostValidReservationWhenDatabaseIsEmpty test, we understand the reason, but for a future team member who may encounter the class out of context, it might be confusing.
Are there other options?
Reuse #
It turns out that, by lucky accident, the code base already contains an equality comparer that almost fits:
internal sealed class ReservationDtoComparer : IEqualityComparer<ReservationDto> { public bool Equals(ReservationDto? x, ReservationDto? y) { var datesAreEqual = Equals(x?.At, y?.At); if (!datesAreEqual && DateTime.TryParse(x?.At, out var xDate) && DateTime.TryParse(y?.At, out var yDate)) datesAreEqual = Equals(xDate, yDate); return datesAreEqual && Equals(x?.Email, y?.Email) && Equals(x?.Name, y?.Name) && Equals(x?.Quantity, y?.Quantity); } public int GetHashCode(ReservationDto obj) { var dateHash = obj.At?.GetHashCode(StringComparison.InvariantCulture); if (DateTime.TryParse(obj.At, out var dt)) dateHash = dt.GetHashCode(); return HashCode.Combine(dateHash, obj.Email, obj.Name, obj.Quantity); } }
This class already compares two reservations' dates, emails, names, and quantities, while ignoring any IDs. Just what we need?
There's only one problem. ReservationDtoComparer compares ReservationDto objects - not Reservation objects.
Would it be possible to somehow, on the spot, without writing a new class, transform ReservationDtoComparer to an IEqualityComparer<Reservation>?
Well, yes it is.
Contravariant functor #
We can contramap an IEqualityComparer<ReservationDto> to a IEqualityComparer<Reservation> because equivalence gives rise to a contravariant functor.
In order to enable contravariant mapping, you must add a ContraMap method:
public static class Equivalance { public static IEqualityComparer<T1> ContraMap<T, T1>( this IEqualityComparer<T> source, Func<T1, T> selector) where T : notnull { return new ContraMapComparer<T, T1>(source, selector); } private sealed class ContraMapComparer<T, T1> : IEqualityComparer<T1> where T : notnull { private readonly IEqualityComparer<T> source; private readonly Func<T1, T> selector; public ContraMapComparer(IEqualityComparer<T> source, Func<T1, T> selector) { this.source = source; this.selector = selector; } public bool Equals([AllowNull] T1 x, [AllowNull] T1 y) { if (x is null && y is null) return true; if (x is null || y is null) return false; return source.Equals(selector(x), selector(y)); } public int GetHashCode(T1 obj) { return source.GetHashCode(selector(obj)); } } }
Since the IEqualityComparer<T> interface defines two methods, the selector must contramap the behaviour of both Equals and GetHashCode. Fortunately, that's possible.
Notice that, as explained in the overview article, in order to map from an IEqualityComparer<T> to an IEqualityComparer<T1>, the selector has to go the other way: from T1 to T. How this is possible will become more apparent with an example, which will follow later in the article.
Identity law #
A ContraMap method with the right signature isn't enough to be a contravariant functor. It must also obey the contravariant functor laws. As usual, it's proper computer-science work to actually prove this, but you can write some tests to demonstrate the identity law for the IEqualityComparer<T> interface. In this article, you'll see parametrised tests written with xUnit.net. First, the identity law:
[Theory] [InlineData("18:30", 1, "18:30", 1)] [InlineData("18:30", 2, "18:30", 2)] [InlineData("19:00", 1, "19:00", 1)] [InlineData("18:30", 1, "19:00", 1)] [InlineData("18:30", 2, "18:30", 1)] public void IdentityLaw(string time1, int size1, string time2, int size2) { var sut = new TimeDtoComparer(); T id<T>(T x) => x; IEqualityComparer<TimeDto>? actual = sut.ContraMap<TimeDto, TimeDto>(id); var dto1 = new TimeDto { Time = time1, MaximumPartySize = size1 }; var dto2 = new TimeDto { Time = time2, MaximumPartySize = size2 }; Assert.Equal(sut.Equals(dto1, dto2), actual.Equals(dto1, dto2)); Assert.Equal(sut.GetHashCode(dto1), actual.GetHashCode(dto1)); }
In order to observe that the two comparers have identical behaviours, the test must invoke both the Equals and the GetHashCode methods on both sut and actual to assert that the two different objects produce the same output.
All test cases pass.
Composition law #
Like the above example, you can also write a parametrised test that demonstrates that ContraMap obeys the composition law for contravariant functors:
[Theory] [InlineData(" 7:45", "18:13")] [InlineData("18:13", "18:13")] [InlineData("22" , "22" )] [InlineData("22:32", "22" )] [InlineData( "9" , "9" )] [InlineData( "9" , "8" )] public void CompositionLaw(string time1, string time2) { IEqualityComparer<TimeDto> sut = new TimeDtoComparer(); Func<string, (string, int)> f = s => (s, s.Length); Func<(string s, int i), TimeDto> g = t => new TimeDto { Time = t.s, MaximumPartySize = t.i }; IEqualityComparer<string>? projection1 = sut.ContraMap((string s) => g(f(s))); IEqualityComparer<string>? projection2 = sut.ContraMap(g).ContraMap(f); Assert.Equal( projection1.Equals(time1, time2), projection2.Equals(time1, time2)); Assert.Equal( projection1.GetHashCode(time1), projection2.GetHashCode(time1)); }
This test defines two local functions, f and g. Once more, you can't directly compare methods for equality, so instead you have to call both Equals and GetHashCode on projection1 and projection2 to verify that they return the same values.
They do.
Relaxed assertion #
The code base already contains a function that converts Reservation values to ReservationDto objects:
public static ReservationDto ToDto(this Reservation reservation) { if (reservation is null) throw new ArgumentNullException(nameof(reservation)); return new ReservationDto { Id = reservation.Id.ToString("N"), At = reservation.At.ToIso8601DateTimeString(), Email = reservation.Email.ToString(), Name = reservation.Name.ToString(), Quantity = reservation.Quantity }; }
Given that it's possible to map from Reservation to ReservationDto, it's also possible to map equality comparers in the contrary direction: from IEqualityComparer<ReservationDto> to IEqualityComparer<Reservation>. That's just what the PostValidReservationWhenDatabaseIsEmpty test needs!
Most of the test stays the same, but you can now write the assertion as:
var expected = new Reservation( Guid.NewGuid(), at, new Email(email), new Name(name ?? ""), quantity); Assert.Contains( expected, db.Grandfather, new ReservationDtoComparer().ContraMap((Reservation r) => r.ToDto()));
Instead of using the too-strict equality comparison of Reservation, the assertion now takes advantage of the relaxed, test-specific comparison of ReservationDto objects.
What's not to like?
To be truthful, this probably isn't a trick I'll perform often. I think it's fair to consider contravariant functors an advanced programming concept. On a team, I'd be concerned that colleagues wouldn't understand what's going on here.
The purpose of this article series isn't to advocate for this style of programming. It's to show some realistic examples of contravariant functors.
Even in Haskell, where contravariant functors are en explicit part of the base package, I can't recall having availed myself of this functionality.
Equivalence in Haskell #
The Haskell Data.Functor.Contravariant module defines a Contravariant type class and some instances to go with it. One of these is a newtype called Equivalence, which is just a wrapper around a -> a -> Bool.
In Haskell, equality is normally defined by the Eq type class. You can trivially 'promote' any Eq instance to an Equivalence instance using the defaultEquivalence value.
To illustrate how this works in Haskell, you can reproduce the two reservation types:
data Reservation = Reservation { reservationID :: UUID, reservationAt :: LocalTime, reservationEmail :: String, reservationName :: String, reservationQuantity :: Int } deriving (Eq, Show) data ReservationJson = ReservationJson { jsonAt :: String, jsonEmail :: String, jsonName :: String, jsonQuantity :: Double } deriving (Eq, Show, Read, Generic)
The ReservationJson type doesn't have an ID, whereas Reservation does. Still, you can easily convert from Reservation to ReservationJson:
reservationToJson :: Reservation -> ReservationJson reservationToJson (Reservation _ at email name q) = ReservationJson (show at) email name (fromIntegral q)
Now imagine that you have two reservations that differ only on reservationID:
reservation1 :: Reservation reservation1 = Reservation (fromWords 3822151499 288494060 2147588346 2611157519) (LocalTime (fromGregorian 2021 11 11) (TimeOfDay 12 30 0)) "just.inhale@example.net" "Justin Hale" 2 reservation2 :: Reservation reservation2 = Reservation (fromWords 1263859666 288625132 2147588346 2611157519) (LocalTime (fromGregorian 2021 11 11) (TimeOfDay 12 30 0)) "just.inhale@example.net" "Justin Hale" 2
If you compare these two values using the standard equality operator, they're (not surprisingly) not the same:
> reservation1 == reservation2 False
Attempting to compare them using the default Equivalence value doesn't help, either:
> (getEquivalence $ defaultEquivalence) reservation1 reservation2 False
But if you promote the comparison to Equivalence and then contramap it with reservationToJson, they do look the same:
> (getEquivalence $ contramap reservationToJson $ defaultEquivalence) reservation1 reservation2 True
This Haskell example is equivalent in spirit to the above C# assertion.
Notice that Equivalence is only a wrapper around any function of the type a -> a -> Bool. This corresponds to the IEqualityComparer interface's Equals method. On the other hand, Equivalence has no counterpart to GetHashCode - that's a .NETism.
When using Haskell as inspiration for identifying universal abstractions, it's not entirely clear how Equivalence is similar to IEqualityComparer<T>. While a -> a -> Bool is isomorphic to its Equals method, and thus gives rise to a contravariant functor, what about the GetHashCode method?
As this article has demonstrated, it turned out that it's possible to also contramap the GetHashCode method, but was that just a fortunate accident, or is there something more fundamental going on?
Conclusion #
Equivalence relations give rise to a contravariant functor. In this article, you saw how this property can be used to relax assertions in unit tests.
Strictly speaking, an equivalence relation is exclusively a function that compares two values to return a Boolean value. No GetHashCode method is required. That's a .NET-specific implementation detail that, unfortunately, has been allowed to leak into the object base class. It's not part of the concept of an equivalence relation, but still, it's possible to form a contravariant functor from IEqualityComparer<T>. Is this just a happy coincidence, or could there be something more fundamental going on?
Read on.
