An Either monad by Mark Seemann
The Either sum type forms a monad. An article for object-oriented programmers.
This article is an instalment in an article series about monads.
The Either sum type is a useful data type that forms a functor. Actually, it forms two functors. Like many other useful functors, it also forms a monad. Again, more than one monad is possible. In this article I'll focus on the 'usual' monad instance where mapping takes place over the right side. If you swap left and right, however, you can also define a monad that maps over the left side. Try it; it's a good exercise.
Either is also known as Result, in which case right is usually called success or OK, while left is called error or failure.
In this article, I'll base the C# implementation on the code from Church-encoded Either.
Join #
A monad must define either a bind or join function. As outlined in the introduction to monads, if you have one, you can use it to implement the other. For variety's sake, in this article series I do both. I also vary the names when there's no clear idiomatic naming convention. For this version of Either, I've chosen to start with a method called Join:
public static IEither<L, R> Join<L, R>(this IEither<L, IEither<L, R>> source) { return source.Match( onLeft: l => new Left<L, R>(l), onRight: r => r); }
This method flattens a nested Either value. If the outer Either is a left case, the method returns a new Left<L, R>(l) value, which fits the required return type. If the outer Either is a right case, it contains another, nested Either value that it can return.
As already described in the article Church-encoded Either, you can use Either values instead of exceptions. While that article already gives an example, the Either in that value isn't nested. This, however, can easily happen when you try to compose calculations that may fail. Another example may involve parsing. Here are two simple parsers:
public static IEither<string, DateTime> TryParseDate(string candidate) { if (DateTime.TryParse(candidate, out var d)) return new Right<string, DateTime>(d); else return new Left<string, DateTime>(candidate); } public static IEither<string, TimeSpan> TryParseDuration(string candidate) { if (TimeSpan.TryParse(candidate, out var ts)) return new Right<string, TimeSpan>(ts); else return new Left<string, TimeSpan>(candidate); }
These functions try to parse candidate values to more structured data types. If parsing fails, they return the candidate value so that calling code may get a chance to inspect and report the string that caused a failure. What happens if you try to compose these two functions?
IEither<string, DateTime> dt = TryParseDate("2022-03-21"); IEither<string, TimeSpan> ts = TryParseDuration("2"); IEither<string, IEither<string, DateTime>> nested = dt.Select(d => ts.Select(dur => d + dur));
Composing the results of these two functions produces a nested result that you can flatten with Join:
IEither<string, DateTime> flattened = nested.Join();
Using Join for that purpose is, however, often awkward, so a better option is to flatten as you go.
SelectMany #
Monadic bind (in C# called SelectMany) enables you to flatten as you go. As also shown in the monad introduction, if you already have Join you can always implement SelectMany like this:
public static IEither<L, R1> SelectMany<L, R, R1>( this IEither<L, R> source, Func<R, IEither<L, R1>> selector) { return source.Select(selector).Join(); }
The SelectMany method makes the above composition a little easier:
IEither<string, DateTime> result = dt.SelectMany(d => ts.Select(dur => d + dur));
Instead of having to flatten a nested result, you can flatten as you go. I think that Scala's flatMap is a better name for that operation than SelectMany, but the behaviour is the same. If you're wondering why it's called SelectMany, see my attempt at an explanation in the article about the list monad. The name makes modest sense in that context, but in the context of Either, that meaning is lost.
Query syntax #
Perhaps you still find the above composition awkward. After all, you have to nest a Select inside a SelectMany. Is there a simpler way?
One option is to use query syntax, but in order to do that, you must (again as outlined in the monad introduction) add a special boilerplate SelectMany overload:
public static IEither<L, R1> SelectMany<L, R, R1, U>( this IEither<L, R> source, Func<R, IEither<L, U>> k, Func<R, U, R1> s) { return source.SelectMany(x => k(x).Select(y => s(x, y))); }
This enables you to rewrite the above composition like this:
IEither<string, DateTime> result = from d in dt from dur in ts select d + dur;
It's often a question of subjectivity whether you like one alternative over the other, but the behaviour is the same.
Return #
Apart from monadic bind, a monad must also define a way to put a normal value into the monad. Conceptually, I call this function return (because that's the name that Haskell uses). You don't, however, have to define a static method called Return. What's of importance is that the capability exists. For Either<L, R> in C# the idiomatic way would be to use a constructor. This constructor does double duty as monadic return:
public Right(R right)
In other words, return wraps a value in a right case.
Why not the left case? Because it wouldn't type-check. A return function should take a value of the type R and return an IEither<L, R>. The Left constructor, however, doesn't take an R value - it takes an L value.
Left identity #
We need to identify the return function in order to examine the monad laws. Let's see what they look like for the Either monad, starting with the left identity law.
[Theory] [InlineData("2")] [InlineData("2.3:00")] [InlineData("4.5:30")] [InlineData("0:33:44")] [InlineData("foo")] public void LeftIdentityLaw(string a) { Func<string, IEither<string, string>> @return = s => new Right<string, string>(s); Func<string, IEither<string, TimeSpan>> h = TryParseDuration; Assert.Equal(@return(a).SelectMany(h), h(a)); }
As always, even a parametrised test constitutes no proof that the law holds. I show the tests to illustrate what the laws look like in 'real' code.
Right identity #
In a similar manner, we can showcase the right identity law as a test.
[Theory] [InlineData("2022-03-22")] [InlineData("2022-03-21T16:57")] [InlineData("bar")] public void RightIdentityLaw(string a) { Func<string, IEither<string, DateTime>> f = TryParseDate; Func<DateTime, IEither<string, DateTime>> @return = d => new Right<string, DateTime>(d); IEither<string, DateTime> m = f(a); Assert.Equal(m.SelectMany(@return), m); }
The parameters supplied as a will cause m to be both Left and Right values, but the test demonstrates that the law holds in both cases.
Associativity #
The last monad law is the associativity law that describes how (at least) three functions compose. We're going to need three functions. I'm going to reuse TryParseDuration and add two new Either-valued functions:
public static IEither<string, double> DaysForward(TimeSpan ts) { if (ts < TimeSpan.Zero) return new Left<string, double>($"Negative durations not allowed: {ts}."); return new Right<string, double>(ts.TotalDays); } public static IEither<string, int> Nat(double d) { if (d % 1 != 0) return new Left<string, int>($"Non-integers not allowed: {d}."); if (d < 1) return new Left<string, int>($"Non-positive numbers not allowed: {d}."); return new Right<string, int>((int)d); }
These silly functions are only here for purposes of demonstration. Don't try to infer any deep meaning from them.
Designating them f, g, and h, we can use them to express the monad associativity law:
[Theory] [InlineData("2")] [InlineData("-2.3:00")] [InlineData("4.5:30")] [InlineData("0:33:44")] [InlineData("0")] [InlineData("foo")] public void AssociativityLaw(string a) { Func<string, IEither<string, TimeSpan>> f = TryParseDuration; Func<TimeSpan, IEither<string, double>> g = DaysForward; Func<double, IEither<string, int>> h = Nat; var m = f(a); Assert.Equal(m.SelectMany(g).SelectMany(h), m.SelectMany(x => g(x).SelectMany(h))); }
The test cases supplied via the [InlineData] attributes comprise a set of values that make their way through the composition to varying degrees. "2" makes it all the way through to a Right value, because it encodes a two-day duration. It's both a positive value, greater than zero, and an integer. The other test cases become Left values at various stages in the composition, being either a non-number, fractional, zero, or negative.
Conclusion #
Either (AKA Result) is another useful data structure that forms a monad. You can use it instead of throwing exceptions. Its monadic nature enables you to compose multiple Either-valued functions in a sane and elegant way.
Next: The Identity monad.
