The Maybe monad by Mark Seemann
The Maybe sum type forms a monad. An article for object-oriented programmers.
This article is an instalment in an article series about monads.
The Maybe sum type is a useful data type that forms a functor. Like many other useful functors, it also forms a monad.
It can be useful when querying another data structure (like a list or a tree) for a value that may or may not be present. It's also useful when performing a calculation that may not be possible, such as taking the square root of of a number, or calculating the average of a collection of values. A third common use case is when parsing a value, although usually, the Either sum type is often a better option for that task.
Bind #
A monad must define either a bind or join function. In C#, monadic bind is called SelectMany. Depending on how you've implemented Maybe<T> the details of the implementation may vary, but the observable behaviour must always be the same. In this article I'm going to continue to use the Maybe<T> class first shown in the article about the Maybe functor. (That's not really my favourite implementation, but it doesn't matter.)
In that code base, I chose to implement SelectMany as an extension method. Why I didn't use an instance method I no longer remember. Again, this doesn't matter.
public static Maybe<TResult> SelectMany<T, TResult>( this Maybe<T> source, Func<T, Maybe<TResult>> selector) { if (source.HasItem) return selector(source.Item); else return new Maybe<TResult>(); }
If the source has an item, SelectMany calls selector with the value and returns the result. If not, the result is an empty Maybe<TResult>.
Monadic bind becomes useful when you have more than one function that returns a monadic value. Consider, for example, this variation of Average:
public static Maybe<double> Average(IEnumerable<double> values) { if (values.Any()) return new Maybe<double>(values.Average()); else return new Maybe<double>(); }
You can't calculate the average of an empty collection, so if values is empty, this function returns an empty Maybe<double>.
If you only needed this Average function, then you could use Maybe's functor affordance to map the result. On the other hand, imagine that you'd like to pass the Average result to this Sqrt function:
public static Maybe<double> Sqrt(double d) { var result = Math.Sqrt(d); switch (result) { case double.NaN: case double.PositiveInfinity: return new Maybe<double>(); default: return new Maybe<double>(result); } }
This is another calculation that may not be possible. If you try to compose Average and Sqrt with Select (the functor's map function), you'd get a Maybe<Maybe<double>>. Fortunately, however, monads are functors you can flatten:
[Theory] [InlineData(new double[0], -100)] [InlineData(new double[] { 5, 3 }, 2)] [InlineData(new double[] { 1, -2 }, -100)] public void ComposeAverageAndSqrt(double[] values, double expected) { Maybe<double> actual = Average(values).SelectMany(Sqrt); Assert.Equal(expected, actual.GetValueOrFallback(-100)); }
The SelectMany method flattens as it goes. Viewed in this way, Scala's flatMap seems like a more appropriate name.
The above test demonstrates how SelectMany returns a flattened Maybe<double>. The first test case has zero elements, so the Average method is going to return an empty Maybe<double>. SelectMany handles that gracefully by returning another empty value.
In the second test case Average returns a populated value that contains the number 4. SelectMany passes 4 to Sqrt, which returns 2 wrapped in a Maybe<double>.
In the third test case, the average is -.5, wrapped in a Maybe<double>. SelectMany passes -.5 on to Sqrt, which returns an empty value.
Query syntax #
Monads also enable query syntax in C# (just like they enable other kinds of syntactic sugar in languages like F# and Haskell). As outlined in the monad introduction, however, you must add a special SelectMany overload:
public static Maybe<TResult> SelectMany<T, U, TResult>( this Maybe<T> source, Func<T, Maybe<U>> k, Func<T, U, TResult> s) { return source.SelectMany(x => k(x).Select(y => s(x, y))); }
As I also mentioned in the monad introduction, it seems to me that you can always implement this overload with the above expression. Once this overload is in place, you can rewrite the above composition in query syntax, if that's more to your liking:
[Theory] [InlineData(new double[0], -100)] [InlineData(new double[] { 5, 3 }, 2)] [InlineData(new double[] { 1, -2 }, -100)] public void ComposeAverageAndSqrtWithQuerySyntax(double[] values, double expected) { Maybe<double> actual = from a in Average(values) from s in Sqrt(a) select s; Assert.Equal(expected, actual.GetValueOrFallback(-100)); }
In this case, query syntax is more verbose, but the behaviour is the same. It's just two different ways of writing the same expression. The C# compiler desugars the query-syntax expression to one that composes with SelectMany.
Join #
In the introduction you learned that if you have a Flatten or Join function, you can implement SelectMany, and the other way around. Since we've already defined SelectMany for Maybe<T>, we can use that to implement Join. In this article I use the name Join rather than Flatten. This is an arbitrary choice that doesn't impact behaviour. Perhaps you find it confusing that I'm inconsistent, but I do it in order to demonstrate that the behaviour is the same even if the name is different.
The concept of a monad is universal, but the names used to describe its components differ from language to language. What C# calls SelectMany, Scala calls flatMap, and what Haskell calls join, other languages may call Flatten.
You can always implement Join by using SelectMany with the identity function.
public static Maybe<T> Join<T>(this Maybe<Maybe<T>> source) { return source.SelectMany(x => x); }
Instead of flattening as you go with SelectMany, you could also use Select and Join to compose Average and Sqrt:
[Theory] [InlineData(new double[0], -100)] [InlineData(new double[] { 5, 3 }, 2)] [InlineData(new double[] { 1, -2 }, -100)] public void JoinAverageAndSqrt(double[] values, double expected) { Maybe<double> actual = Average(values).Select(Sqrt).Join(); Assert.Equal(expected, actual.GetValueOrFallback(-100)); }
You'd typically not write the composition like this, as it seems more convenient to use SelectMany, but you could. 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 Maybe<T> in C# the idiomatic way would be to use a constructor. This constructor overload does double duty as monadic return:
public Maybe(T item) { if (item == null) throw new ArgumentNullException(nameof(item)); this.HasItem = true; this.Item = item; }
Why is it that overload, and not the other one? Because if you try to use new Maybe<T>() as return, you'll find that it breaks the monad laws. Try it. It's a good exercise.
Left identity #
Now that we're on the topic of the monad laws, let's see what they look like for the Maybe monad, starting with the left identity law.
[Theory] [InlineData(0)] [InlineData(1)] [InlineData(2)] public void LeftIdentity(int a) { Func<int, Maybe<int>> @return = i => new Maybe<int>(i); Func<int, Maybe<double>> h = i => i != 0 ? new Maybe<double>(1.0 / i) : new Maybe<double>(); Assert.Equal(@return(a).SelectMany(h), h(a)); }
To provide some variety, h is another Maybe-valued function - this time one that performs a safe multiplicative inverse. If i is zero, it returns an empty Maybe<double> because you can't devide by zero; otherwise, it returns one divided by i (wrapped in a Maybe<double>).
Right identity #
In a similar manner, we can showcase the right identity law as a test.
[Theory] [InlineData("")] [InlineData("foo")] [InlineData("42")] [InlineData("1337")] public void RightIdentity(string a) { Maybe<int> f(string s) { if (int.TryParse(s, out var i)) return new Maybe<int>(i); else return new Maybe<int>(); } Func<int, Maybe<int>> @return = i => new Maybe<int>(i); Maybe<int> m = f(a); Assert.Equal(m.SelectMany(@return), m); }
Again, for variety's sake, for f I've chosen a function that should probably be named TryParseInt if used in another context.
Associativity #
The last monad law is the associativity law that we can demonstrate like this:
[Theory] [InlineData("bar")] [InlineData("-1")] [InlineData("0")] [InlineData("4")] public void Associativity(string a) { Maybe<int> f(string s) { if (int.TryParse(s, out var i)) return new Maybe<int>(i); else return new Maybe<int>(); } Func<int, Maybe<double>> g = i => Sqrt(i); Func<double, Maybe<double>> h = d => d == 0 ? new Maybe<double>() : new Maybe<double>(1 / d); var m = f(a); Assert.Equal(m.SelectMany(g).SelectMany(h), m.SelectMany(x => g(x).SelectMany(h))); }
Here, I've copy-and-pasted the TryParseInt function I also used in the right identity example, and combined it with the Sqrt function and a safe multiplicative inverse. The law, however, should hold for all pure functions that type-check. The functions shown here are just examples.
As usual, a parametrised test is no proof that the law holds. I provide the tests only as examples of what the laws looks like.
Conclusion #
The Maybe sum type is a versatile and useful data structure that forms a monad. This enables you to compose disparate functions that each may err by failing to return a value.
Next: An Either monad.
