Wikibooks Haskell has a page on the topic of

Understanding monads

Some functional programming languages make use of monads^{[1] [2]} to structure programs which include operations that must be executed in a specific order. The name monad derives from category theory, a branch of mathematics that describes patterns applicable to many mathematical fields. Image File history File links Wikibooks-logo-en. ... Wikibooks logo Wikibooks, previously called Wikimedia Free Textbook Project and Wikimedia-Textbooks, is a wiki for the creation of books. ... Functional programming is a programming paradigm that treats computation as the evaluation of mathematical functions and avoids state and mutable data. ... In category theory, a monad or triple is a type of functor, together with two associated natural transformations. ... In mathematics, category theory deals in an abstract way with mathematical structures and relationships between them. ... For other meanings of mathematics or uses of math and maths, see Mathematics (disambiguation) and Math (disambiguation). ...

The primary uses of monads in functional programming are to express input/output (I/O) operations and changes in state without using language features that introduce side effects^[3]. They exploit a loophole that, although a function cannot directly cause a side effect, it can construct a value describing a desired side effect that the caller should apply at a convenient time. However, I/O and state management are by no means the only uses of monads. They are useful in any situation where the programmer wants to carry out a purely functional computation while a related computation is carried out "on the side." Energy Input: The energy placed into a reaction. ... In the theory of computation, a finite state machine (FSM) or finite state automaton (FSA) is an abstract machine that has only a finite, constant amount of memory. ... In computer science, a function is said to produce a side effect if it modifies some state other than its return value. ...

The Haskell programming language is a functional language that makes heavy use of monads, and includes syntactic sugar to make monad composition more convenient. All of the code samples below are written in Haskell unless noted otherwise. Haskell is a standardized purely functional programming language with non-strict semantics, named after the logician Haskell Curry. ... Syntactic sugar is a term coined by Peter J. Landin for additions to the syntax of a computer language that do not affect its functionality but make it sweeter for humans to use. ...

Motivation

Before discussing the details of monads, it might help to give a motivating example. Consider a function that is undefined for some known values, such as division. Division might occur repeatedly in a calculation, like this one, which returns the resistance of two electrical resistors in parallel: In mathematics, a partial function is a relation that associates each element of a set (sometimes called its domain) with at most one element of another (possibly the same) set, called the codomain. ... In mathematics, especially in elementary arithmetic, division is an arithmetic operation which is the inverse of multiplication. ...

 -- par is a function that takes two real numbers and returns another par :: Float -> Float -> Float par x y = 1 / ((1 / x) + (1 / y)) 

Instead of avoiding any errors by checking whether each divisor is zero, it might be convenient to have a modified division operator that does the check implicitly, as in the following pseudocode: Pseudocode (derived from pseudo and code) is a compact and informal high-level description of a computer programming algorithm that uses the structural conventions of programming languages, but omits detailed subroutines, variable declarations or language-specific syntax. ...

 -- // is an operator that takes two "Maybe Float"s and returns another. -- "Maybe Float" extends the Float type to represent calculations that may fail. (//) :: Maybe Float -> Maybe Float -> Maybe Float x // y = ... -- the definition appears below. par :: Float -> Float -> Maybe Float par x y = 1 // ((1 // x) + (1 // y)) -- types do not actually match -- see below for correct version 

With the // operator, dividing by zero anywhere in the computation will result in the entire computation returning a special value of the Maybe monad called "Nothing", which indicates a failure to compute a value. Otherwise, the computation will produce a numerical result, contained in the other Maybe value, which is called "Just". The result of this division operator can then be passed to other functions. This concept of "maybe values" is one situation where monads are useful.

Concepts

Definition

A monad is a construction that, given an underlying type system, embeds a corresponding monadic type system into it (that is, each monadic type is also an underlying type). This monadic type system preserves all significant aspects of the underlying type system, while adding features particular to the monad. In computer science, a type system defines how a programming language classifies values and expressions into types, how it can manipulate those types and how they interact. ...

