Tuple bifunctor by Mark Seemann
A Pair (a two-tuple) forms a bifunctor. An article for object-oriented programmers.
This article is an instalment in an article series about bifunctors. In the previous overview, you learned about the general concept of a bifunctor. In practice, there's two useful bifunctor instances: pairs (two-tuples) and Either. In this article, you'll see how a pair is a bifunctor, and in the next article, you'll see how Either fits the same abstraction.
Tuple as a functor #
You can treat a normal pair (two-tuple) as a functor by mapping one of the elements, while keeping the other generic type fixed. In Haskell, when you have types with multiple type arguments, you often 'fix' the types from the left, leaving the right-most type free to vary. Doing this for a pair, which in C# has the type Tuple<T, U>, this means that tuples are functors if we keep T fixed and enable translation of the second element from U1 to U2.
This is easy to implement with a standard Select extension method:
public static Tuple<T, U2> Select<T, U1, U2>( this Tuple<T, U1> source, Func<U1, U2> selector) { return Tuple.Create(source.Item1, selector(source.Item2)); }
You simply return a new tuple by carrying source.Item1 over without modification, while on the other hand calling selector with source.Item2. Here's a simple example, which also highlights that C# understands functors:
var t = Tuple.Create("foo", 42); var actual = from i in t select i % 2 == 0;
Here, actual is a Tuple<string, bool> with the values "foo" and true. Inside the query expression, i is an int, and the select expression returns a bool value indicating whether the number is even or odd. Notice that the string in the first element disappears inside the query expression. It's still there, but the code inside the query expression can't see "foo".
Mapping the first element #
There's no technical reason why the mapping has to be over the second element; it's just how Haskell does it by convention. There are other, more philosophical reasons for that convention, but in the end, they boil down to the ultimately arbitrary cultural choice of reading from left to right (in Western scripts).
You can translate the first element of a tuple as easily:
public static Tuple<T2, U> SelectFirst<T1, T2, U>( this Tuple<T1, U> source, Func<T1, T2> selector) { return Tuple.Create(selector(source.Item1), source.Item2); }
While, technically, you can call this method Select, this can confuse the C# compiler's overload resolution system - at least if you have a tuple of two identical types (e.g. Tuple<int, int> or Tuple<string, string>). In order to avoid that sort of confusion, I decided to give the method another name, and in keeping with how C# LINQ methods tend to get names, I thought SelectFirst sounded reasonable.
In Haskell, this function is called first, and is part of the Bifunctor type class:
Prelude Data.Bifunctor> first (even . length) ("foo", 42)
(False,42)
In C#, you can perform the same translation using the above SelectFirst extension method:
var t = Tuple.Create("foo", 42); var actual = t.SelectFirst(s => s.Length % 2 == 0);
This also returns a Tuple<bool, int> containing the values false and 42. Notice that in this case, the first element "foo" is translated into false (because its length is odd), while the second element 42 carries over unchanged.
Mapping the second element #
You've already seen how the above Select method maps over the second element of a pair. This means that you can already map over both dimensions of the bifunctor, but perhaps, for consistency's sake, you'd also like to add an explicit SelectSecond method. This is now trivial to implement, since it can delegate its work to Select:
public static Tuple<T, U2> SelectSecond<T, U1, U2>( this Tuple<T, U1> source, Func<U1, U2> selector) { return source.Select(selector); }
There's no separate implementation; the only thing this method does is to delegate work to the Select method. It's literally the Select method, just with another name.
Clearly, you could also have done it the other way around: implement SelectSecond and then call it from Select.
The SelectSecond method works as you'd expect:
var t = Tuple.Create("foo", 1337); var actual = t.SelectSecond(i => i % 2 == 0);
Again, actual is a tuple containing the values "foo" and false, because 1337 isn't even.
This fits with the Haskell implementation, where SelectSecond is called second:
Prelude Data.Bifunctor> second even ("foo", 1337)
("foo",False)
The result is still a pair where the first element is "foo" and the second element False, exactly like in the C# example.
Mapping both elements #
With SelectFirst and SelectSecond, you can trivially implement SelectBoth:
public static Tuple<T2, U2> SelectBoth<T1, T2, U1, U2>( this Tuple<T1, U1> source, Func<T1, T2> selector1, Func<U1, U2> selector2) { return source.SelectFirst(selector1).SelectSecond(selector2); }
This method takes two translations, selector1 and selector2, and first uses SelectFirst to project along the first axis, and then SelectSecond to map the second dimension.
This implementation creates an intermediary pair that callers never see, so this could theoretically be inefficient. In this article, however, I want to show you that it's possible to implement SelectBoth based on SelectFirst and SelectSecond. In the next article, you'll see how to do it the other way around.
Using SelectBoth is easy:
var t = Tuple.Create("foo", 42); var actual = t.SelectBoth(s => s.First(), i => i % 2 == 0);
This translation returns a pair where the first element is 'f' and the second element is true. This is because the first lambda expression s => s.First() returns the first element of the input string "foo", whereas the second lambda expression i => i % 2 == 0 determines that 42 is even.
In Haskell, SelectBoth is called bimap:
Prelude Data.Bifunctor> bimap head even ("foo", 42)
('f',True)
The return value is consistent with the C# example, since the input is also equivalent.
Identity laws #
Pairs obey all the bifunctor laws. While it's formal work to prove that this is the case, you can get an intuition for it via examples. Often, I use a property-based testing library like FsCheck or Hedgehog to demonstrate (not prove) that laws hold, but in this article, I'll keep it simple and only cover each law with a parametrised test.
private static T Id<T>(T x) => x; [Theory] [InlineData("foo", 42)] [InlineData("bar", 1337)] [InlineData("foobar", 0)] [InlineData("ploeh", 7)] [InlineData("fnaah", -6)] public void SelectFirstObeysFirstFunctorLaw(string first, int second) { var t = Tuple.Create(first, second); Assert.Equal(t, t.SelectFirst(Id)); }
This test uses xUnit.net's [Theory] feature to supply a small set of example input values. It defines the identity function as a private function called Id, since C# doesn't come equipped with such a function in the Base Class Library.
The test simply creates a tuple with the input values and verifies that the original tuple t is equal to the tuple projected over the first axis with the Id function.
Likewise, the first functor law applies when translating over the second dimension:
[Theory] [InlineData("foo", 42)] [InlineData("bar", 1337)] [InlineData("foobar", 0)] [InlineData("ploeh", 7)] [InlineData("fnaah", -6)] public void SelectSecondObeysFirstFunctorLaw(string first, int second) { var t = Tuple.Create(first, second); Assert.Equal(t, t.SelectSecond(Id)); }
This is the same test as the previous test, with the only exception that it calls SelectSecond instead of SelectFirst.
Since SelectBoth in this example is implemented by composing SelectFirst and SelectSecond, you should expect it to obey the general identity law for bifunctors. It does, but it's always nice to see it with your own eyes:
[Theory] [InlineData("foo", 42)] [InlineData("bar", 1337)] [InlineData("foobar", 0)] [InlineData("ploeh", 7)] [InlineData("fnaah", -6)] public void SelectBothObeysIdentityLaw(string first, int second) { var t = Tuple.Create(first, second); Assert.Equal(t, t.SelectBoth(Id, Id)); }
Here you can see that projecting over both dimensions with the identity function returns the original tuple.
Consistency law #
In general, it shouldn't matter whether you map with SelectBoth or a combination of SelectFirst and SelectSecond:
[Theory] [InlineData("foo", 42)] [InlineData("bar", 1337)] [InlineData("foobar", 0)] [InlineData("ploeh", 7)] public void ConsistencyLawHolds(string first, int second) { Func<string, bool> f = string.IsNullOrWhiteSpace; Func<int, DateTime> g = i => new DateTime(i); var t = Tuple.Create(first, second); Assert.Equal( t.SelectBoth(f, g), t.SelectSecond(g).SelectFirst(f)); Assert.Equal( t.SelectFirst(f).SelectSecond(g), t.SelectSecond(g).SelectFirst(f)); }
This example creates two functions f and g. The first function, f, is just an alias for string.IsNullOrWhiteSpace, although I want to stress that it's just an example. The law should hold for any two (pure) functions. The second function, g, creates a new DateTime object from an integer, using one of the DateTime constructor overloads.
The test then verifies that you get the same result from calling SelectBoth as when you call SelectFirst followed by SelectSecond, or the other way around.
Composition laws #
The composition laws insist that you can compose functions, or translations, and that again, the choice to do one or the other doesn't matter. Along each of the axes, it's just the second functor law applied. You've already seen that SelectSecond is nothing but an alias for Select, so surely, the second functor law must hold for SelectSecond as well. This parametrised test demonstrates that it does:
[Theory] [InlineData("foo", 42)] [InlineData("bar", 1337)] [InlineData("foobar", 0)] [InlineData("ploeh", 7)] [InlineData("fnaah", -6)] public void SecondFunctorLawHoldsForSelectSecond(string first, int second) { Func<bool, char> f = b => b ? 'T' : 'F'; Func<int, bool> g = i => i % 2 == 0; var t = Tuple.Create(first, second); Assert.Equal( t.SelectSecond(x => f(g(x))), t.SelectSecond(g).SelectSecond(f)); }
Here, f is a function that returns 'T' for true and 'F' for false, and g is a function that, as you've seen before, determines whether a number is even. The second functor law states that mapping f(g(x)) in a single step is equivalent to first mapping over g and then map the result of that using f.
The same law applies if you fix the second dimension and translate over the first:
[Theory] [InlineData("foo", 42)] [InlineData("bar", 1337)] [InlineData("foobar", 0)] [InlineData("ploeh", 7)] [InlineData("fnaah", -6)] public void SecondFunctorLawHoldsForSelectFirst(string first, int second) { Func<int, bool> f = x => x % 2 == 0; Func<string, int> g = s => s.Length; var t = Tuple.Create(first, second); Assert.Equal( t.SelectFirst(x => f(g(x))), t.SelectFirst(g).SelectFirst(f)); }
Here, f is the even function, whereas g is a function that returns the length of a string. Again, the test demonstrates that the output is the same whether you map over an intermediary step, or whether you map using only a single step.
This generalises to the composition law for SelectBoth:
[Theory] [InlineData("foo", 42)] [InlineData("bar", 1337)] [InlineData("foobar", 0)] [InlineData("ploeh", 7)] [InlineData("fnaah", -6)] public void SelectBothCompositionLawHolds(string first, int second) { Func<int, bool> f = x => x % 2 == 0; Func<string, int> g = s => s.Length; Func<bool, char> h = b => b ? 'T' : 'F'; Func<int, bool> i = x => x % 2 == 0; var t = Tuple.Create(first, second); Assert.Equal( t.SelectBoth(x => f(g(x)), y => h(i(y))), t.SelectBoth(g, i).SelectBoth(f, h)); }
Again, whether you translate in one or two steps shouldn't affect the outcome.
As all of these tests demonstrate, the bifunctor laws hold for pairs. The tests only showcase 4-5 examples for a pair of string and integer, but I hope it gives you an intuition how any pair is a bifunctor. After all, the SelectFirst, SelectSecond, and SelectBoth methods are all generic, and they behave the same for all generic type arguments.
Summary #
Pairs (two-tuples) are bifunctors. You can translate the first and second element of a pair independently of each other, and the bifunctor laws hold for any pure translation, no matter how you compose the projections.
As always, there can be performance differences between the various compositions, but the outputs will be the same regardless of composition.
A functor, and by extension, a bifunctor, is a structure-preserving map. This means that any projection preserves the structure of the underlying container. In practice that means that for pairs, no matter how you translate a pair, it remains a pair. A pair is characterised by containing two values at once, and no matter how you translate it, it'll still contain two values.
The other common bifunctor, Either, is complementary. While it has two dimensions, it only contains one value, which is of either the one type or the other. It's still a bifunctor, though, because mappings preserve the structure of Either, too.
Next: Either bifunctor.
