A monad is a common abstraction. While typically associated with Haskell, monads also exist in C# and other languages.

This article series is part of a larger series of articles about functors, applicatives, and other mappable containers.

If you understand what a functor is, it should be easy to grasp the idea of a monad. It's a functor you can flatten.

There's a little more to it than that, and you also need to learn what I mean by flatten, but that's the essence of it.

In this article-series-within-an-article series, I'll explain this disproportionally dreaded concept, giving you plenty of examples as well as a more formal definition. Examples will be in both C#, F#, and Haskell, although I plan to emphasise C#. I expect that there's little need of explaining monads to people already familiar with Haskell. I'll show examples as separate articles in this series. These articles are mostly aimed at object-oriented programmers curious about monads.

This list is far from exhaustive; more monads exist.

Set diagram with monads shown as a subset of applicatives, which is shown as a subset of functors, again a subset of generic types.

All monads are applicative functors, but not all applicative functors are monads. As the set diagram reiterates, applicative functors are functors, but again: not necessarily the other way around.

Flattening #

A monad is a functor you can flatten. What do I mean by flatten?

As in the article that introduces functors, imagine that you have some Functor<T> container. More concretely, this could be IEnumerable<T>, Maybe<T>, Task<T>, etcetera.

When working with functors, you sometimes run into situations where the containers nest inside each other. Instead of a Functor<decimal>, you may find yourself with a Functor<Functor<decimal>>, or maybe even an object that's thrice or quadruply nested.

If you can flatten such nested functor objects to just Functor<T>, then that functor also forms a monad.

In C#, you need a method with this kind of signature:

public static Functor<T> Flatten<T>(this Functor<Functor<T>> source)

Notice that this method takes a Functor<Functor<T>> as input and returns a Functor<T> as output. I'm not showing the actual implementation, since Functor<T> is really just a 'pretend' functor (and monad). In the example articles that follow, you'll see actual implementation code.

With Flatten you can write code like this:

Functor<decimaldest = source.Flatten();

Here, source is a Functor<Functor<decimal>>.

This function also exists in Haskell, although there, it's called join:

join :: Monad m => m (m a) -> m a

For any Monad m you can flatten or join a nested monad m (m a) to a 'normal' monad m a.

This is the same function as Flatten, so in C# we could define an alias like this:

public static Functor<T> Join<T>(this Functor<Functor<T>> source)
    return source.Flatten();

Usually, however, you don't see monads introduced via join or Flatten. It's a shame, really, because it's the most straightforward description.

Bind #

Most languages that come with a notion of monads define them via a function colloquially referred to as monadic bind or just bind. In C# it's called SelectMany, F# computation expressions call it Bind, and Scala calls it flatMap (with a vestige of the concept of flattening). Haskell just defines it as an operator:

(>>=) :: Monad m => m a -> (a -> m b) -> m b

When talking about it, I tend to call the >>= operator bind.

Translated to C# it has this kind of signature:

public static Functor<TResult> SelectMany<TTResult>(
    this Functor<T> source,
    Func<T, Functor<TResult>> selector)

It looks almost like a functor's Select method (AKA map or fmap function). The difference is that this selector returns a functor value (Functor<TResult>) rather than a 'naked' TResult value.

When a Flatten (or Join) method already exists, you can always implement SelectMany like this:

public static Functor<TResult> SelectMany<TTResult>(
    this Functor<T> source,
    Func<T, Functor<TResult>> selector)
    Functor<Functor<TResult>> nest = source.Select(selector);
    return nest.Flatten();

I've split the implementation over two lines of code to make it clearer what's going on. That's also the reason I've used an explicit type declaration rather than var.

The Select method exists because the type is already a functor. When you call Select with selector you get a Functor<Functor<TResult>> because selector itself returns a Functor<TResult>. That's a nested functor, which you can Flatten.

You can use SelectMany like this:

Functor<TimeSpan> source = Functor.Return(TimeSpan.FromMinutes(32));
Functor<doubledest = source.SelectMany(x => Functor.Return(x.TotalSeconds + 192));

The lambda expression returns a Functor<double>. Had you called Select with this lambda expression, the result would have been a nested functor. SelectMany, however, flattens while it maps (it flatMaps). (This example is rather inane, since it would be simpler to use Select and omit wrapping the output of the lambda in the functor. The later articles in this series will show some more compelling examples.)

If you already have Flatten (or Join) you can always implement SelectMany like this. Usually, however, languages use monadic bind (e.g. SelectMany) as the foundation. Both C#, Haskell, and F# do that. In that case, it's also possible to go the other way and implement Flatten with SelectMany. You'll see examples of that in the subsequent articles.

Syntactic sugar #

Several languages understand monads well enough to provide some degree of syntactic sugar. While you can always use SelectMany in C# by simply calling the method, there are situations where that becomes awkward. The same is true with bind functions in F# and >>= in Haskell.

