What is a monad?

Question!

Having briefly looked at Haskell recently, what would be a brief, succinct, practical explanation as to what a monad essentially is?

I have found most explanations I've come across to be fairly inaccessible and lacking in practical detail.



Answers

I wrote this mostly for me but I hope others find it useful :)

Monads address a problem which also shows up in arithmetic as division by zero (DivByZero). Specifically, calculations involving division must detect or allow for a DivByZero exception. This requirement makes coding such expressions in the general case messy.

The Monadic solution is to embrace DivByZero by doing the following

  1. Expand the Number type to support DivByZero conditions with a specific value that is not a regular number such as NaN, Infinity, or Null. Let's call this new number type, Nullable<Number>.
  2. Provide a function for "lifting" or wrapping an existing Number into a Nullable<Number> type (the idea of "wrapping" is that the Number or value can be "unwrapped" without information loss)
  3. Provide a function for "lifting" or wrapping existing operators on Numbers into a versions that operates on Nullable<Number>. Such a wrapper function might merely do the following:
    1. unwrap Numbers from within Nullable<Number>s and invoke it's wrapped Number operator on them, then "lift" the resulting Number into a Nullable<Number>
    2. detect a DivByZero exceptions and produce a Null result value. The expanded type, Nullable<Number>, now accommodates all results values of conventional operators.
    3. when these Nullable<Number> operands the now wrapped operators include Null, the operator wrappers will act accordingly such as to by pass further processing and return Null ( 1 + Null -> Null). What actions to take depends on the programmer. In general, these wrapper functions is where a lot of the functionality of Monads are written while state information is maintain in properties of the wrapper type.

So, a Monad is an expanded type together with a function that "wraps" the original type in this expanded version and a function that wraps the original operators so they can handle this new expanded type. (Monads may have been a motivation for generics or type-parameters.)

It turns out that instead of merely smoothing out the handling of DivByZero (or Infinity if you will), the Monad treatment is broadly applicable to situations that can benefit from type expansion to simplify their coding. In fact, this applicability seems to be wide.

For example, the IO monad is a type that represents the universe, literally. The intent is to recognize that the values returned by the prototypical HelloWorld program is not completely described by the result type of string and it's value "Hello World!". In fact, such a result also includes modifications to hardware and memory states of devices such as the console. In this case, specifically, the console is now displaying additional text, the cursor is on a new line, and so forth. The IO monad is an explicitly recognition of such external effects or side effects, if you will.

Why bother?

Monads allow Stateless algorithms to be devised as such, stateless. State-full machines are complex. A machine with 10 bits may be in 2^10 possible states. Eliminating this complexity is the ideal of functional languages.

Variables hold state. Eliminating "variables" should simply stuff. Purely functional programs don't have variables only values (despite usage of the term 'variable' in the Haskell documentation) and use labels or symbols or names for for them. Consequently, the closest thing to a variable in a purely functional language is the parameters received by a function as they accept new values on each invocation.

The absence of variables is why purely functional languages use recursion instead of loops to iterate. The act of incrementing a counter involves the use of a variable that becomes incremented and all the uncertainty with how it gets updated, when it gets tested, what value it should and when, and then the complexity when you have multiple threads.

Nevertheless, So what?

Without the presence of state, a program becomes a declaration or a definition of it's results, as oppose to a matriculation of some underlying state towards a result. Essentially, the functional expression of incFun(x) = x + 1 is simpler than the imperative expression of incImp(x) = x.add(1); return x; Here, incFun does not modify x but creates a new value. It may even be by replaced by it's occurrence within an expression, 1 + incFun(x), with the it's definition, 1 + (x + 1). On the other hand, incImp modifies the state of x. Whatever such modification means for x is unclear and can be impossible to determine without executing the program in addition to any concurrency issues.

Such complexity gets cognitively expensive over time (2^N). In contrast, the operator, +, cannot modify x but must construct a new value whose result is limited to and fully determined by the values x and 1 and the definition of +. In particular, the 2^N complexity explosion is avoided. Additionally, to emphasize concurrency, incImp, unlike incFun, cannot be invoked concurrently without precautions around the sharing of the parameter since it becomes modified by each invocation.

Why call it a Monad?

A monad is characterized by a mathematical structure called a Monoid from Algebraic group theory. With that said, all it means is that the structure has the following three properties:

  1. has a binary operator, *, such that x * y = z for x, y, and z belong to some type S. For example 1 ÷ 2 = 0.5
  2. has an element i, called the identity, that does nothing such that (i * x) = (x * i) = x. For example the numeric operator, +, and the number, 0, in 4 + 0 = 0 + 4 = 4
  3. the order of evaluation of "segments" is irrelevant: (x * y) * z = x * (y * z). For example the numeric operator, +, in (3 + 4) + 12 = 3 + (4 + 12) = 19. Note, however, that the sequencing of terms must not change.

Property three (3) allows expressions of arbitrary lengths to be evaluated by delineating them into segments and evaluating each independently such as in parallel. For example, x1*x2*...*xN may be segmented into (x1..xJ) * (xJ+1...xM) * (xM+1...xN). The separate result, x0J * xJM * xMN, may then be collected and further evaluated. Support for segmentation like this is a key technique ensuring correct concurrency and distributed evaluation as used by Google's distributed search algorithms (a la map/reduce).

By : George


This answer begins with a motivating example, works through the example, derives an example of a monad, and formally defines "monad".

Consider these three functions in pseudocode:

f(<x, messages>) := <x, messages "called f. ">
g(<x, messages>) := <x, messages "called g. ">
wrap(x)          := <x, "">

