# Either bifunctor by Mark Seemann

*Either forms a bifunctor. An article for object-oriented programmers.*

This article is an instalment in an article series about bifunctors. As the overview article explains, essentially there's two practically useful bifunctors: pairs and Either. In the previous article, you saw how a pair (a two-tuple) forms a bifunctor. In this article, you'll see how Either also forms a bifunctor.

### Mapping both dimensions #

In the previous article, you saw how, if you have maps over both dimensions, you can trivially implement `SelectBoth`

(what Haskell calls `bimap`

):

`return source.SelectFirst(selector1).SelectSecond(selector2);`

The relationship can, however, go both ways. If you implement `SelectBoth`

, you can derive `SelectFirst`

and `SelectSecond`

from it. In this article, you'll see how to do that for Either.

Given the Church-encoded Either, the implementation of `SelectBoth`

can be achieved in a single expression:

public static IEither<L1, R1> SelectBoth<L, L1, R, R1>( this IEither<L, R> source, Func<L, L1> selectLeft, Func<R, R1> selectRight) { return source.Match<IEither<L1, R1>>( onLeft: l => new Left<L1, R1>( selectLeft(l)), onRight: r => new Right<L1, R1>(selectRight(r))); }

Given that the input `source`

is an `IEither<L, R>`

object, there's isn't much you can do. That interface only defines a single member, `Match`

, so that's the only method you can call. When you do that, you have to supply the two arguments `onLeft`

and `onRight`

.

The `Match`

method is defined like this:

T Match<T>(Func<L, T> onLeft, Func<R, T> onRight)

Given the desired return type of `SelectBoth`

, you know that `T`

should be `IEither<L1, R1>`

. This means, then, that for `onLeft`

, you must supply a function of the type `Func<L, IEither<L1, R1>>`

. Since a functor is a structure-preserving map, you should translate a *left* case to a *left* case, and a *right* case to a *right* case. This implies that the concrete return type that matches `IEither<L1, R1>`

for the `onLeft`

argument is `Left<L1, R1>`

.

When you write the function with the type `Func<L, IEither<L1, R1>>`

as a lambda expression, the input argument `l`

has the type `L`

. In order to create a `new Left<L1, R1>`

, however, you need an `L1`

object. How do you produce an `L1`

object from an `L`

object? You call `selectLeft`

with `l`

, because `selectLeft`

is a function of the type `Func<L, L1>`

.

You can apply the same line of reasoning to the `onRight`

argument. Write a lambda expression that takes an `R`

object `r`

as input, call `selectRight`

to turn that into an `R1`

object, and return it wrapped in a `new Right<L1, R1>`

object.

This works as expected:

> new Left<string, int>("foo").SelectBoth(string.IsNullOrWhiteSpace, i => new DateTime(i)) Left<bool, DateTime>(false) > new Right<string, int>(1337).SelectBoth(string.IsNullOrWhiteSpace, i => new DateTime(i)) Right<bool, DateTime>([01.01.0001 00:00:00])

Notice that both of the above statements evaluated in *C# Interactive* use the same projections as input to `SelectBoth`

. Clearly, though, because the inputs are first a `Left`

value, and secondly a `Right`

value, the outputs differ.

### Mapping the left side #

When you have `SelectBoth`

, you can trivially implement the translations for each dimension in isolation. In the previous article, I called these methods `SelectFirst`

and `SelectSecond`

. In this article, I've chosen to instead name them `SelectLeft`

and `SelectRight`

, but they still corresponds to Haskell's `first`

and `second`

`Bifunctor`

functions.

public static IEither<L1, R> SelectLeft<L, L1, R>(this IEither<L, R> source, Func<L, L1> selector) { return source.SelectBoth(selector, r => r); }

The method body is literally a one-liner. Just call `SelectBoth`

with `selector`

as the projection for the left side, and the identity function as the projection for the right side. This ensures that if the actual value is a `Right<L, R>`

object, nothing's going to happen. Only if the input is a `Left<L, R>`