In practical terms, a monad, unlike your everyday function result, stores function results and side-effect representations. This allows side effects to be propagated through the return values of functions without breaking the pure functional model. Haskell's Maybe monad can either have a normal return value, or Nothing. Similarly, Error monads can have a normal return value or an error value.

The usual formulation of a monad for programming is known as a Kleisli triple, and has the following components:

1. A type construction that defines, for every underlying type, how to obtain a corresponding monadic type. In Haskell's notation, the name of the monad represents the type constructor. If M is the name of the monad and t is a data type, then "M t" is the corresponding type in the monad.
2. A unit function that maps a value in an underlying type to a value in the corresponding monadic type. The result is the "simplest" value in the corresponding type that completely preserves the original value (simplicity being understood appropriately to the monad). In Haskell, this function is called return due to the way it is used in the do-notation described later. The unit function has the polymorphic type t→M t.
3. A binding operation of polymorphic type (M t)→(t→M u)→M u, which Haskell represents by the infix operator >>=. Its first argument is a value in a monadic type, its second argument is a function that maps from the underlying type of the first argument to another monadic type, and its result is in that other monadic type. The binding operation can be understood as having four stages:
   1. The monad-related structure on the first argument is "pierced" to expose any number of values in the underlying type t.
   2. The given function is applied to all of those values to obtain values of type (M u).
   3. The monad-related structure on those values is also pierced, exposing values of type u
   4. Finally, the monad-related structure is reassembled over all of the results, giving a single value of type (M u).

Consider how these apply to the "Maybe" example. An infix is an affix inserted inside an existing word. ...

1. A Maybe type is just the underlying type, and a value representing "nothing", i.e. undefined.
   

   data Maybe t = Just t | Nothing

2. The Maybe value corresponding to an underlying value, is just that value.

   return x = Just x

3. Binding a function to something that is just a value means applying it directly to that value. Binding a function to nothing produces nothing.

   (Just x) >>= f = f x

   Nothing >>= f = Nothing

Axioms

For a monad to behave correctly, the definitions must obey a few axioms.^[4] (The ≡ symbol is not Haskell code, but indicates an equivalence between two Haskell expressions.)

• "return" must preserve all information about its argument.

  (return x) >>= f ≡ f x

  m >>= return ≡ m

