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



Answers

Why do we need monads?

  1. We want to program only using functions. ("functional programming" after all -FP).
  2. Then, we have a first big problem. This is a program:

    f(x) = 2 * x

    g(x,y) = x / y

    How can we say what is to be executed first? How can we form an ordered sequence of functions (i.e. a program) using no more than functions?

    Solution: compose functions. If you want first g and then f, just write f(g(x,y)). OK, but ...

  3. More problems: some functions might fail (i.e. g(2,0), divide by 0). We have no "exceptions" in FP. How do we solve it?

    Solution: Let's allow functions to return two kind of things: instead of having g : Real,Real -> Real (function from two reals into a real), let's allow g : Real,Real -> Real | Nothing (function from two reals into (real or nothing)).

  4. But functions should (to be simpler) return only one thing.

    Solution: let's create a new type of data to be returned, a "boxing type" that encloses maybe a real or be simply nothing. Hence, we can have g : Real,Real -> Maybe Real. OK, but ...

  5. What happens now to f(g(x,y))? f is not ready to consume a Maybe Real. And, we don't want to change every function we could connect with g to consume a Maybe Real.

    Solution: let's have a special function to "connect"/"compose"/"link" functions. That way, we can, behind the scenes, adapt the output of one function to feed the following one.

    In our case: g >>= f (connect/compose g to f). We want >>= to get g's output, inspect it and, in case it is Nothing just don't call f and return Nothing; or on the contrary, extract the boxed Real and feed f with it. (This algorithm is just the implementation of >>= for the Maybe type).

  6. Many other problems arise which can be solved using this same pattern: 1. Use a "box" to codify/store different meanings/values, and have functions like g that return those "boxed values". 2. Have composers/linkers g >>= f to help connecting g's output to f's input, so we don't have to change f at all.

  7. Remarkable problems that can be solved using this technique are:

    • having a global state that every function in the sequence of functions ("the program") can share: solution StateMonad.

    • We don't like "impure functions": functions that yield different output for same input. Therefore, let's mark those functions, making them to return a tagged/boxed value: IO monad.

Total happiness !!!!

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?







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.




A monad is an array of functions

(Pst: an array of functions is just a computation).

Actually, instead of a true array (one function in one cell array) you have those functions chained by another function >>=. The >>= allows to adapt the results from function i to feed function i+1, perform calculations between them or, even, not to call function i+1.

The types used here are "types with context". This is, a value with a "tag". The functions being chained must take a "naked value" and return a tagged result. One of the duties of >>= is to extract a naked value out of its context. There is also the function "return", that takes a naked value and puts it with a tag.

An example with Maybe. Let's use it to store a simple integer on which make calculations.

-- a * b
multiply :: Int -> Int -> Maybe Int
multiply a b = return  (a*b)

-- divideBy 5 100 = 100 / 5
divideBy :: Int -> Int -> Maybe Int
divideBy 0 _ = Nothing -- dividing by 0 gives NOTHING
divideBy denom num = return (quot num denom) -- quotient of num / denom

-- tagged value
val1 = Just 160 

-- array of functions feeded with val1
array1 = val1 >>= divideBy 2  >>= multiply 3 >>= divideBy  4 >>= multiply 3

-- array of funcionts created with the do notation
-- equals array1 but for the feeded val1
array2 :: Int -> Maybe Int
array2 n = do
       v <- divideBy 2  n
       v <- multiply 3 v
       v <- divideBy 4 v
       v <- multiply 3 v
       return v

-- array of functions, 
-- the first >>= performs 160 / 0, returning Nothing
-- the second >>= has to perform Nothing >>= multiply 3 ....
-- and simply returns Nothing without calling multiply 3 ....
array3 = val1 >>= divideBy 0  >>= multiply 3 >>= divideBy  4 >>= multiply 3

main = do
     print array1
     print (array2 160)
     print array3

Just to show that monads are array of functions with helper operations, consider the equivalent to the above example, just using a real array of functions

type MyMonad = [Int -> Maybe Int] -- my monad as a real array of functions

myArray1 = [divideBy 2, multiply 3, divideBy 4, multiply 3]

-- function for the machinery of executing each function i with the result provided by function i-1
runMyMonad :: Maybe Int -> MyMonad -> Maybe Int
runMyMonad val [] = val
runMyMonad Nothing _ = Nothing
runMyMonad (Just val) (f:fs) = runMyMonad (f val) fs

And it would be used like this:

print (runMyMonad (Just 160) myArray1)






In OO terms, a monad is a fluent container.

The minimum requirement is a definition of class <A> Something that supports a constructor Something(A a) and at least one method Something<B> flatMap(Function<A, Something<B>>)

Arguably, it also counts if your monad class has any methods with signature Something<B> work() which preserves the class's rules -- the compiler bakes in flatMap at compile time.