f takes an ordered pair of the form <x, messages> and returns an ordered pair. It leaves the first item untouched and appends "called f. " to the second item. Same with g.

You can compose these functions and get your original value, along with a string that shows which order the functions were called in:

  f(g(wrap(x)))
= f(g(<x, "">))
= f(<x, "called g. ">)
= <x, "called g. called f. ">

You dislike the fact that f and g are responsible for appending their own log messages to the previous logging information. (Just imagine for the sake of argument that instead of appending strings, f and g must perform complicated logic on the second item of the pair. It would be a pain to repeat that complicated logic in two -- or more -- different functions.)

You prefer to write simpler functions:

f(x)    := <x, "called f. ">
g(x)    := <x, "called g. ">
wrap(x) := <x, "">

But look at what happens when you compose them:

  f(g(wrap(x)))
= f(g(<x, "">))
= f(<<x, "">, "called g. ">)
= <<<x, "">, "called g. ">, "called f. ">

The problem is that passing a pair into a function does not give you what you want. But what if you could feed a pair into a function:

  feed(f, feed(g, wrap(x)))
= feed(f, feed(g, <x, "">))
= feed(f, <x, "called g. ">)
= <x, "called g. called f. ">

Read feed(f, m) as "feed m into f". To feed a pair <x, messages> into a function f is to pass x into f, get <y, message> out of f, and return <y, messages message>.

feed(f, <x, messages>) := let <y, message> = f(x)
                          in  <y, messages message>

Notice what happens when you do three things with your functions:

First: if you wrap a value and then feed the resulting pair into a function:

  feed(f, wrap(x))
= feed(f, <x, "">)
= let <y, message> = f(x)
  in  <y, "" message>
= let <y, message> = <x, "called f. ">
  in  <y, "" message>
= <x, "" "called f. ">
= <x, "called f. ">
= f(x)

That is the same as passing the value into the function.

Second: if you feed a pair into wrap:

  feed(wrap, <x, messages>)
= let <y, message> = wrap(x)
  in  <y, messages message>
= let <y, message> = <x, "">
  in  <y, messages message>
= <x, messages "">
= <x, messages>

That does not change the pair.

Third: if you define a function that takes x and feeds g(x) into f:

h(x) := feed(f, g(x))

and feed a pair into it:

  feed(h, <x, messages>)
= let <y, message> = h(x)
  in  <y, messages message>
= let <y, message> = feed(f, g(x))
  in  <y, messages message>
= let <y, message> = feed(f, <x, "called g. ">)
  in  <y, messages message>
= let <y, message> = let <z, msg> = f(x)
                     in  <z, "called g. " msg>
  in <y, messages message>
= let <y, message> = let <z, msg> = <x, "called f. ">
                     in  <z, "called g. " msg>
  in <y, messages message>
= let <y, message> = <x, "called g. " "called f. ">
  in <y, messages message>
= <x, messages "called g. " "called f. ">
= feed(f, <x, messages "called g. ">)
= feed(f, feed(g, <x, messages>))

That is the same as feeding the pair into g and feeding the resulting pair into f.

You have most of a monad. Now you just need to know about the data types in your program.

What type of value is <x, "called f. ">? Well, that depends on what type of value x is. If x is of type t, then your pair is a value of type "pair of t and string". Call that type M t.

M is a type constructor: M alone does not refer to a type, but M _ refers to a type once you fill in the blank with a type. An M int is a pair of an int and a string. An M string is a pair of a string and a string. Etc.

Congratulations, you have created a monad!

Formally, your monad is the tuple <M, feed, wrap>.

A monad is a tuple <M, feed, wrap> where:

  • M is a type constructor.
  • feed takes a (function that takes a t and returns an M u) and an M t and returns an M u.
  • wrap takes a v and returns an M v.

t, u, and v are any three types that may or may not be the same. A monad satisfies the three properties you proved for your specific monad:

  • Feeding a wrapped t into a function is the same as passing the unwrapped t into the function.

    Formally: feed(f, wrap(x)) = f(x)

  • Feeding an M t into wrap does nothing to the M t.

    Formally: feed(wrap, m) = m

  • Feeding an M t (call it m) into a function that

    • passes the t into g
    • gets an M u (call it n) from g
    • feeds n into f

    is the same as

    • feeding m into g
    • getting n from g
    • feeding n into f

    Formally: feed(h, m) = feed(f, feed(g, m)) where h(x) := feed(f, g(x))

Typically, feed is called bind (AKA >>= in Haskell) and wrap is called return.

By : Jordan


Explanation

It's quite simple, when explained in C#/Java terms:

  1. A monad is a function that takes arguments and returns a special type.

  2. The special type that this monad returns is also called monad. (A monad is a combination of #1 and #2)

  3. There's some syntactic sugar to make calling this function and conversion of types easier.

Example

A monad is useful to make the life of the functional programmer easier. The typical example: The Maybe monad takes two parameters, a value and a function. It returns null if the passed value is null. Otherwise it evaluates the function. If we needed a special return type, we would call this return type Maybe as well. A very crude implementation would look like this:

object Maybe(object value, Func<object,object> function)
{
    if(value==null)
        return null;

    return function(value);
}

This is spectacularly useless in C# because this language lacks the required syntactic sugar to make monads useful. But monads allow you to write more concise code in functional programming languages.

Oftentimes programmers call monads in chains, like so:

var x = Maybe(x, x2 => Maybe(y, y2 => Add(x2, y2)));

In this example the Add method would only be called if x and y are both non-null, otherwise null will be returned.

Answer

To answer the original question: A monad is a function AND a type. Like an implementation of a special interface.

By : Simon


This video can help you solving your question :)
By: admin