object will the projection run:

> new Left<string, int>("").SelectLeft(string.IsNullOrWhiteSpace) Left<bool, int>(true) > new Left<string, int>("bar").SelectLeft(string.IsNullOrWhiteSpace) Left<bool, int>(false) > new Right<string, int>(42).SelectLeft(string.IsNullOrWhiteSpace) Right<bool, int>(42)

In the above *C# Interactive* session, you can see how projecting three different objects using `string.IsNullOrWhiteSpace`

works. When the `Left`

object indeed does contain an empty string, the result is a `Left`

value containing `true`

. When the object contains `"bar"`

, however, it contains `false`

. Furthermore, when the object is a `Right`

value, the mapping has no effect.

### Mapping the right side #

Similar to `SelectLeft`

, you can also trivially implement `SelectRight`

:

public static IEither<L, R1> SelectRight<L, R, R1>(this IEither<L, R> source, Func<R, R1> selector) { return source.SelectBoth(l => l, selector); }

This is another one-liner calling `SelectBoth`

, with the difference that the identity function `l => l`

is passed as the first argument, instead of as the last. This ensures that only `Right`

values are mapped:

> new Left<string, int>("baz").SelectRight(i => new DateTime(i)) Left<string, DateTime>("baz") > new Right<string, int>(1_234_567_890).SelectRight(i => new DateTime(i)) Right<string, DateTime>([01.01.0001 00:02:03])

In the above examples, `Right`

integers are projected into `DateTime`

values, whereas `Left`

strings stay strings.

### Identity laws #

Either obeys 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; public static IEnumerable<object[]> BifunctorLawsData { get { yield return new[] { new Left<string, int>("foo") }; yield return new[] { new Left<string, int>("bar") }; yield return new[] { new Left<string, int>("baz") }; yield return new[] { new Right<string, int>( 42) }; yield return new[] { new Right<string, int>( 1337) }; yield return new[] { new Right<string, int>( 0) }; } } [Theory, MemberData(nameof(BifunctorLawsData))] public void SelectLeftObeysFirstFunctorLaw(IEither<string, int> e) { Assert.Equal(e, e.SelectLeft(Id)); }

This test uses xUnit.net's `[Theory]`

feature to supply a small set of example input values. The input values are defined by the `BifunctorLawsData`

property, since I'll reuse the same values for all the bifunctor law demonstration tests.

The tests also use the identity function implemented as a `private`

function called `Id`

, since C# doesn't come equipped with such a function in the Base Class Library.

For all the `IEither<string, int>`

objects `e`

, the test simply verifies that the original Either `e`

is equal to the Either projected over the first axis with the `Id`

function.

Likewise, the first functor law applies when translating over the second dimension:

[Theory, MemberData(nameof(BifunctorLawsData))] public void SelectRightObeysFirstFunctorLaw(IEither<string, int> e) { Assert.Equal(e, e.SelectRight(Id)); }

This is the same test as the previous test, with the only exception that it calls `SelectRight`

instead of `SelectLeft`

.

Both `SelectLeft`

and `SelectRight`

are implemented by `SelectBoth`

, so the real test is whether this method obeys the identity law:

[Theory, MemberData(nameof(BifunctorLawsData))] public void SelectBothObeysIdentityLaw(IEither<string, int> e) { Assert.Equal(e, e.SelectBoth(Id, Id)); }

Projecting over both dimensions with the identity function does, indeed, return an object equal to the input object.

### Consistency law #

In general, it shouldn't matter whether you map with `SelectBoth`

or a combination of `SelectLeft`

and `SelectRight`

:

[Theory, MemberData(nameof(BifunctorLawsData))] public void ConsistencyLawHolds(IEither<string, int> e) { bool f(string s) => string.IsNullOrWhiteSpace(s); DateTime g(int i) => new DateTime(i); Assert.Equal(e.SelectBoth(f, g), e.SelectRight(g).SelectLeft(f)); Assert.Equal( e.SelectLeft(f).SelectRight(g), e.SelectRight(g).SelectLeft(f)); }

