Monads, part one

Posted on by

Lots of other bloggers have attempted this, but what the heck, I’ll give it a shot too. In this series I’m going to attempt to answer the question:

I’m a C# programmer with no “functional programming” background whatsoever. What is this “monad” thing I keep hearing about, and what use is it to me?

Bloggers often attempt to tackle this problem by jumping straight into the functional programming usage of the term, and start talking about “bind” and “unit” operations, and higher-order functional programming with higher-order types. Even worse is to go all the way back to the category theory underpinning monads and start talking about “monoids in the category endofunctors” and the like. I want to start from a much more pragmatic, object-oriented, C#-type-system focussed place and move towards the rarefied heights of functional programming as we go.

Object-oriented programmers like talking about “design patterns”, so let’s use that as our framing device.

The Maison du Trifolium at DouggaThe idea of “design patterns” comes from real-world-let’s-build-a-building architecture. You see the same patterns come up over and over again in architecture in the several millennia that humans have been building stuff: walls, doors, windows, ceilings, columns, vestibutes, courtyards, drawbridges, moats, closets, kitchens and so on. These things all have relationships to each other; a courtyard with no doors and windows is not a very useful courtyard. And these patterns and their relationships are pretty stable over time and space; the Pentagon and a 1900-year old Roman-style villa clearly have many patterns in common despite the vast gulf of time and space between their constructions.

The Pentagon US Department of Defense buildingSo too with software, we see the same recognizable patterns come up over and over again: functions, variables, types, and so on. Those patterns are so ingrained into our languages, so a part of the air we breathe that we seldom even notice that they are design patterns, but they are. And therefore when we discuss design patterns it is almost always in the context of a pattern that is not a part of the language, but rather must be explicitly implemented by the developer.

C#, for example, does not have the “singleton” pattern (that I mentioned last time) “baked in” to the language. It could have been; there could be special syntax for singleton class C { ... }, as there is for static classes or abstract classes. The C# language designers did not consider it an important enough pattern to be elevated into the language as a first class feature, so you’ve got to “follow the pattern” yourself if you want to make a singleton.

The “monad pattern” is just another design pattern for types, just as the singleton pattern is a design pattern for types. It’s a description of the “shape” of a solution to a number of problems. The thing about the monad pattern is that, unlike the singleton pattern, it can sneak up on you. Plenty of developers have used the monad pattern entirely by accident, not realizing that they’re re-inventing something that already has a name.

Man, things are starting to get highfalutin already and that is specifically what I want to avoid. Next time on FAIC we’ll take a look at some examples of types that have the monad flavour to them and see what they have in common.

Photos of the trifolium villa at Dougga and the Pentagon are from Wikimedia Commons; click on the photos for larger versions and for the photo credits.

