Monad in plain English? (For the OOP programmer with no FP background)

Question

In terms that an OOP programmer would understand (without any functional programming background), what is a monad?

What problem does it solve and what are the most common places it's used?

EDIT:

To clarify the kind of understanding I was looking for, let's say you were converting an FP application that had monads into an OOP application. What would you do to port the responsibilities of the monads to the OOP app?

Answer 1

From wikipedia:

In functional programming, a monad is a kind of abstract data type used to represent computations (instead of data in the domain model). Monads allow the programmer to chain actions together to build a pipeline, in which each action is decorated with additional processing rules provided by the monad. Programs written in functional style can make use of monads to structure procedures that include sequenced operations,1[2] or to define arbitrary control flows (like handling concurrency, continuations, or exceptions).

Formally, a monad is constructed by defining two operations (bind and return) and a type constructor M that must fulfill several properties to allow the correct composition of monadic functions (i.e. functions that use values from the monad as their arguments). The return operation takes a value from a plain type and puts it into a monadic container of type M. The bind operation performs the reverse process, extracting the original value from the container and passing it to the associated next function in the pipeline.

A programmer will compose monadic functions to define a data-processing pipeline. The monad acts as a framework, as it's a reusable behavior that decides the order in which the specific monadic functions in the pipeline are called, and manages all the undercover work required by the computation.[3] The bind and return operators interleaved in the pipeline will be executed after each monadic function returns control, and will take care of the particular aspects handled by the monad.

I believe it explains it very well.

Answer 2

In terms that an OOP programmer would understand (without any functional programming background), what is a monad?

A monad is an "amplifier" of types that obeys certain rules and which has certain operations provided.

First, what is an "amplifier of types"? By that I mean some system which lets you take a type and turn it into a more special type. For example, in C# consider Nullable<T>. This is an amplifier of types. It lets you take a type, say int, and add a new capability to that type, namely, that now it can be null when it couldn't before.

As a second example, consider IEnumerable<T>. It is an amplifier of types. It lets you take a type, say, string, and add a new capability to that type, namely, that you can now make a sequence of strings out of any number of single strings.

What are the "certain rules"? Briefly, that there is a sensible way for functions on the underlying type to work on the amplified type such that they follow the normal rules of functional composition. For example, if you have a function on integers, say

int M(int x) { return x + N(x * 2); }

then the corresponding function on Nullable<int> can make all the operators and calls in there work together "in the same way" that they did before.