This example creates two local functions `f`

and `g`

. The first function, `f`

, just delegates to `string.IsNullOrWhiteSpace`

, although I want to stress that this is 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 `SelectLeft`

followed by `SelectRight`

, 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. This parametrised test demonstrates that the law holds for `SelectLeft`

:

[Theory, MemberData(nameof(BifunctorLawsData))] public void SecondFunctorLawHoldsForSelectLeft(IEither<string, int> e) { bool f(int x) => x % 2 == 0; int g(string s) => s.Length; Assert.Equal(e.SelectLeft(x => f(g(x))), e.SelectLeft(g).SelectLeft(f)); }

Here, `f`

is the *even* function, whereas `g`

is a local function that returns the length of a string. 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 first dimension and translate over the second:

[Theory, MemberData(nameof(BifunctorLawsData))] public void SecondFunctorLawHoldsForSelectRight(IEither<string, int> e) { char f(bool b) => b ? 'T' : 'F'; bool g(int i) => i % 2 == 0; Assert.Equal(e.SelectRight(x => f(g(x))), e.SelectRight(g).SelectRight(f)); }

Here, `f`

is a local function that returns `'T'`

for `true`

and `'F'`

for `false`

, and `g`

is a local function that, as you've seen before, determines whether a number is even. 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, MemberData(nameof(BifunctorLawsData))] public void SelectBothCompositionLawHolds(IEither<string, int> e) { bool f(int x) => x % 2 == 0; int g(string s) => s.Length; char h(bool b) => b ? 'T' : 'F'; bool i(int x) => x % 2 == 0; Assert.Equal( e.SelectBoth(x => f(g(x)), y => h(i(y))), e.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 Either. The tests only showcase six examples for either a string or an integer, but I hope it gives you an intuition how any Either object is a bifunctor. After all, the `SelectLeft`

, `SelectRight`

, and `SelectBoth`

methods are all generic, and they behave the same for all generic type arguments.

### Summary #

Either objects are bifunctors. You can translate the first and second dimension of an Either object 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. For Either objects, it means that *left* objects remain *left* objects, and *right* objects remain *right* objects, even if the contained values change. Either is characterised by containing exactly one value, but it can be either a *left* value or a *right* value. No matter how you translate it, it still contains only a single value - *left* or *right*.

The other common bifunctor, *pair*, is complementary. Not only does it also have two dimensions, but a pair always contains both values at once.

**Next:** Rose tree bifunctor.

## Comments

I feel like the concepts of functor and bifunctor were used somewhat interchangeably in this post. Can we clarify this relationship?

To help us with this, consider type variance. The generic type Func<A> is covariant, but more specifically, it is covariant on A. That additional prepositional phrase is often omitted because it can be inferred. In contrast, the generic type Func<A, B> is both covariant and contravariant but (of course) not on the same type parameter. It is covariant in B and contravariant in A.

I feel like saying that a generic type with two type parameters is a (bi)functor also needs an additional prepositional phrase. Like, Either<L, R> is a bifunctor in L and R, so it is also a functor in L and a functor in R.

Does this seem like a clearer way to talk about a specific type being both a bifunctor and a fuctor?

Tyson, thank you for writing. I find no fault with what you wrote. Is it clearer? I don't know.

One thing that's surprised me throughout this endeavour is exactly what does or doesn't confuse readers. This, I can't predict.

A functor is, by its definition, assumed to be covariant. Contravariant functors also exist, but they're explicitly named

contravariant functorsto distinguish them from standard functors.Ultimately, co- or contravariance of generic type arguments is (I think) insufficient to identify a type as a functor. Whether or not something is a functor is determined by whether or not it obeys the functor laws. Can we guarantee that all types with a covariant type argument will obey the functor laws?

I wasn't trying to discuss the relationship between functors and type variance. I just brought up type variance as an example in programming where I think adding additional prepositional phrases to statements can clarify things.