39 thoughts on “Monads, part one”

  2. This sounds like a great approach; I’m very much looking forward to the series. I only recently actually understood monads (I think), thanks to Wes Dyer’s “Marvels of Monads”, even though I had already attempted it several times (before, it went very much over my head). And yes, I knew about the maybe monad and understood it fairly well on its own. I didn’t, however, understand what the maybe monad shared generally with other monads. In other words, what makes it a monad? The thing that clinched it for me was adding Task<T> from async/await to the set that already included Nullable<T> and IEnumerable<T>, and suddenly understanding what “amplify” means in the article.

    Reply ↓

    • Indeed; as I commented in the previous episode, Wes and I used to work together on the C# compiler and his article was the one that really made monads “click” for me. As you say, it is the abstraction underlying the pattern that is the tricky bit to understand. Most of the blogger analogies involving space suits or burritos, though clever, I think do not give the typical OO developer a crisp idea of what the common features of the pattern are. And actually going to the underlying category theory with its morphisms and monoids and endofunctors is so abstract that it is hard to see how it applies to real code; most people do not think of IEnumerable<T> as being “a morphism in the category of types”. Thus I’m trying to take a middle ground; next time we’ll pick five examples of types you already know that follow the monad pattern, and then start to suss out what the commonalities are. I want to keep this very focussed on code you could actually write.

      Reply ↓

    • Maybe if Monads were called StatementContexts or SmartPipes or StepComputation or even ConcatMapables they might make more sense. As for the Maybe monad it just turns out that it sort of works like an “early break” when you treat it as a callable (note that =<< is a version of the call/apply operator called ($) in Haskell, invoke in Java, and operator() in C++).

      Reply ↓

  3. Pingback: The Morning Brew - Chris Alcock » The Morning Brew #1301

  4. I think an important aspect of Monads is that you can write helper functions operating on all possible monads, even unwritten ones.

    I guess one could consider Nullable<T>, IEnumerable<T> and Task<T> all monads because they have a return and a bind can be defined. But what useful helper functions could exist which can operate an all of these and provide some common benefit?

    For example, mapM: why would I want to map over a T[] with a (T => T?) and receive a T[] that is null if one of the elements was mapped to null. I cannot think of a use-case.

    Reply ↓

    • Though it is slightly unfortunate that C# lacks the “higher types” that are necessary to make a method that is polymorphic over all monads, that ability is actually not one that I miss a lot in C#, for exactly the reason you mention: what common monads would you want to treat polymorphically in this manner?

      Reply ↓

      • I would say that it’s very important. This polymorphism over any monad is really the main point of identifying this pattern — you can write all these functions for any *individual* type-which-happens-to-be-a-monad, no problem, but you don’t really get much benefit that way. You can (and do) write code for cartesian products or for combining parsers or for handling exceptions, but being able to abstract it is the main advantage of noticing the pattern in the first place.

        I don’t know much C#, but it looks like e.g. Nullable isn’t a monad — you can’t have Nullable<Nullable>, which is critical to actually being a monad, rather than “sort of” being one (some people would say that having M<M> is the whole point — otherwise you can/should use a weaker abstraction). But let’s pretend it is one. You can think of a Nullable value as a computation that produces a T but might throw an exception. Then this Nullable-mapM is like mapping a bunch of functions that might throw exceptions over the list: If any one of the functions “throws an exception” (returns Null), the whole mapM will — otherwise you just get a regular list. So this lets you implement a particular sort of exceptions directly in the language, as plain first-class values.

        Of course, these aren’t very useful exceptions — you just have a single “failure” exception, which doesn’t communicate any information. So you can define an Except monad (so you have values of type Except) such that instead of just failing with Null, you can fail with a value of type E, and it’ll be automatically propagated exception-style.

        Let’s look at the other examples. IEnumerable looks like an interface, and I don’t know enough to say whether you can actually implement the monad API for it (I suspect not), so I’ll pretend you said List instead. 🙂 You can think of List as a list of values, but you can also think of it as a single nondeterministic value. Then List-mapM means: For each element in this list, apply this function, and then nondeterministically pick one of its return values. So in the end you get a list of lists, one for each possible choice you could have made (note: nondeterminism doesn’t mean “pick one randomly” — it means “pick all of them”, but only one at any particular time. Sort of like a loop. But from your perspective it doesn’t matter). So you get a sort of cartesian product (this is what list comprehensions are based on).

        Task seems to be a sort of asynchronous/promise type. By precedent, it probably winds up not being quite a monad either, but I’ll just pretend it’s some sort of CPS/IO-style monad. Let’s say you have a bunch of tasks and you’re communicating asynchronously with a TCP socket. You have a function that takes a string, and returns a task that asks the user for that string, then produces the user’s response. Now you can mapM this function over the list [“Name”,”Age”,”SSN”], and you get back one single task that asks the user for three pieces of information in turn, and then produces a list of all three answers.

        These seem like somewhat different behaviors, but they’re really the same thing in a sense, and this is the sense that you can abstract with higher-order polymorphism over any monad — you can just write this function once, to a common API, and then use it in quite a lot of particular cases (the ones mentioned above as well as parsers, logging, continuations, etc. You get a different, but related, meaning in each of those contexts). Note that mapM is just one example of such a function, and not the most useful one (in fact, it doesn’t even require all of the monad interface — it can be implemented on any “Applicative functor”, which is a rather weaker abstraction). And of course in Haskell you have a simple syntax sugar which is polymorphic over any monad.

        This would probably be a better explanation with code examples, but this comment is already way too long (and I don’t really know C#, anyway). 🙂

        Reply ↓

        • I think the point of this post was to introduce the concept of Monads to C# programmers, who are not used to thinking about types in the context of higher abstractions. In C# you don’t usually think of types that have completely unrelated “usage semantics” (such as Nullable and Task) as being related. What Eric is doing here is introducing the concept of thinking in these terms. (Maybe it’s worth talking about Monoid or Functor since they are simpler.)

          As for not being able to write generic functions over monads, can’t this be solved by introducing an interface – the closest thing to a typeclass – for monads? For example:

          interface IMonad<T> { 
    IMonad<B> Bind<B>(IMonad<T> ma, Func<T, IMonad<B>> mb);
    IMonad<T> Return(T t);
}

          Then if all the monadic types (assuming they really are) implement this interface, you can write mapM, sequence, etc…

          Reply ↓

          • Though I see what you are getting at here, this isn’t quite right. The bind and return operations are not operations on instances of the monad; they are in C# parlance “static methods” of the monad type. To express that properly you need something like Haskell’s “higher types”.

  5. Accidentally or not I like that you use “shape” to describe the commonalities captured in Patterns. Christoffer Alexander, who’s a building houses kind of architect and by several regarded as the founder of the Patterns discipline James O. Coplien a leading figure in the same discipline talk about patterns as capturing _form_ of function.

    Reply ↓

    • Thanks for the note. People were complaining that the comments were too narrow, so I widened them. Obviously I am not yet a WordPress CSS master. 🙂 I’ll figure out how to do it elegantly eventually.

      Reply ↓

  11. Pingback: Links of the Week – Trappings from the tumultuous technical turmoil... exception null || !

  12. It’s official. Monads are unexplainable. They cannot be explained. When someone comprehends monads, it alters their brain structure in a way that renders them incapable of communicating it to other people. For all I know, this itself is a monad.

    Reply ↓

  13. Monads are just a way to encapsulate program state so that it won’t mix up with another monad (state container/encapsulation). See, object oriented programmers are the masters of encapsulation, and still do it wrong. Usually class state is leaked out (by its methods) as side-effect. And when two of these leaked states mix, that is your non-reproducible-bug-in-production.

    Reply ↓

    • Yeah thats true for State Monads which AND a state or hidden effect to the result, but there are also Conditional Monads (Maybe and Either) which OR program state to your result, and List Monad which gives you all of the possible permutations of your result.

      Reply ↓

  14. Pingback: Monadic .NET Types | BlogoSfera

  15. Pingback: Amplify C# | The Coding Notes

  16. Pingback: Following the pattern | Fabulous adventures in coding

  17. Pingback: Dealing with Data that Will Become Invalidated | Ready to Rock Software Development

  18. Pingback: Harder to C++: Monads for Mortals [1] | Clatter from the Byte Kitchen

  19. Pingback: fleshweasel comments on “Learn You a Haskell” | blog.offeryour.com

  20. Pingback: Bookmarks for February 19th | Chris's Digital Detritus

  21. Pingback: Functional Programming: Links, News And Resources (7) | Angel "Java" Lopez on Blog

  22. Pingback: Practical Intro to Monads in JavaScript – Evojam Technology Blog

  23. Pingback: Why Async? | 神刀安全网

  24. Pingback: A new start – Vrasidas Oikonomakos blog

  25. Pingback: Monads, part two | Fabulous adventures in coding

  26. Pingback: Fixing Random, part 13 | Fabulous adventures in coding

  27. Pingback: Hungarian Monadic Notation: Call Me Maybe | Knowing .NET

  28. Pingback: Static constructors, part four | Fabulous adventures in coding

  29. Pingback: Consideration-grabbing Ways To Alcohol Addiction -

  30. Pingback: “unknown”과“missing”값을 어떻게 변수에 저장하고“unknown”과“missing”의 차이를 유지해야합니까? 만족스러운 해결책을 제시 할 수없는 - How IT

Leave a comment