• Binding two functions in succession is the same as binding one function that can be determined from them.
  

  (m >>= f) >>= g ≡ m >>= (&# 0;> f x >>= g)

In the last rule, the notation &# 0;> defines an anonymous function that maps any value x to the expression that follows. An anonymous function is a function (or a subroutine) defined, and possibly called, without being bound to a name. ...

Monadic zero

A monad can optionally define a "zero" value for every type. Binding a zero with any function produces the zero for the result type, just as 0 multiplied by any number is 0.

• mzero >>= f ≡ mzero

Similarly, binding any m with a function that always returns a zero results in a zero

• m >>= (&# 0;> mzero) ≡ mzero

Intuitively, the zero represents a value in the monad that has only monad-related structure and no values from the underlying type. In the Maybe monad, "Nothing" is a zero. In the List monad, "[]" (the empty list) is a zero.

do-notation

Although there are times when it makes sense to use >>= directly in a program, it is more typical to use a format called "do-notation" that mimics the appearance of non-functional languages. The compiler translates do-notation to expressions involving >>=. For example, the following definitions both give the value [(3,42),(3,42),(4,42),(4,42)] to a:

 a = do x <- [3..4] [1..2] return (x, 42) 

 a = [3..4] >>= (&# 0;> [1..2] >>= (y -> return (x, 42))) 

The do-block notation can be used with any monad as it is simply syntactic sugar for >>=.

The following definitions for safe division for values in the Maybe monad are also equivalent:

 x // y = do a <- x -- Extract the values "inside" x and y, if there are any. b <- y if b == 0 then Nothing else Just (a / b) 

 x // y = x >>= (a -> y >>= (b -> if b == 0 then Nothing else Just (a / b))) 

Examples

Maybe monad

The Maybe monad has already been defined above. The following definitions complete the original motivating example of the "par" function.

 add x y = do x' <- x y' <- y return (x' + y') par x y = let one = return 1 jx = return x jy = return y in one // (add (one // jx) (one // jy)) 

If the result of any division is Nothing, it will propagate through the rest of the expression.

Identity monad

The simplest monad is the identity monad, which attaches no information to values.

 Id t = t return x = x x >>= f = f x 

A do-block in this monad performs variable substitution; do {x <- 2; return 3*x} results in 6. In computer science and mathematics, a variable (pronounced ) (sometimes called an object or identifier in computer science) is a symbolic representation used to denote a quantity or expression. ...

Collections

Some familiar collection types, including lists, sets, and multisets, are monads. The definition for lists is given here. Look up collection, collect in Wiktionary, the free dictionary. ... In computer science, a linked list is one of the fundamental data structures, and can be used to implement other data structures. ... In mathematics, a set can be thought of as any collection of distinct objects considered as a whole. ... In mathematics, a multiset (or bag) is a generalization of a set. ...

 -- "return" constructs a one-item list. return x = [x] -- "bind" concatenates the lists obtained by applying f to each item in list xs. xs >>= f = concat (map f xs) -- The zero object is an empty list. mzero = [] 

In the list monad, a do-block is a list comprehension. For example, do {x <- [1..n]; return (2*x)} corresponds to the mathematical expression "(2×1,2×2,...,2×n)." In some programming languages, list comprehension is a syntactic construct for creating a list based on existing lists, analogous to the set-builder notation (set comprehension), that is, the mathematical notation such as the following: For an example, in Haskells list comprehension syntax, the example set-builder construct above...

The monads for sets and multisets support the use of set-builder notation similarly. The set monad is useful when the state of a computation is ambiguous, as in a parser that has not read enough input to decide what syntax it is reading. The parser can maintain a set that represents the possible syntaxes, and scan until the set has one item (meaning that a syntax was recognized) or no items (meaning that the input is unacceptable). In set theory and its applications to logic, mathematics, and computer science, set-builder notation is a mathematical notation for describing a set by indicating the properties that its members must satisfy. ... A parser is a computer program or a component of a program that analyses the grammatical structure of an input, with respect to a given formal grammar, a process known as parsing. ...

I/O

A monad for I/O operations is usually implemented in the language implementation rather than being defined publicly. The following example demonstrates the use of an I/O monad to interact with the user.

 do putStrLn "What is your name?" name <- getLine putStrLn ("Nice to meet you, " ++ name ++ "!") 

State transformers

A state transformer monad allows a programmer to attach state information of any type to a calculation. Given any value, the corresponding value in the state transformer monad is a function that accepts a state, then outputs another state along with a value.

 type StateTrans 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 transformer m so that it applies f to its result. m >>= f = r -> let (x, s) = m r in (f x) s 

Useful state transformers include:

 readState = s -> (s, s) -- Examine the state at this point in the computation. writeState x = s -> ((), x) -- Replace the state. 

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

 applyTrans:: StateTrans s a -> s -> (a, s) applyTrans t s = t s 

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

Others

Other concepts that researchers have expressed as monads include:

• Continuations
• Exception handling
• Graphical user interfaces
• Logging
• Interprocess communication
• Parsers
• Interpreters
• Strict evaluation
• Interfaces to code written in other languages

In computing, a continuation is a representation of some of the execution state of a program (often the call stack and the current Instruction pointer) at a certain point. ... Exception handling is a programming language construct or computer hardware mechanism designed to handle the occurrence of some condition that changes the normal flow of execution. ... GUI redirects here. ... Inter-process communication (IPC) is the exchange of data between one process and another, either within the same computer or over a network. ... A parser is a computer program or a component of a program that analyses the grammatical structure of an input, with respect to a given formal grammar, a process known as parsing. ... In computer science, an interpreter is a computer program that executes, or performs, instructions written in a computer programming language. ... Eager evaluation is the evaluation model in most traditional programming languages. ...

Alternate formulation

Although Haskell defines monads in terms of the "return" and "bind" functions, it is also possible to define a monad in terms of "return" and two other operations, "join" and "map". This formulation fits more closely with the definition of monads in category theory. The map operation, with type (t→u)→(M t→M u), takes a function between two types and produces a function that does the "same thing" to values in the monad. The join operation, with type M (M t)→M t, "flattens" two layers of monadic information into one.

The two formulations are related as follows. As before, the ≡ symbol indicates equivalence between two Haskell expressions.

 (map f) m ≡ m >>= (&# 0;> return (f x)) join m ≡ m >>= (&# 0;> x) m >>= f ≡ join ((map f) m) 

History

Eugenio Moggi first described the general use of monads to structure programs.^[5] Several people built on his work, including programming language researchers Philip Wadler and Simon Peyton Jones (both of whom were involved in the specification of Haskell). Early versions of Haskell used a problematic "lazy list" model for I/O, and Haskell 1.3 introduced monads as a more flexible way to combine I/O with lazy evaluation. Philip Wadler is a computer scientist well-known for his contributions to programming language design and type theory. ... Simon Peyton Jones is a British computer scientist who does research on the implementation and applications of functional programming languages, particularly lazy functional languages. ...

In addition to IO, scientific articles and Haskell libraries have successfully applied monads to topics including parsers and programming language interpreters. The concept of monads along with the Haskell do-notation for them has also been generalized to form arrows. In computer science, arrows provide a more general interface to computation than monads. ...

As of 2006, Haskell and its derivatives are the only major users of monads in programming. There exist formulations also in Scheme and Perl, and monads have been an option in the design of a new ML standard. 2006 is a common year starting on Sunday of the Gregorian calendar. ...

Effect systems are an alternative way of describing side effects as types. An effect system is a formal system which describes the computational effects of computer programs, such as side effects. ...

See also

• Arrows in functional programming - whereas monads generalize the results of a computation to effects, arrows further generalize the inputs similarly.

In computer science, arrows provide a more general interface to computation than monads. ...

References

1. ^ Philip Wadler. Comprehending Monads. Proceedings of the 1990 ACM Conference on LISP and Functional Programming, Nice. 1990.
2. ^ Philip Wadler. The Essence of Functional Programming. Conference Record of the Nineteenth Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages. 1992.
3. ^ Simon L. Peyton Jones, Philip Wadler. Imperative Functional Programming. Conference record of the Twentieth Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, Charleston, South Carolina. 1993
4. ^ The three fundamental laws of Monad. See this page
5. ^ Moggi, Eugenio (1991). "Notions of Computation and Monads". Information and Computation 93 (1). 

Philip Wadler is a computer scientist well-known for his contributions to programming language design and type theory. ... Simon Peyton Jones is a British computer scientist who does research on the implementation and applications of functional programming languages, particularly lazy functional languages. ...

External links

• A (hopefully) painless introduction to monads
• What the hell are Monads?
• You Could Have Invented Monads! (And Maybe You Already Have.), a gentle introduction.
• All About Monads
• Monads as Computation
• Monads as Containers
• Monads for the Working Haskell Programmer
• "Monads for Functional Programming" (PDF) by Philip Wadler
• A tour of the Haskell Monad functions by Henk-Jan van Tuyl
• The Haskell Programmer's Guide to the IO Monad — Don't Panic (PDF)
• Monads in Ruby
• Notions of Computation and Monads (PDF) by Eugenio Moggi