Why is a monad useful? Because it is a container that allows chain-able operations that preserve semantics. For example, Optional<?> preserves the semantics of isPresent for Optional<String>, Optional<Integer>, Optional<MyClass>, etc.

As a rough example,

Something<Integer> i = new Something("a")
  .flatMap(doOneThing)
  .flatMap(doAnother)
  .flatMap(toInt)

Note we start with a string and end with an integer. Pretty cool.

In OO, it might take a little hand-waving, but any method on Something that returns another subclass of Something meets the criterion of a container function that returns a container of the original type.

That's how you preserve semantics -- i.e. the container's meaning and operations don't change, they just wrap and enhance the object inside the container.




I'll try to make the shortest definition I can manage using OOP terms:

A generic class CMonadic<T> is a monad if it defines at least the following methods:

class CMonadic<T> { 
    static CMonadic<T> create(T t);  // a.k.a., "return" in Haskell
    public CMonadic<U> flatMap<U>(Func<T, CMonadic<U>> f); // a.k.a. "bind" in Haskell
}

and if the following laws apply for all types T and their possible values t

left identity:

CMonadic<T>.create(t).flatMap(f) == f(t)

right identity

instance.flatMap(CMonadic<T>.create) == instance

associativity:

instance.flatMap(f).flatMap(g) == instance.flatMap(t => f(t).flatMap(g))

Examples:

A List monad may have:

List<int>.create(1) --> [1]

And flatMap on the list [1,2,3] could work like so:

intList.flatMap(x => List<int>.makeFromTwoItems(x, x*10)) --> [1,10,2,20,3,30]

Iterables and Observables can also be made monadic, as well as Promises and Tasks.

Commentary:

Monads are not that complicated. The flatMap function is a lot like the more commonly encountered map. It receives a function argument (also known as delegate), which it may call (immediately or later, zero or more times) with a value coming from the generic class. It expects that passed function to also wrap its return value in the same kind of generic class. To help with that, it provides create, a constructor that can create an instance of that generic class from a value. The return result of flatMap is also a generic class of the same type, often packing the same values that were contained in the return results of one or more applications of flatMap to the previously contained values. This allows you to chain flatMap as much as you want:

intList.flatMap(x => List<int>.makeFromTwo(x, x*10))
       .flatMap(x => x % 3 == 0 
                   ? List<string>.create("x = " + x.toString()) 
                   : List<string>.empty())

It just so happens that this kind of generic class is useful as a base model for a huge number of things. This (together with the category theory jargonisms) is the reason why Monads seem so hard to understand or explain. They're a very abstract thing and only become obviously useful once they're specialized.

For example, you can model exceptions using monadic containers. Each container will either contain the result of the operation or the error that has occured. The next function (delegate) in the chain of flatMap callbacks will only be called if the previous one packed a value in the container. Otherwise if an error was packed, the error will continue to propagate through the chained containers until a container is found that has an error handler function attached via a method called .orElse() (such a method would be an allowed extension)

Notes: Functional languages allow you to write functions that can operate on any kind of a monadic generic class. For this to work, one would have to write a generic interface for monads. I don't know if its possible to write such an interface in C#, but as far as I know it isn't:

interface IMonad<T> { 
    static IMonad<T> create(T t); // not allowed
    public IMonad<U> flatMap<U>(Func<T, IMonad<U>> f); // not specific enough,
    // because the function must return the same kind of monad, not just any monad
}



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 >>=.




From a practical point of view (summarizing what has been said in many previous answers and related articles), it seems to me that one of the fundamental "purposes" (or usefulness) of the monad is to leverage the dependencies implicit in recursive method invocations aka function composition (i.e. when f1 calls f2 calls f3, f3 needs to be evaluated before f2 before f1) to represent sequential composition in a natural way, especially in the context of a lazy evaluation model (that is, sequential composition as a plain sequence, e.g. "f3(); f2(); f1();" in C - the trick is especially obvious if you think of a case where f3, f2 and f1 actually return nothing [their chaining as f1(f2(f3)) is artificial, purely intended to create sequence]).

This is especially relevant when side-effects are involved, i.e. when some state is altered (if f1, f2, f3 had no side-effects, it wouldn't matter in what order they're evaluated; which is a great property of pure functional languages, to be able to parallelize those computations for example). The more pure functions, the better.

I think from that narrow point of view, monads could be seen as syntactic sugar for languages that favor lazy evaluation (that evaluate things only when absolutely necessary, following an order that does not rely on the presentation of the code), and that have no other means of representing sequential composition. The net result is that sections of code that are "impure" (i.e. that do have side-effects) can be presented naturally, in an imperative manner, yet are cleanly separated from pure functions (with no side-effects), which can be evaluated lazily.

This is only one aspect though, as warned here.




Links