(That is incredibly vague and imprecise; you asked for an explanation that didn't assume anything about knowledge of functional composition.)

What are the "operations"? (1) That there is a way to take a value of an unamplified type and turn it into a value of the amplified type. (2) That there is a way to transform operations on the unamplified type into operations on the amplified type that obeys the rules of functional composition mentioned before, and (3) that there is usually a way to get the unamplified type back out of the amplified type. (This last point isn't strictly necessary for a monad but it is frequently the case that such an operation exists.)

Again, take Nullable<T> as an example. You can turn an int into a Nullable<int> with the constructor. The C# compiler takes care of most nullable "lifting" for you, but if it didn't, the lifting transformation is straightforward: an operation, say,

int M(int x) { whatever }

is transformed into

Nullable<int> M(Nullable<int> x) 
{ 
    if (x == null) 
        return null; 
    else 
        return new Nullable<int>(whatever);
}

And turning a nullable int back into an int is done with the Value property.

It's the function transformation that is the key bit. Notice how the actual semantics of the nullable operation -- that an operation on a null propagates the null -- is captured in the transformation. We can generalize this. Suppose you have a function from int to int, like our original M. You can easily make that into a function that takes an int and returns a Nullable<int> because you can just run the result through the nullable constructor. Now suppose you have this higher-order method:

Nullable<T> Bind<T>(Nullable<T> amplified, Func<T, Nullable<T>> func)
{
    if (amplified == null) 
        return null;
    else
        return func(amplified.Value);
}

See what you can do with that? Any method that takes an int and returns an int, or takes an int and returns a nullable int can now have the nullable semantics applied to it.

Furthermore: suppose you have two methods

Nullable<int> X(int q) { ... }
Nullable<int> Y(int r) { ... }

and you want to compose them:

Nullable<int> Z(int s) { return X(Y(s)); }

That is, Z is the composition of X and Y. But you cannot do that because X takes an int, and Y returns a nullable int. But since you have the "bind" operation, you can make this work:

Nullable<int> Z(int s) { return Bind(Y(s), X); }

The bind operation on a monad is what makes composition of functions on amplified types work. The "rules" I handwaved about above are that the monad preserves the rules of normal function composition; that composing with identity functions results in the original function, that composition is associative, and so on.

In C#, "Bind" is called "SelectMany". Take a look at how it works on the sequence monad. We need to have three things: turn a value into a sequence, turn a sequence into a value, and bind operations on sequences. Those operations are:

IEnumerable<T> MakeSequence<T>(T item)
{
    yield return item;
}
T Single<T>(IEnumerable<T> sequence)
{
    // let's just take the first one
    foreach(T item in sequence) return item; 
}
IEnumerable<T> SelectMany<T>(IEnumerable<T> seq, Func<T, IEnumerable<T>> func)
{
    foreach(T item in seq)
        foreach(T result in func(item))
            yield return result;            
}

The nullable monad rule was "to combine two functions that produce nullables together, check to see if the inner one results in null; if it does, produce null, if it does not, then call the outer one with the result". That's the desired semantics of nullable. The sequence monad rule is "to combine two functions that produce sequences together, apply the outer function to every element produced by the inner function, and then concatenate all the resulting sequences together". The fundamental semantics of the monads are captured in the Bind/SelectMany methods; this is the method that tells you what the monad really means.

We can do even better. Suppose you have a sequences of ints, and a method that takes ints and results in sequences of strings. We could generalize the binding operation to allow composition of functions that take and return different amplified types, so long as the inputs of one match the outputs of the other:

IEnumerable<U> SelectMany<T,U>(IEnumerable<T> seq, Func<T, IEnumerable<U>> func)
{
    foreach(T item in seq)
        foreach(U result in func(item))
            yield return result;            
}

So now we can say "amplify this bunch of individual integers into a sequence of integers. Transform this particular integer into a bunch of strings, amplified to a sequence of strings. Now put both operations together: amplify this bunch of integers into the concatenation of all the sequences of strings." Monads allow you to compose your amplifications.

What problem does it solve and what are the most common places it's used?

That's rather like asking "what problems does the singleton pattern solve?", but I'll give it a shot.

Monads are typically used to solve problems like:

• I need to make new capabilities for this type and still combine old functions on this type to use the new capabilities.
• I need to capture a bunch of operations on types and represent those operations as composable objects, building up larger and larger compositions until I have just the right series of operations represented, and then I need to start getting results out of the thing
• I need to represent side-effecting operations cleanly in a language that hates side effects

(Note that these are basically three ways of saying the same thing.)

C# uses monads in its design. As already mentioned, the nullable pattern is highly akin to the "maybe monad". LINQ is entirely built out of monads; the "SelectMany" method is what does the semantic work of composition of operations. (Erik Meijer is fond of pointing out that every LINQ function could actually be implemented by SelectMany; everything else is just a convenience.)

To clarify the kind of understanding I was looking for, let's say you were converting an FP application that had monads into an OOP application. What would you do to port the responsibilities of the monads into the OOP app?

Most OOP languages do not have a rich enough type system to represent the monad pattern itself directly; you need a type system that supports types that are higher types than generic types. So I wouldn't try to do that. Rather, I would implement generic types that represent each monad, and implement methods that represent the three operations you need: turning a value into an amplified value, turning an amplified value into a value, and transforming a function on unamplified values into a function on amplified values.

A good place to start is how we implemented LINQ in C#. Study the SelectMany method; it is the key to understanding how the sequence monad works in C#. It is a very simple method, but very powerful!

For a more in-depth and theoretically sound explanation of monads in C#, I highly recommend my colleague Wes Dyer's article on the subject. This article is what explained monads to me when they finally "clicked" for me.

http://blogs.msdn.com/wesdyer/archive/2008/01/11/the-marvels-of-monads.aspx

Answer 3

A monad is a data type that encapsulates a value and to which essentially two operations can be applied:

• return x creates a value of the monad type that encapsulates x
• m >>= f (read it as "the bind operator") applies the function f to the value in the monad m

That's what a monad is. There are a few more technicalities, but basically those two operations define a monad. The real question is what a monad does, and that depends on the monad — lists are monads, Maybes are monads, IO operations are monads. All that it means when we say those things are monads is that they have the monad interface of return and >>=.

Answer 4

If you've ever used Powershell, the patterns Eric described should sound familiar. Powershell cmdlets are monads; functional composition is represented by a pipeline.

Jeffrey Snover's interview with Erik Meijer goes into more detail.

Answer 5

I would say the closest OO analogy to monads is the "command pattern".

In the command pattern you wrap an ordinary statement or expression in a command object. The command object expose an execute method which executes the wrapped statement. So statement are turned into first class objects which can passed around and executed at will. Commands can be composed so you can create a program-object by chaining and nesting command-objects.

The commands are executed by a separate object, the invoker. The benefit of using the command pattern (rather than just execute a series of ordinary statements) is that different invokers can apply different logic to how the commands should be executed.

The command pattern could be used to add (or remove) language features which is not supported by the host language. For example, in a hypothetical OO language without exceptions, you could add exception semantics by exposing "try" and "throw" methods to the commands. When a command calls throw, the invoker backtracks through the list (or tree) of commands until the last "try" call. Conversely, you could remove exception semantic from a language (if you believe exceptions are bad) by catching all exceptions thrown by each individual commands, and turning them into error codes which are then passed to the next command.

Even more fancy execution semantics like transactions, non-deterministic execution or continuations can be implemented like this in a language which doesn't support it natively. It is a pretty powerful pattern if you think about it.

Now in reality the command-patterns is not used as a general language feature like this. The overhead of turning each statement into a separate class would lead to an unbearable amount of boilerplate code. But in principle it can be used to solve the same problems as monads are used to solve in fp.

Answer 6

In terms that an OOP programmer would understand (without any functional programming background), what is a monad?

What problem does it solve and what are the most common places it's used?are the most common places it's used?

In terms of OO programming, a monad is an interface (or more likely a mixin), parameterized by a type, with two methods, return and bind that describe:

• How to inject a value to get a monadic value of that injected value type;
• How to use a function that makes a monadic value from a non-monadic one, on a monadic value

The problem it solves is the same type of problem you'd expect from any interface, namely, "I have a bunch of different classes that do different things, but seem to do those different things in a way that has am underlying similarity. How can I describe that similarity between them, even if the classes themselves aren't really subtypes of anything closer than 'the Object' class itself?"

More specifically, the Monad "interface" is similar to IEnumerator or IIterator in that it takes a type that itself takes a type. The main "point" of Monad though is being able to connect operations based on the interior type, even to the point of having a new "internal type", while keeping - or even enhancing - the information structure of the main class.

I hope that helped.

Answer 7

You have a recent presentation "Monadologie -- professional help on type anxiety" by Christopher League (July 12th, 2010), which is quite interesting on topics of continuation and monad.
The video going with this (slideshare) presentation is actually available at vimeo.
The Monad part start around 37 minutes in, on this one hour video, and starts with slide 42 of its 58 slide presentation.

It is presented as "the leading design pattern for functional programming", but the language used in the examples is Scala, which is both OOP and functional.
You can read more on Monad in Scala in the blog post "Monads - Another way to abstract computations in Scala", from Debasish Ghosh (March 27, 2008).

A type constructor M is a monad if it supports these operations:

# the return function
def unit[A] (x: A): M[A]

# called "bind" in Haskell 
def flatMap[A,B] (m: M[A]) (f: A => M[B]): M[B]

# Other two can be written in term of the first two:

def map[A,B] (m: M[A]) (f: A => B): M[B] =
  flatMap(m){ x => unit(f(x)) }

def andThen[A,B] (ma: M[A]) (mb: M[B]): M[B] =
  flatMap(ma){ x => mb }

So for instance (in Scala):

• Option is a monad

    def unit[A] (x: A): Option[A] = Some(x)

    def flatMap[A,B](m:Option[A])(f:A =>Option[B]): Option[B] =
      m match {
       case None => None
       case Some(x) => f(x)
      }

• List is Monad

    def unit[A] (x: A): List[A] = List(x)

    def flatMap[A,B](m:List[A])(f:A =>List[B]): List[B] =
      m match {
        case Nil => Nil
        case x::xs => f(x) ::: flatMap(xs)(f)
      }

Monad are a big deal in Scala because of convenient syxtax built to take advantage of Monad structures:

for comprehension in Scala:

for(i <- 1 to 4;
    j <- 1 to i;
    k <- 1 to j)
yield { i*j*k }

is translated by the compiler to:

(1 to 4).flatMap { i =>
  (1 to i).flatMap { j =>
    (1 to j).map { k =>
      i*j*k }}}

The key abstraction is the flatMap, which binds the computation through chaining.
Each invocation of flatMap returns the same data structure type (but of different value), that serves as the input to the next command in chain.
In the above snippet, flatMap takes as input a closure (SomeType) => List[AnotherType] and returns a List[AnotherType]. The important point to note is that all flatMaps take the same closure type as input and return the same type as output.
This is what "binds" the computation thread - every item of the sequence in the for-comprehension has to honor this same type constraint.

---

If you take two operations (that may fail) and pass the result to the third, like:

lookupVenue: String => Option[Venue]
getLoggedInUser: SessionID => Option[User]
reserveTable: (Venue, User) => Option[ConfNo]

, but without taking advantage of Monad, you get convoluted OOP-code like:

val user = getLoggedInUser(session)
val confirm =
  if(!user.isDefined) { None }
  else lookupVenue(name) match {
    case None => None
    case Some(venue) => {
      val confno = reserveTable(venue, user.get)
      if(confno.isDefined)
        mailTo(confno.get, user.get)
      confno
    }
  }

, whereas with Monad, you can work with the actual types (Venue, User) like all the operations work, and keep the Option verification stuff hidden, all because of the flatmaps of the for syntax:

val confirm =
for(venue <- lookupVenue(name);
    user <- getLoggedInUser(session);
    confno <- reserveTable(venue, user))
yield {
  mailTo(confno, user)
  confno
}

The yield part will only be executed if all three functions have Some[X]; any None would directly be returned to confirm.

---

So:

Monads allow ordered computation within Functional Programing, that allows us to model sequencing of actions in a nice structured form, somewhat like a DSL.
And the greatest power comes with the ability to compose monads that serve different purposes, into extensible abstractions within an application.
This sequencing and threading of actions by a monad is done by the language compiler that does the transformation through the magic of closures.

---

By the way, Monad is not only model of computation used in FP: see this blog post.

Category theory proposes many models of computation. Among them

• the Arrow model of computations
• the Monad model of computations
• the Applicative model of computations