In C# you can use query syntax:

Functor<DateTime> fdt = Functor.Return(new DateTime(2001, 8, 3));
Functor<TimeSpan> fts = Functor.Return(TimeSpan.FromDays(4));
Functor<DateTime> dest = from dt in fdt
                         from ts in fts
                         select dt - ts;

In order to support more than a single from expression, however, you must supply a special SelectMany overload, or the code doesn't compile:

public static Functor<TResult> SelectMany<TUTResult>(
    this Functor<T> source,
    Func<T, Functor<U>> k,
    Func<T, U, TResult> s)
    return source.SelectMany(x => k(x).Select(y => s(x, y)));

This is an odd quirk of C# that I've yet to encounter in other languages, and I consider it ceremony that I have to perform to satiate the C# compiler. It's not part of the concept of what a monad is. As far as I can tell, you can always implement it like shown here.

Haskell's syntactic sugar is called do notation and works for all monads:

example :: (Monad m, Num a) => m a -> m a -> m a
example fdt fts = do
  dt <- fdt
  ts <- fts
  return $ dt - ts

In F#, computation expressions drive syntactic sugar, but still based (among other things) on the concept of a monad:

let example (fdt : Monad<DateTime>) (fts : Monad<TimeSpan>) = monad {
    let! dt = fdt
    let! ts = fts
    return dt - ts }

Here, we again have to pretend that a Monad<'a> type exists, with a companion monad computation expression.

Return #

The ability to flatten nested functors is the essence of what a monad is. There are, however, also some formal requirements. As is the case with functors, there are laws that a monad should obey. I'll dedicate a separate article for those, so we'll skip them for now.

Another requirement is that in addition to SelectMany/bind/flatMap/>>= a monad must also provide a method to 'elevate' a value to the monad. This function is usually called return. It should have a type like this:

public static Functor<T> Return<T>(T x)

You can see it in use in the above code snippet, and with the relevant parts repeated here:

Functor<DateTime> fdt = Functor.Return(new DateTime(2001, 8, 3));
Functor<TimeSpan> fts = Functor.Return(TimeSpan.FromDays(4));

This code example lifts the value DateTime(2001, 8, 3) to a Functor<DateTime> value, and the value TimeSpan.FromDays(4) to a Functor<TimeSpan> value.

Usually, in a language like C# a concrete monad type may either afford a constructor or factory method for this purpose. You'll see examples in the articles that give specific monad examples.

Conclusion #

A monad is a functor you can flatten. That's the simplest way I can put it.

In this article you learned what flattening means. You also learned that a monad must obey some laws and have a return function. The essence, however, is flattening. The laws just ensure that the flattening is well-behaved.

It may not yet be clear to you why some functors would need flattening in the first place, but subsequent articles will show examples.

The word monad has its own mystique in software development culture. If you've ever encountered some abstruse nomenclature about monads, then try to forget about it. The concept is really not hard to grasp, and it usually clicks once you've seen enough examples, and perhaps done some exercises.

Next: Kleisli composition.


Quoting image in words:

  • Every Monad is an applicative functor
  • Every applicative functor is a functor
  • Every functor is a generic type

As your aricle about Monomorphic functors shows, not every functor is a generic type. However, it is true that every applicative functor is a generic (or polymorphic) functor.

2022-04-18 15:28 UTC

True, the illustration is a simplification.

2022-04-18 20:38 UTC

I guess you might know that already but the reason for the strange SelectMany ceremonial version is compiler performance. The complicated form is needed so that the overload resolution does not take exponential amount of time. See a 2013 article by Eric Lippert covering this.

2022-05-02 11:50 UTC

Petr, thank you for writing. I remember reading about it before, but it's good to have a proper source.

If I understand the article correctly, the problem seems to originate from overload resolution. This would, at least, explain why neither F# nor Haskell needs that extra overload. I wonder if a language like Java would have a similar problem, but I don't think that Java has syntactic sugar for monads.

It still seems a little strange that the C# compiler requires the presence of that overload. Eric Lippert seems to strongly imply that it's always possible to derive that extra overload from any monad's fundamental functions (as is also my conjecture). If this is so, the C# compiler should be able to do that work by itself. Monads that wish to supply a more efficient implement (e.g. IEnumerable<T>) could still do so: The C# compiler could look for the overload and use it if it finds it, and still fall back to the default implementation if none is available.

But I suppose that since the query syntax feature only really exists to support IEnumerable<T> this degree of sophistication wasn't warranted.

2022-05-03 6:12 UTC

Wish to comment?

You can add a comment to this post by sending me a pull request. Alternatively, you can discuss this post on Twitter or somewhere else with a permalink. Ping me with the link, and I may respond.


Monday, 28 March 2022 06:12:00 UTC


"Our team wholeheartedly endorses Mark. His expert service provides tremendous value."
Hire me!
Published: Monday, 28 March 2022 06:12:00 UTC