Monad (functional programming): Difference between revisions

For the object in category theory, see Monad (category theory).

In functional programming, a monad is a design pattern that can structure program logic in a way that is both generic and declarative. More specifically, a monad generically transforms underlying data types into richer types with some standard higher-order functions (also called "functionals") that must obey formal rules known as the monad laws. So long as these criteria are met, monads can represent many kinds of computations at a high level of abstraction, not just pure functions.

This allows monads to simplify a wide range of problems elegantly, keeping the many benefits of purely functional programming like referential transparency, but without any need to extend the language's main semantics. With monads, a programmer can chain functions in logical order (independent of time and evaluation strategy) to build a succinct pipeline, which handles additional data, control flow, or side-effects automatically.

Some languages, particularly functional ones like Haskell, offer libraries with definitions for a general Monad class and often-used instances. However, since monads are ultimately an abstract pattern, one can implement them conveniently in any language that supports parametric polymorphism.

Overview

The idea of a monad originally comes from category theory, where it is defined as an endofunctor with additional structure. When translated into functional programming terms, a monad acts as a generic concept (or an equivalent feature like a type class), applying structure and features to simpler types generically instead of relying on their underlying semantics. Working on types yet remaining agnostic about their operational details gives monads much of their expressive power; what sets monads apart from other generics though are their stringent behavior and unique functionals.

The monad pattern does not arise as often in object-oriented programming, but many object-oriented languages offer mechanisms similar to type classes, generics in Java or templates in C++ for instance. One can use these features to implement and deploy monads even in languages that are not normally considered functional.

Conceptual definition

Altogether, a monad contains three parts:

1. A type constructor that specifies how the monadic type is built up from other pre-existing types.
2. A type converter, often called unit or return, that wraps a single variable in the monad.
3. A combinator, typically called bind (as in binding a variable), that unwraps a monadic variable, inserts it into an expression, then rewraps it all in the monad.

To fully qualify as a monad, these three parts must also respect a few laws, which the programmer should check (and ideally prove) independently. These laws intuitively come down to...

1. Converting a variable with $unit$ only to immediately $bind$ it to a function should be redundant and no different from just applying the function to the original variable.
2. Using $bind$ to feed an already monadic variable to $unit$ itself is also redundant and should have no effect.
3. When $bind$ is used repeatedly to chain functions, the order of evaluation for $bind$ ifself should be irrelevant.

The upshot is that when all these criteria are satisfied, a monad can reify any computation characterized by its type constructor. This in turn allows structuring a program concisely, even with side-effects, while keeping the rigor and flexibility of purely functional programming.

Utility

The monad pattern has proven valuable for combining abstract usability with functional precision in many diverse scenarios, not limited to:

• Exception handling and control flow
• Managing data structures
• Variable assignment
• Parsing, domain-specific languages, and language bindings
• Containing "impure" features, such as input/output or mutable state
• Object models for graphical user interfaces

Oftentimes, programmers will use $bind$ to chain functions on the monad into a sequence, which has led some to describe monads as "programmable semicolons", a reference to how many imperative languages use semicolons to separate statements. Monads, however, do not actually order program flow so much as encapsulate additional logic that interlaces with other formalisms (like currying). Some monads can pass along extra data that is inaccessible to functions, and some even exert finer control over execution, for example only calling a function under certain conditions. Their general utility lies in simplifying a program's structure and improving separation of concerns through abstraction.

Especially in purely functional programming, functions cannot rely on state without complex workarounds, nor should order of evaluation matter. Only explicit function composition should impose a sequence on computations. Functional languages can still express these other situations, including impure computations and strict evaluation, through a complex scaffold of function composition and continuation-passing style (CPS). With monads though, much of this scaffolding can be abstracted away, essentially by bundling each recurring pattern from the CPS code into a distinct monad. Since this lets application programmers implement domain logic while offloading bookkeeping onto pre-developed modules, monads can even be considered a tool for aspect-oriented programming.

An example: Maybe

A very common issue for robust programs is preparing for undefined operations or variables. This turns out to be a very natural application for a monad, specifically one known as the Maybe monad.

To start, an option type Maybe can be defined to contain either a value, of any type, or an undefined value Nothing. The word Just will also mark a plain value embedded in Maybe to avoid any confusion with unembedded values:

newtype Maybe T  =  Just T or Nothing

We would like to use this type as a simple checked exception: if the computation becomes undefined at any point, it will short-circuit and return Nothing. If all steps of the calculation succeed though, the final result should just be the correct value.

Consider an addition function add that should do exactly this when adding two Maybe variables, mx and my. Using a naive approach to define the function for all cases will lead to a tedious series of conditionals though:

add : (Maybe Number, Maybe Number)  →  Maybe Number

add(mx, my)  =  ...
    if mx is Nothing then
        ... Nothing
    else if my is Nothing then
        ... Nothing
    else
        ... Just(x + y)
    end if

To alleviate this, we can define an operation for chaining the steps together; we'll use the infix symbol >>= and define it to feed a (possibly undefined) result from each step into the next. Since we are technically inserting the result into another function, we will take a function as input to our operator. The add function already fixes down the underlying types for us too so we may as well allow this operator to output a different type from the input:

>>= : (Maybe T, (T → Maybe U))  →  Maybe U

(ma >>= f)  =  ...
    if ma is (Just a) then
        ... f(a)
    else
        ... Nothing
    end if

We can now redefine add as something much more compact:

add(mx, my)  =  mx >>= (my >>= Just(x + y))

This is more elegant, but a little extra analysis reveals something far more powerful. For one, notice that within either version of add, Just is only needed to tag a plain value as now a Maybe value. To emphasize how Just merely wraps existing values, we can treat it as a function too, which we'll call eta for now:

eta : T  →  Maybe T

eta(x)  =  Just x

The key insight is that now we have two functions, >>= and eta, which greatly simplified add but without any specific dependence on its semantics whatsoever. We can, in fact, apply these functions to simplify any code that acts on Maybe, even if the underlying types are entirely different. For example, here is a concise NOT operator from (Kleene's) trinary logic that completely automates undefined values:

trinot : Maybe Boolean  →  Maybe Boolean

trinot(mp)  =  mp >>= eta(not(p))

This Maybe type along with its two functionals is a monad, >>= acting as $bind$ and eta as $unit$. Other monads will embody different logical processes, and some monads have extra properties that can make them more powerful, but all of them follow the basic outline of this example.

History

The term "monad" in programming actually goes all the way back to the APL and J programming languages, which do tend toward being purely functional. However, in those languages, "monad" was simply shorthand for a function taking one parameter (a function with two parameters being a "dyad", and so on). This usage predates the first discussions of programming with true monads by decades and is roughly contemporaneous with the first work on monads in category theory.

The mathematician Roger Godement was the first to formulate the concept of a monad in the late 1950s. Over the next decades, as theorists developed the idea further, the term "monad" due to mathematician and leading category-theorist Saunders Mac Lane came to dominate.

Starting in the 1980s, a vague notion of a monad pattern began to surface in the computer science community. According to programming language researcher Philip Wadler, computer scientist John C. Reynolds anticipated several facets of it in the 70s and early 80s; Reynolds had discussed the value of continuation-passing style, category theory as a rich source for program semantics, and the type distinction between values and computations. The research language Opal, which was actively designed up until 1990, also effectively based I/O on a monadic type although the connection was not realized at the time.

The computer scientist Eugenio Moggi was the first to make an explicit link between the monad of category theory and functional programming, in a conference paper in 1989, followed by a more refined journal submission in 1991. In earlier work, several computer scientists had advanced the idea of using category theory to provide general semantics for the lambda calculus. Moggi's key insight was that a real-world program is not just a function that maps values to other values, but rather a transformation that forms computations on those values. When formalized in category-theoretic terms, this leads to the conclusion that a monad is the structure to represent these computations.

Several others popularized and built on this idea, including Philip Wadler and Simon Peyton Jones, both of whom were involved in the specification of Haskell. In particular, early versions of Haskell used a problematic "lazy list" model for I/O, and Haskell 1.3 introduced a monadic interface as a more flexible way to combine I/O with lazy evaluation. Besides I/O, the Haskell community successfully applied monads to a wide range of design problems, including imperative syntax sugar (known in Haskell as "do-notation"). Researchers working with Haskell also eventually generalized the monad pattern into a wider hierarchy of structures, including applicative functors and arrows.

At first, programming with monads was largely confined to Haskell and its derivatives, but as functional programming has influenced other paradigms, many languages have incorporated a monad pattern (in spirit if not in name). Formulations now exist in Scheme, Perl, Python, Racket, Clojure, Scala, F#, and have also been considered for a new ML standard.

Formal definition

Since monads are ultimately mathematical objects, working from a formal definition can dodge some subtler pitfalls and inject more rigor into a program. Within computer science, a couple different definitions have become standard, and though one or the other may be more convenient in a given situation, they are both equivalent. Whichever one a programmer chooses, the formal definition allows verifying a program's logic and in some cases, optimizing code through rewriting.

Kleisli triple

The more common definition in functional programming, used in the Maybe example, actually differs from the standard definition of category-theory. Instead, the package of type constructor, $unit$, and $bind$ makes up what is known as a Kleisli triple. These three components turn out to characterize a specific monad anyways though, so the triple can act as an alternate definition.

To formalize the concept, we will first pin down the three components. For any well-defined types T,U:

• The type constructor M marks a new higher-order type M T
• $unit$ defines a specific procedure to embed any object a of type T into a monad with type M T:

unit(a) : T → M T

• $bind$ (expressed as >>=) defines how to insert any monadic object ma of type M T (including a first-class function with that output) into any function f : T → M U:

(ma >>= f) : (M T, (T → M U))  →  M U

If this seems like unnecessary hair-splitting, the added value comes from now formalizing the monad laws with the same symbols:

unit(a) >>= f(x)  ==  f(a)
ma >>= unit(x)    ==  ma
mx >>= (f(x) = my >>= g(y) = mz)  ==  (mx >>= f(x) = my) >>= g(y) = mz

Now that we have a solid foundation to start from, we can analyze monads with much more precision.

Verifying the monad laws

Returning to the Maybe example, while its components were matched to the required parts of a monad, there was no demonstrative proof it satisfies the monad laws. Now with a formal definition, this can be rectified:

Law 1:  eta(a) >>= f(x)  ==  (Just a) >>= f(x)
        ==  f(a)

Law 2:  ma >>= eta(x)  ==  Nothing >>= eta(x)               ==  Nothing ...
    or                 ==  (Just a) >>= eta(x)  ==  eta(a)  ==  Just a
        ==  ma

Law 3:  (ma >>= f(x)) >>= g(y)  ==  (Nothing) >>= g                           ==  Nothing ...
    or                          ==  f(a) = my >>= g(y)  ==  Nothing >>= g(y)  ==  Nothing ...
    or                                                  ==  g ∘ f(a)          ==  ma >>= (g ∘ f(x))
        ==  ma >>= (f(x) = my >>= g(y))

Note how the proof procedure takes the specifics of Maybe, then applies them as rewrite-rules to one side of each law's equation. The proof succeeds if an algebraic chain of equalities can reach the other side of the law in question.

Derivation from functors

Although computer scientists usually define monads by way of Kleisli triples, one can also use the standard definition from category theory as a recipe. Mathematically, a monad is actually just a functor with two additional natural transformations, one of which is the $unit$ functional already described. As a result, this approach only differs from the Kleisli triple by replacing $bind$ with the other transformation.

A second functional map is also necessary, but this is typically not a major inconvenience since it is defined for all functors; if a monad is derived from a functor instead of defined from scratch, $map$ is inherited automatically from the parent functor. Details can be found in the article for the map functional, but one key point is that $map$ can act on any mapping, not just functions with monadic output like $bind$:

map(h) : (a → b)  →  (ma → mb)

If the class hierarchy is followed closely, it turns out $unit$ isn't truly unique to monads either, but rather to applicative functors, an intermediate structure between a monad and a vanilla functor. In the applicative context, $unit$ is sometimes referred to as pure, but is effectively the same operator. The only effective difference from the derivation based on Kleisli triples is that without $bind$, $unit$ must respect a different law in terms of $map$:

unit ∘ h(x)  ==  (map h) ∘ unit(x)

The real leap from applicative functor to monad comes with the join functional, which does characterize the resulting monad:

• $join$ allows "flattening" repeated applications of the monadic functor:

join(mma) : M (M T) → M T

As the characteristic functional, $join$ must also satisfy three variations on the monad laws:

join ∘ (map join) mmma    ==  join ∘ join(mmma)    ==  ma
join ∘ (map unit) ma      ==  join ∘ unit(ma)      ==  ma  
join ∘ (map ∘ map h) mma  ==  (map h) ∘ join(mma)  ==  mb

A developer may pick either way to define a monad, but the results are mathematically the same, and if necessary, deriving components of one form from the other is very straight-forward:

(map h) ma   ==  ma >>= (unit ∘ h(x))
join(mma)    ==  mma >>= id(x)

ma >>= f(x)  ==  join ∘ (map f) ma

Another example: List

The complex multivalued square and cube root functions may be composed so they produce the sixth root function. The structure that governs the type of input and output and the structure that composes the different operations are, together, a list monad.

A monad that demonstrates the alternative definition's usefulness, and how diverse monads are, is the List monad; yes, the standard list structure does in fact become a monad so long as we provide the necessary parts. With a basic $append$ operator ++, the type constructor can follow the typical recursive definition:

List T  =  []  or  T ++ (List T)

Embedding a plain value in a list is also trivial in most languages:

unit(x)  =  [x]

At first glance, applying a function iteratively with a list comprehension may seem like an easy choice for $bind$ too. However, this solution won't work as-is because $bind$ expects functions with monadic output, i.e. more (possibly non-trivial) lists. To maintain a true list, $bind$ must flatten any resulting nested structure after iterating over the input. Thankfully, these two tasks match up with $map$ and $join$:

(map h) xlist    =  [ h(x1), h(x2), ..., h(xn) ]
join(xlistlist)  =  xlist1 ++ xlist2 ++ ... ++ xlistn

Now with these functionals defined, $bind$ comes from the equivalence formulas automatically:

(xlist >>= f)  =  join ∘ (map f) xlist

One scenario for this monadic list is representing nondeterministic computation. List can hold results from each step in an algorithm for all execution paths, then condense itself to "forget" which paths led to which results (a sometimes important distinction from deterministic, exhaustive algorithms). Another benefit is that checks can be included in List's definition, stopping and removing paths at their first point of failure, without any changes to functions in the pipeline. In languages with lazy evaluation, list elements are only generated as needed, which can also notably improve efficiency.

A second situation where List shines is composing multivalued functions. For instance, consider the complex roots of a number: the nth root of a number will return n distinct complex numbers, but if another mth root of those results is taken, the final m•n values should be identical to the output of the m•nth root function. List completely automates this issue away, condensing the results from each step into a flat, mathematically correct list.

Techniques

Monads present opportunities for some other interesting techniques beyond just organizing program logic. Since monads preserve referential transparency, they can lay the groundwork for useful syntactic features while their abstract and mathematical nature enable some very powerful higher-order functions.

Syntax Sugar

Although it often makes sense to use $bind$ directly, many programmers use a special format that mimics imperative statements (called do-notation in Haskell, perform-notation in OCaml, computation expressions in F#, and for comprehension in Scala). This is only syntactic sugar that allows writing sequential statements within a code block; the compiler will then quietly translate these expressions into more functional, monadic code.

To see this feature in action, consider the add function from the Maybe example. If we wanted to implement the non-monadic version in Haskell, it would be:

add mx my =
    case mx of
        Nothing -> Nothing
        Just x  -> case my of
                       Nothing -> Nothing
                       Just y  -> Just (x + y)

In monadic Haskell, return is the standard name for $unit$, plus lambda expressions must be handled explicitly. Even with these technicalities, the Maybe monad still makes for a cleaner definition:

add mx my =
    mx >>= (\x ->
        my >>= (\y ->
            return (x + y)))

With do-notation though, we can distill this even further into a very intuitive sequence:

add mx my = do
    x <- mx
    y <- my
    return (x + y)

Here is a second example that also uses Maybe but in an entirely different language: F#. It implements a "safe division" function (returning None if either operand is undefined or division by zero occurs) using computation expressions:

let readNum () =
  let s = Console.ReadLine()
  let succ,v = Int32.TryParse(s)
  if (succ) then Some(v) else None

let secure_div = 
  maybe { 
    let! x = readNum()
    let! y = readNum()
    if (y = 0) 
    then None
    else return (x / y)
  }

At build-time, the compiler will internally "de-sugar" this function into a denser chain of $bind$ calls:

maybe.Delay(fun () ->
  maybe.Bind(readNum(), fun x ->
    maybe.Bind(readNum(), fun y ->
      if (y=0) then None else maybe.Return(x / y))))

For a last example, note that even the general monad laws themselves can be expressed in do-notation:

do { x <- return v; f x }            ==  do { f v }
do { x <- m; return x }              ==  do { m }
do { y <- do { x <- m; f x }; g y }  ==  do { x <- m; y <- f x; g y }

Exactly how various languages sugarcoat monads are beyond the scope of this article, but a developer should always remember that it is purely a syntactic convenience. Imperative-style blocks can always be replaced with direct monadic (or even non-monadic CPS) expressions. While these blocks are convenient in many situations, such as assigning/binding several variables (which would otherwise require a great deal of nesting), $bind$ can be clearer and shorter just as often. Some functional programming advocates even argue that since this syntax sugar allows novices to carry over poor habits and assumptions from imperative programming, it should be avoided by default and only used when obviously superior.

Monad concept

Every monad has a specific implementation that defines the required operators and meets the monad laws, but these criteria aren't the only features of a monad. For example, functionals like $map$ and $join$ can be automatically derived; many languages have also settled on a standard idiom for features that all monads share.

As a result, it makes sense for a language to provide a generic concept or template to build specific monads from. Besides simplifying development and guaranteeing a new monad inherits relevant features from superclasses (such as functors), matching a specification adds another layer of quality control.

For example, Haskell provides a general monad class in its base libraries. Not only does the type class derive from an applicative functor class, but several useful functions and operators are pre-defined in terms of the $bind$ functional, plus the type class provides type signatures to improve type safety.

Bonus functionals

On top of the functionals already mentioned, several other handy ones can be defined for monads in general.

One inconvenience of the monad pattern that might have already come to mind is redefining functions to output monadic types. Fortunately, so long as a monadic function operates on the underlying values the same as some simpler function, it can be defined generically with lift. It essentially does what it says, "lifting" a function or operator from a basic version to a monadic one.

To see $lift$ in action, consider the add function for Maybe numbers once more. However much using $bind$ or do-notation simplified the definition, $lift$ can distill it even further into the very concise:

add(mx, my)  =  lift(+)

Even this is not the full power of $lift$ though; since it is a capability of monads in general, this definition can work for all monads that satisfy the Monad class specification, not just Maybe. The above definition doesn't even need changing, only the type signature for add needs to be generalized:

add : (Monad Number, Monad Number)  →  Monad Number

Another higher-order operator, which can be useful in analysis just as much as applications, is monadic function composition. This operator allows chaining functions even more naturally, especially if variable binding must be done explicitly. For example, if the symbol >=> is used for the composition operator, the monad laws can be converted to an especially insightful form:

(f >=> g) x  =  (f(x) = my) >>= g(y)

(unit >=> g)     ==  g
(f >=> unit)     ==  f
(f >=> g) >=> h  ==  f >=> (g >=> h)

This version of the laws makes it very clear that they amount to associative composition and $unit$ being a two-sided identity.

Variations

At a purely mathematical level, some monads have nice properties that make them even more powerful. This section includes a few significant cases.

Additive monads

An additive monad is a monad endowed with a closed, associative, binary operator mplus and an identity element under $mplus$, called mzero. In other words, an additive monad also qualifies as a monoid in regards to $mplus$.

The reason for calling the identity as a "zero", rather than a "one", is that $mzero$ does act as an absorber for $bind$. Just as multiplying any number by 0 results in 0, binding $mzero$ with any function yields $mzero$. This property is two-sided, also coming into play if one binds a non-empty monad to a zero function.

Intuitively, $mzero$ represents a monadic wrapper with no value from an underlying type. So the Maybe monad can be considered additive, with Nothing as $mzero$ and a variation on the OR operator as $mplus$. List is also an additive monad, with the empty list [] acting as $mzero$ and the concatenation operator ++ as $mplus$

The free monad

In some situations, the general features of a monad may be useful but there is no specific pattern to recommend one kind or another. This is where the free monad comes in. The free monad is unique because it doesn't implement any particular semantics like other monads. Instead, it is a free object in the class of monads, an entirely formal object that satisfies the laws of its class without any evaluation or deeper assigned meaning.

Perhaps the most direct explanation for the free monad begins from the fact that all monads are monoids over functors. Just as a free monoid simply concatenates elements into a string without evaluation, the free monad provides a handle to compose and navigate chains of functors.

In code, this means a free monadic type expresses nested functors with the bare minimum needed to satisfy the type system. For example, a recursive and linear definition for a free monad might look like this, with type markers standing in for $unit$ and $bind$:

new type (Free F(T))  =  Unit T or Bind (Free G(U), F)

At first, this may seem like a solution in search of a problem, but many syntactic operations suit the free monad's formal nature. Whenever syntax and type are processed in separate phases, a free monad can work on computational chains while leaving semantics for later. As a result, it is often used in parsers and interpreters for domain-specific languages, and others have applied them to more dynamic problems, such as iteratees.

Comonads

Besides generating monads with extra properties, for any given monad, one can also define a comonad. This is just a categorical dual, which loosely means that it will have the same required components, only with the direction of the type signatures reversed. So if we start from the $bind$-centric definition of a monad, a comonad consists of:

• A type constructor W that marks the higher-order type W T
• An inversion of $unit$ that extracts the underlying value from the comonad:

extract (wa) : W T -> T

• A reversal of $bind$ that extends a chain of reducing functions on comonadic values:

extend (wa,f) : (W U, W U -> T) -> W T

The $extend$ and $extract$ functionals must also satisfy duals of the monad laws:

extract ∘ extend (wa,f)    ==  f(wa)
extend (wa, extract)       ==  wa
extend (extend (wa,f), g)  ==  extend (wa, λx.extend (f(x), g))

Analogous to monads, comonads can also be derived using a dual of $join$:

• $duplicate$ takes an already comonadic value and wraps it in another layer of comonadic structure:

duplicate (wa) : W T -> W (W T)

A definition by $duplicate$, $extract$, and $map$ must also respect duals of the alternative laws:

(map duplicate) ∘ duplicate  ==  duplicate ∘ duplicate
(map extract) ∘ duplicate    ==  extract ∘ duplicate    ==  id
((map ∘ map) f) ∘ duplicate  ==  duplicate ∘ (map f)

And as with monads, the two sets of functionals can be converted automatically:

(map f) wwa     ==  extend (wwa, f ∘ extract)
duplicate wb    ==  extend (wb, id)

extend (wc, g)  ==  (map g) ∘ duplicate(wc)

Conceptually, if monads represent computations built up from underlying values, then comonads can be seen as reductions back down to values. One limitation of monadic code is that it can't, in a sense, be fully "unpacked"; once a first-order value is embedded into a monad, it remains quarantined inside the monad along with any side-effects (a good thing in purely functional programming). Sometimes though, a specific problem or paradigm is really more concerned with consuming contextual data to yield basic values. It turns out that comonads are ideal for modeling this logic in explicit code.

One simple example is the product comonad, which outputs values based on an input value and shared environment data. A less trivial example is the stream comonad, which is essentially dual to List. Rather than emphasizing concatenation, however, Stream uses $extract$ to consume elements from the front of the queue. Perhaps the real power of Stream comes from using $extend$ though, where each comonadic function filters the incoming data stream. In fact, while not as popular as monads, researchers have found comonads particularly useful for processing data streams and modeling the semantics of dataflow programming languages.

Since monads and comonads are both mathematically strict, one cannot simply move objects back and forth between the two. As an even higher abstraction, (Hughes) arrows can encompass both structures, but finding more concrete ways to combine monadic and comonadic code is an active area of research.

More examples

Identity monad

The simplest monad is the identity monad, which attaches no information to values but still satisfies the monad laws:

new type Id T  =  T

unit(x)    =  x
(x >>= f)  =  f(x)

The Identity monad does actually have valid uses though, such as providing a base case for recursive monad transformers. It can also be used to perform basic variable substitution within an imperative-style block.

Collections

As we saw above, a list is actually a monad too, particularly since it has a well-defined procedure for flattening nested structure. It turns out this is true for several familiar collection types; in fact, while every monad is technically a monoid, collections with a concatenation operator are free monoids.

By picking special properties under concatenation, we can even characterize a specific collection:

Collection	Monoid properties
List	Free
Finite multiset	Commutative
Finite set	Commutative & idempotent
Finite permutations	Non-commutative & idempotent

I/O monad (Haskell)

As already mentioned, functions should not have any unmanaged side effects in pure code, but that does not exclude a function from explicitly describing an effect, then passing this handle through the program for later use. This idea is at the heart of Haskell's IO monad, where an object of type IO can be seen as containing the current state of the world outside the program. When a programmer binds an IO monad to a function, the function can make decisions based on a view of the world (user or system input), then yield a new world-state as a monadic value (program output).

For example, Haskell has several functions for acting on the wider file system, including one that checks whether a file exists and another that deletes a file. Their two type signatures are:

doesFileExist :: FilePath -> IO Bool
removeFile :: FilePath -> IO ()

Since the first is interested in whether a given file actually exists, a true or false question about the outside world, it embeds a boolean value within the IO monad. The second function, on the other hand, is only concerned with the action on the file system. As a result, it wraps an undefined value in the IO structure because only the outside action is relevant.

The IO monad does not restrict us to file I/O though; we can even use it to mimic a typical "Hello, World!" program like in imperative languages:

main :: IO ()
main = do
  putStrLn "Hello, world!"
  putStrLn "What is your name, user?"
  name <- getLine
  putStrLn ("Nice to meet you, " ++ name ++ "!")

Desugared, this translates into the following monadic pipeline:

main :: IO ()
main =
  putStrLn "Hello, world!" >>
  putStrLn "What is your name, user?" >> 
  getLine >>= (\name ->
    putStrLn ("Nice to meet you, " ++ name ++ "!"))

Writer monad (Javascript)

Another common situation is keeping a log file or otherwise updating the user about a program's progress. Sometimes, a programmer may want to log even more specific, technical data for later profiling or debugging. The writer monad can handle these tasks by generating auxiliary output that accumulates step-by-step.

To show how the monad pattern isn't restricted to primarily functional languages, we can implement and use a Writer monad in Javascript. First, we will use an array (with nested tails) to construct our Writer type as a linked list. The underlying output value will live in position 0 of the array, and position 1 will implicitly hold a chain of auxiliary notes:

const writer = [value, []];

Defining $unit$ is also very simple:

const unit = value => [value, []];

Now that we have settled on how to embed values into the monadic type, we can define some sample functions that will output Writer objects with debugging notes:

const squared = x => [x * x, [`${x} was squared.`]];
const halved = x => [x / 2, [`${x} was halved.`]];

To have a true monad though, we still need to define $bind$, but in this case, this is just a matter of properly appending a function's results into a Writer object's linked list:

const bind = (writer, transform) => {
    const [value, log] = writer;
    const [result, updates] = transform(value);
    return [result, log.concat(updates)];
};

With this done, the sample functions can now be chained together using $bind$. However, by defining a version of monadic composition (we will call it pipelog), we can apply our functions in an even more succinct notation:

const pipelog = (writer, ...transforms) =>
    transforms.reduce(bind, writer);

The final result is a clean separation of concerns between stepping through the computations and logging them to audit later on:

pipelog(unit(4), squared, halved);
// Resulting writer object = [8, ['4 was squared.', '16 was halved.']]

Environment monad

An environment monad (also called a reader monad and a function monad) allows a computation to depend on values from a shared environment. The monad type constructor maps a type T to functions of type E → T, where E is the type of the shared environment. The monad functions are:

${\begin{array}{ll}{\text{return}}\colon &T\rightarrow E\rightarrow T=t\mapsto e\mapsto t\\{\text{bind}}\colon &(E\rightarrow T)\rightarrow (T\rightarrow E\rightarrow T')\rightarrow E\rightarrow T'=r\mapsto f\mapsto e\mapsto f\,(r\,e)\,e\end{array}}$

The following monadic operations are useful:

${\begin{array}{ll}{\text{ask}}\colon &E\rightarrow E={\text{id}}_{E}\\{\text{local}}\colon &(E\rightarrow E)\rightarrow (E\rightarrow T)\rightarrow E\rightarrow T=f\mapsto c\mapsto e\mapsto c\,(f\,e)\end{array}}$

The ask operation is used to retrieve the current context, while local executes a computation in a modified subcontext. As in a state monad, computations in the environment monad may be invoked by simply providing an environment value and applying it to an instance of the monad.

State monads

A state monad allows a programmer to attach state information of any type to a calculation. Given any value type, the corresponding type in the state monad is a function which accepts a state, then outputs a new state (of type s) along with a return value (of type t). This is similar to an environment monad, except that it also return a new state, and thus allows modeling a mutable environment.

type State s t = s -> (t, s)

Note that this monad, unlike those already seen, takes a type parameter, the type of the state information. The monad operations are defined as follows:

-- "return" produces the given value without changing the state.
return x = \s -> (x, s)
-- "bind" modifies m so that it applies f to its result.
m >>= f = \r -> let (x, s) = m r in (f x) s

Useful state operations include:

get = \s -> (s, s) -- Examine the state at this point in the computation.
put s = \_ -> ((), s) -- Replace the state.
modify f = \s -> ((), f s) -- Update the state

Another operation applies a state monad to a given initial state:

runState :: State s a -> s -> (a, s)
runState t s = t s

do-blocks in a state monad are sequences of operations that can examine and update the state data.

Informally, a state monad of state type S maps the type of return values T into functions of type $S\rightarrow T\times S$, where S is the underlying state. The return and bind function are:

${\begin{array}{ll}{\text{return}}\colon &T\rightarrow S\rightarrow T\times S=t\mapsto s\mapsto (t,s)\\{\text{bind}}\colon &(S\rightarrow T\times S)\rightarrow (T\rightarrow S\rightarrow T'\times S)\rightarrow S\rightarrow T'\times S\ =m\mapsto k\mapsto s\mapsto (k\ t\ s')\quad {\text{where}}\;(t,s')=m\,s\end{array}}$.

From the category theory point of view, a state monad is derived from the adjunction between the product functor and the exponential functor, which exists in any cartesian closed category by definition.

Continuation monad

A continuation monad with return type $R$ maps type $T$ into functions of type $\left(T\rightarrow R\right)\rightarrow R$. It is used to model continuation-passing style. The return and bind functions are as follows:

${\begin{array}{ll}{\text{return}}\colon &T\rightarrow \left(T\rightarrow R\right)\rightarrow R=t\mapsto f\mapsto f\,t\\{\text{bind}}\colon &\left(\left(T\rightarrow R\right)\rightarrow R\right)\rightarrow \left(T\rightarrow \left(T'\rightarrow R\right)\rightarrow R\right)\rightarrow \left(T'\rightarrow R\right)\rightarrow R=c\mapsto f\mapsto k\mapsto c\,\left(t\mapsto f\,t\,k\right)\end{array}}$

The call-with-current-continuation function is defined as follows:

${\text{call/cc}}\colon \ \left(\left(T\rightarrow \left(T'\rightarrow R\right)\rightarrow R\right)\rightarrow \left(T\rightarrow R\right)\rightarrow R\right)\rightarrow \left(T\rightarrow R\right)\rightarrow R=f\mapsto k\mapsto \left(f\left(t\mapsto x\mapsto k\,t\right)\,k\right)$

See also

• Arrows in functional programming – whereas monads generalize the results of a computation to effects, arrows further generalize the inputs similarly
• Aspect-oriented programming – a paradigm to increase modularity by isolating secondary or supporting functionality
• Effect system – an alternative way of describing side effects as types
• Inversion of control – the abstract principle of calling specific functions from a reusable software entity
• Monad transformers – which allow monads to be composed in a modular and convenient way
• Uniqueness types - an alternative way of dealing with side-effects in functional languages
• xmonad – an Xwindows tiling windows manager programmed in Haskell using a monad design pattern

External links

Haskell monad tutorials

• Monad Tutorials Timeline Probably the most comprehensive collection of links to monad tutorials, ordered by date.
• Piponi, Dan (August 7, 2006). "You Could Have Invented Monads! (And Maybe You Already Have.)". A Neighborhood of Infinity. — The most famous "blog post" tutorial.
• Yorgey, Brent (12 March 2009). "The Typeclassopedia" (PDF). The Monad.Reader (13): 17–68. — An attempt to explain all of the leading typeclasses in Haskell in an elementary way, with monadic functors considered as only one form, best understood by comparison with others: e.g., the more general idea of a "Functor" as something you can map over; "Applicative" functors, and so forth; contains an extensive bibliography.
• Yorgey, Brent (January 12, 2009). "Abstraction, intuition, and the "monad tutorial fallacy"". blog :: Brent -> [String]. WordPress.com. — Opposes the idea of making a tutorial about monads in particular.
• What a Monad is not deals with common misconceptions and oversimplifications in a humorous way.
• beelsebob (March 31, 2009). "How you should(n't) use Monad". No Ordering. WordPress.com. — Takes a similar point of view, locating monads in a much wider array of Haskell functor classes, of use only in special circumstances.
• Vanier, Mike (July 25, 2010). "Yet Another Monad Tutorial (part 1: basics)". Mike's World-O-Programming. LiveJournal. — An extremely detailed set of tutorials, deriving monads from first principles.
• "A Fistful of Monads". An explanation of Monads, building on the concepts of Functors, Applicative Functors and Monoids discussed in the previous chapter.
• Functors, Applicatives and Monads in Pictures. A humorous beginner's guide to monads.

Older tutorials

• All About Monads
• Haskell Wiki: Monads as Computation
• Haskell Wiki: Monads as Containers
• Norvell, Theodore. "Monads for the Working Haskell Programmer". Memorial University of Newfoundland.
• Klinger, Stefan (15 December 2005). "The Haskell Programmer's Guide to the IO Monad — Don't Panic" (PDF) (5–54). Centre for Telematics and Information Technology, University of Twente. ISSN 1381-3625. {{cite journal}}: Cite journal requires |journal= (help)
• Turoff, Adam (August 2, 2007). "Introduction to Haskell, Part 3: Monads". ONLamp. O'Reilly Media.
• Monads A monad tutorial providing examples of non-trivial monads apart from the conventional IO/Maybe/List/State monads.
• Söylemez, Ertugrul (2010-07-11). "Understanding Haskell Monads".

Other documentation

• van Tuyl, Henk-Jan (2010-02-27). "A tour of the Haskell monad functions".
• Moggi, Eugenio. "Notions of computation and monads" (PDF). {{cite journal}}: Cite journal requires |journal= (help) — The original paper suggesting use of monads for programming
• Wadler, Philip (August 2001). "Monads for functional programming" (PDF). University of Glasgow. {{cite journal}}: Cite journal requires |journal= (help) — Describes monads in Haskell (before they were implemented)

Scala monad tutorials

• League, Chris (July 12, 2010). Monadologie: Professional Help for Type Anxiety (flv) (Tech talk). New York City: New York Scala Enthusiasts.
• Morris, Tony (June 22, 2010). "Understanding Monads using Scala (Part 1)". λ Tony’s blog λ.
• Iry, James (September 18, 2007). "Monads are Elephants".
• Meredith, Gregory (April 25, 2010). "Pro Scala: Monadic Design Patterns for the Web" (PDF) (1st ed.). p. 300.