# 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.