The Maybe applicative functor by Mark Seemann
An introduction to the Maybe applicative functor for objectoriented programmers.
This article is an instalment in an article series about applicative functors. Previously, in a related series, you got an introduction to Maybe as a functor. Not all functors are applicative, but some are, and Maybe is one of them (like list).
In this article, you'll see how to make a C# Maybe class applicative. While I'm going to start with F# and Haskell, you can skip to the C# section if you'd like.
F# #
A few years ago, I did the Roman numerals kata in F#. This is an exercise where you have to convert between normal base 10 integers and Roman numerals. Conversions can fail in both directions, because Roman numerals don't support negative numbers, zero, or numbers greater than 3,999, and Roman numerals represented as strings could be malformed.
Some Roman numbers are written in a subtractive style, e.g. "IV" means subtract 1 (I) from 5 (V). It's easy enough to subtract two numbers, but because parsing isn't guaranteed to succeed, I didn't have two numbers; I had two number options (recall that in F#, Maybe is called option
).
How do you subtract one int option
from another int option
?
Both of these values could be Some
, or they could be None
. What should happen in each case? With Maybe, only four combinations are possible, so you can put them in a table:
Some x 
None 


Some y 
Some (x  y) 
None 
None 
None 
None 
Some
cases should you return a Some
case with the result of the subtraction; in all other cases, you should return None
.
You can do this with regular pattern matching, but it's hardly the most elegant solution:
// int option let difference = match minuend, subtrahend with  Some m, Some s > Some (m  s)  _ > None
You could attempt to solve this with a specialised helper function like this:
module Option = // ('a > 'b > 'c) > 'a option > 'b option > 'c option let map2 f xo yo = match xo, yo with  Some x, Some y > Some (f x y)  _ > None
which you could use like this:
let difference = Option.map2 () minuend subtrahend
It doesn't, however, generalise well... What if you need to operate on three option values, instead of two? Or four? Should you add map3
and map4
functions as well?
Making option
an applicative functor addresses that problem. Here's one possible implementation of <*>
:
// ('a > 'b) option > 'a option > 'b option let (<*>) fo xo = match fo, xo with  Some f, Some x > Some (f x)  _ > None
This enables you two write the subtraction like this:
let difference = Some () <*> minuend <*> subtrahend
For a detailed explanation on how that works, see the previous explanation for lists; it works the same way for Maybe as it does for List.
In the end, however, I didn't think that this was the most readable code, so in the Roman numeral exercise, I chose to use a computation expression instead.
Haskell #
In Haskell, Maybe
is already Applicative
as part of the language. Without further ado, you can simply write:
difference = pure () <*> minuend <*> subtrahend
As is the case with the F# code, I don't consider this the most readable way to express the subtraction of two integers. In F#, I ultimately decided to use a computation expression. In Haskell, that's equivalent to using do
notation:
difference :: Maybe Integer difference = do m < minuend s < subtrahend return $ m  s
While more verbose, I think it's clearer that one number is being subtracted from another number.
This works for Maybe
because not only is Maybe
Applicative
, it's also a Monad
. It's its monadness that enables the do
notation. Not all applicative functors are monads, but Maybe is.
C# #
In a previous article you saw how to implement the Maybe functor in C#. You can extend it so that it also becomes an applicative functor:
public static Maybe<TResult> Apply<T, TResult>( this Maybe<Func<T, TResult>> selector, Maybe<T> source) { if (selector.HasItem && source.HasItem) return new Maybe<TResult>(selector.Item(source.Item)); else return new Maybe<TResult>(); } public static Maybe<Func<T2, TResult>> Apply<T1, T2, TResult>( this Maybe<Func<T1, T2, TResult>> selector, Maybe<T1> source) { if (selector.HasItem && source.HasItem) { Func<T2, TResult> g = x => selector.Item(source.Item, x); return new Maybe<Func<T2, TResult>>(g); } else return new Maybe<Func<T2, TResult>>(); }
As was the case for making sequences applicative in C#, you need overloads of the Apply
method, because C#'s type inference is inadequate for this task.
If you have two Maybe<int>
values, minuend
and subtrahend
, you can now perform the subtraction:
Func<int, int, int> subtract = (x, y) => x  y; Maybe<int> difference = subtract.ToMaybe().Apply(minuend).Apply(subtrahend);
Like in F# and Haskell, applicative style is hardly the most readable way to express subtraction. It'd be nice if you could write it like Haskell's do
notation. You can, but to do that, you must make Maybe a monad, and this isn't a monad tutorial. Mike Hadlow has a good monad tutorial for C# developers, the gist of which is that you must implement SelectMany
in order to turn your generic type into a monad. For now, I'll leave this as an exercise for you, but if you add an appropriate SelectMany
method, you'd be able to write the subtraction like this:
Maybe<int> difference = from m in minuend from s in subtrahend select m  s;
Again, I think this is more readable, but it does require that the type in question is a monad, and not all applicative functors are (but Maybe is).
Summary #
This article demonstrates that lists or sequences aren't the only applicative functors. Maybe is also an applicative functor, but more exist. The next article will give you another example.
Next: Applicative validation.
Comments
I think we agreed that the issue is not C#'s weak type inference but its lack of default function currying? My guess is that you wrote this quoted part of this article before my comment on your previous article.
Tyson, thank you for writing.
Yes, June 27, 2017, in fact...You're correct that this particular issue is related to the uncurried nature of C# methods.
I do, however, maintain that C#'s type inference capabilities are weaker than F#'s or Haskell's. To be clear, I view this as the result of priorities. I don't think that the people who designed and wrote the C# compiler are less skilled than the designers of F# or Haskell. The C# compiler has to solve many other problems, such as for example overload resolution, which is a language feature in direct opposition to currying. The C# compiler is excellent at overload resolution, a task with which the F# compiler sometimes struggle (and is not even a language feature in Haskell).
Your comment is, however, a reminder that I should consider how I phrase such notions in the future. Thank you for pointing that out. As I'm publishing and get feedback, I constantly learn new things. I'm always grateful when someone like you take the time to educate me.
I'll see if I can improve in the future. I do, however, still have a backlog of articles I wrote months, or even more than a year, ago, so it's possible that more errors escape my attention when I proof read them before publication. If that happens, I'll appreciate more corrections.
Thank you very much for your kind reply. I agree with everything you said.
I will expand my comment a bit to give a clearer picture of my understanding.
First, very little is "needed"; most things are merely sufficient. In particular, we don't need to overload your
Apply
method to achieve your goal. As I mentioned before, it sufficies to have a singleApply
method and instead create overloads of a function calledcurry
that explicitly curries a given function. Furthermore, I think there is a sense in which this latter approach to overcome the lack of default currying is somehow minimal or most abstract or most general.Second, compared to languages like F# or Haskell, type inference is definitely weaker in C#. This issue was also present (in a subtle way) in your previous article, but I decided to largely ignore it in order to keep my comment more focused. In your previous article, you expliciltly defined the local variable
In particular, you explicitly told the C# compiler that the type of all of these six variable isconcat
like thisstring
. That part was necessary; the type inference in C# is not strong enough to innfer (possibily in some use ofconcat
) that the types could bestring
.Suppose instead of defining
Again, I think there is a sense in which this explicit way to specify noninferable types is somehow minimal or most abstract or most general.concat
as a local variable (withFunc<string, string, string, string, string, string, string>
as its type) you had defined it as a member method on a class. Then its type in C# is some kind "method group". The method group of a method essentially corresponds to the set of methods containing itself and its overloads. Then in order to passconcat
intocurry
, there needs to be a type conversion (or cast) from its method group toFunc<string, string, string, string, string, string, string>
. This is also something that the C# system cannot do, and so Language Ext has overloads of a function calledfun
to do this explicitly. Using it on our hypothetical member functionconcat
would look likeMy impression is that there is some low hanging fruit here for strengthing the type inference of the C# compiler. If a method group correpsonds to a singleton set (and that method has no
ref
orout
arguments), then I would think it would be straight forward to consider an implicit cast from the method group to the correspondingFunc
orAction
delegate.