In computer science, functional programming is a programming paradigm that treats computation as the evaluation of mathematical functions and avoids state and mutable data. It emphasizes the application of functions, in contrast to the imperative programming style, which emphasizes changes in state...
, a monad is a programming structure that represents computation
Computation
Computation is defined as any type of calculation. Also defined as use of computer technology in Information processing.Computation is a process following a well-defined model understood and expressed in an algorithm, protocol, network topology, etc...
In computing, an abstract data type is a mathematical model for a certain class of data structures that have similar behavior; or for certain data types of one or more programming languages that have similar semantics...
In the area of mathematical logic and computer science known as type theory, a type constructor is a feature of a typed formal language that builds new types from old. Typical type constructors encountered are product types, function types, power types and list types. Basic types are considered...
In computer science, separation of concerns is the process of separating a computer program into distinct features that overlap in functionality as little as possible. A concern is any piece of interest or focus in a program. Typically, concerns are synonymous with features or behaviors...
A domain model in problem solving and software engineering can be thought of as a conceptual model of a domain of interest which describes the various entities, their attributes, roles and relationships, plus the constraints that govern the integrity of the model elements comprising that problem...
. A defined monad allows the programmer to chain actions together and build different pipelines that process data in various steps, in which each action is decorated
Decorator pattern
In object-oriented programming, the decorator pattern is a design pattern that allows behaviour to be added to an existing object dynamically.-Introduction:...
with additional processing rules provided by the monad; for example a sequence of arithmetic
Arithmetic
Arithmetic or arithmetics is the oldest and most elementary branch of mathematics, used by almost everyone, for tasks ranging from simple day-to-day counting to advanced science and business calculations. It involves the study of quantity, especially as the result of combining numbers...
In mathematics, division by zero is division where the divisor is zero. Such a division can be formally expressed as a / 0 where a is the dividend . Whether this expression can be assigned a well-defined value depends upon the mathematical setting...
in intermediate results. Programs written in functional style can make use of monads to structure procedures that include sequenced operations, or to define some arbitrary control flow
Control flow
In computer science, control flow refers to the order in which the individual statements, instructions, or function calls of an imperative or a declarative program are executed or evaluated....
In computer science, concurrency is a property of systems in which several computations are executing simultaneously, and potentially interacting with each other...
In computer science and programming, a continuation is an abstract representation of the control state of a computer program. A continuation reifies the program control state, i.e...
In computer science, a function or expression is said to have a side effect if, in addition to returning a value, it also modifies some state or has an observable interaction with calling functions or the outside world...
In computing, input/output, or I/O, refers to the communication between an information processing system , and the outside world, possibly a human, or another information processing system. Inputs are the signals or data received by the system, and outputs are the signals or data sent from it...
Exception handling is a programming language construct or computer hardware mechanism designed to handle the occurrence of exceptions, special conditions that change the normal flow of program execution....
).
Formally, a monad is constructed by defining two operations (bind and return) and a type constructor
Type constructor
In the area of mathematical logic and computer science known as type theory, a type constructor is a feature of a typed formal language that builds new types from old. Typical type constructors encountered are product types, function types, power types and list types. Basic types are considered...
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 uses an existing monad by composing monadic functions to define a new data-processing pipeline. The monad acts as a framework
Software framework
In computer programming, a software framework is an abstraction in which software providing generic functionality can be selectively changed by user code, thus providing application specific software...
, 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. 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
Aspect (computer science)
In computer science, an aspect of a program is a feature linked to many other parts of the program, but which is not related to the program's primary function. An aspect crosscuts the program's core concerns, therefore violating its separation of concerns that tries to encapsulate unrelated functions...
Category theory is an area of study in mathematics that examines in an abstract way the properties of particular mathematical concepts, by formalising them as collections of objects and arrows , where these collections satisfy certain basic conditions...
Eugenio Moggi is a professor of computer science at the University of Genoa, Italy.He first described the general use of monads to structure programs.- Biography :Academic qualifications:* Ph.D...
first described the general use of monads to structure programs in 1991. Several people built on his work, including programming language researchers Philip Wadler
Philip Wadler
Philip Wadler is a computer scientist known for his contributions to programming language design and type theory. In particular, he has contributed to the theory behind functional programming and the use of monads in functional programming, the design of the purely functional language Haskell, and...
Simon Peyton Jones is a British computer scientist who researches the implementation and applications of functional programming languages, particularly lazy functional languages...
(both of whom were involved in the specification of Haskell
Haskell (programming language)
Haskell is a standardized, general-purpose purely functional programming language, with non-strict semantics and strong static typing. It is named after logician Haskell Curry. In Haskell, "a function is a first-class citizen" of the programming language. As a functional programming language, the...
). 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
Lazy evaluation
In programming language theory, lazy evaluation or call-by-need is an evaluation strategy which delays the evaluation of an expression until the value of this is actually required and which also avoids repeated evaluations...
.
In addition to I/O, 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.
Haskell and its derivatives have been for a long time the only major users of monads in programming. There also exist formulations in Scheme, Perl, Racket, Clojure
Clojure
Clojure |closure]]") is a recent dialect of the Lisp programming language created by Rich Hickey. It is a general-purpose language supporting interactive development that encourages a functional programming style, and simplifies multithreaded programming....
and Scala, and monads have been an option in the design of a new ML standard. Recently F# has included a feature called computation expressions or workflows, which are an attempt to introduce monadic constructs within a syntax more palatable to programmers with an imperative background.
Effect systems are an alternative way of describing side effects as types.
Background
Some primary uses of monads in functional programming are to express input/output
Input/output
In computing, input/output, or I/O, refers to the communication between an information processing system , and the outside world, possibly a human, or another information processing system. Inputs are the signals or data received by the system, and outputs are the signals or data sent from it...
(I/O) operations and changes in state without using language features that introduce side effects
Side effect (computer science)
In computer science, a function or expression is said to have a side effect if, in addition to returning a value, it also modifies some state or has an observable interaction with calling functions or the outside world...
. 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. One value in such monadic function represents a state of the world. When passing in the state of the world to a function, the monad will create a new world back where the state has been changed according to the function's return value. The state created in this way can be passed to another function, thus defining a series of functions which will apply in order as steps of state changes. This process is similar to how a temporal logic
Temporal logic
In logic, the term temporal logic is used to describe any system of rules and symbolism for representing, and reasoning about, propositions qualified in terms of time. In a temporal logic we can then express statements like "I am always hungry", "I will eventually be hungry", or "I will be hungry...
represents the passage of time using only declarative
Declarative programming
In computer science, declarative programming is a programming paradigm that expresses the logic of a computation without describing its control flow. Many languages applying this style attempt to minimize or eliminate side effects by describing what the program should accomplish, rather than...
propositions.
In the following example, putStrLn and getLine are monadic functions defined in terms of the I/O monad (see below). The monad controls the changes of state in the input and output streams, and threads each world state from one line to the next in the do-block.
do
putStrLn "What is your name?"
name <- getLine
putStrLn ("Nice to meet you, " ++ name ++ "!")
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. In imperative programming
Imperative programming
In computer science, imperative programming is a programming paradigm that describes computation in terms of statements that change a program state...
In programming language theory, semantics is the field concerned with the rigorous mathematical study of the meaning of programming languages and models of computation...
of the programming language; with monads, they are made explicit in the monad definition, thus avoiding errors by action at a distance.
Category theory is an area of study in mathematics that examines in an abstract way the properties of particular mathematical concepts, by formalising them as collections of objects and arrows , where these collections satisfy certain basic conditions...
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
that describes patterns applicable to many mathematical fields. (As a minor terminological mismatch, the term monad in functional programming contexts is usually used with a meaning corresponding to that of the term strong monad in category theory, a specific kind of category-theoretical monad.)
Haskell is a standardized, general-purpose purely functional programming language, with non-strict semantics and strong static typing. It is named after logician Haskell Curry. In Haskell, "a function is a first-class citizen" of the programming language. As a functional programming language, the...
is a functional language that makes heavy use of monads, and includes syntactic sugar
Syntactic sugar
Syntactic sugar is a computer science term that refers to syntax within a programming language that is designed to make things easier to read or to express....
to make monadic composition more convenient. All of the code samples in this page are written in Haskell
Haskell (programming language)
Haskell is a standardized, general-purpose purely functional programming language, with non-strict semantics and strong static typing. It is named after logician Haskell Curry. In Haskell, "a function is a first-class citizen" of the programming language. As a functional programming language, the...
unless noted otherwise.
Definition
A monad is a construction that, given an underlying type system
Type system
A type system associates a type with each computed value. By examining the flow of these values, a type system attempts to ensure or prove that no type errors can occur...
, embeds a corresponding type system (called the monadic type system) into it (that is, each monadic type acts as the underlying type). This monadic type system preserves all significant aspects of the underlying type system, while adding features particular to the monad.
The usual formulation of a monad for programming is known as a Kleisli triple, and has the following components:
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.
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.
A binding operation of polymorphic type (M t)→(t→M u)→(M u), which Haskell represents by the infix
Infix
An infix is an affix inserted inside a word stem . It contrasts with adfix, a rare term for an affix attached to the end of a stem, such as a prefix or suffix.-Indonesian:...
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:
The monad-related structure on the first argument is "pierced" to expose any number of values in the underlying type t.
The given function is applied to all of those values to obtain values of type (M u).
The monad-related structure on those values is also pierced, exposing values of type u.
Finally, the monad-related structure is reassembled over all of the results, giving a single value of type (M u).
Object-oriented programming is a programming paradigm using "objects" – data structures consisting of data fields and methods together with their interactions – to design applications and computer programs. Programming techniques may include features such as data abstraction,...
terms, the type construction would correspond to the declaration of the monadic type, the unit function takes the role of a constructor method
Constructor (computer science)
In object-oriented programming, a constructor in a class is a special type of subroutine called at the creation of an object. It prepares the new object for use, often accepting parameters which the constructor uses to set any member variables required when the object is first created...
, and the binding operation contains the logic necessary to execute its registered callback
Callback (computer science)
In computer programming, a callback is a reference to executable code, or a piece of executable code, that is passed as an argument to other code. This allows a lower-level software layer to call a subroutine defined in a higher-level layer....
s (the monadic functions).
In practical terms, a monad (seen as special result values carried throughout the pipeline) 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. For example, Haskell's Maybe monad can have either a normal return value, or Nothing. Similarly, error monads (such as Either e, for some type e representing error information) can have a normal return value or an error value. Consider how these apply to the example of "Maybe" type, as explained in the Examples section.
Axioms
For a monad to behave correctly, the definitions must obey a few axioms. (The ≡ symbol is not Haskell code, but indicates an equivalence between two Haskell expressions.)
"return" acts approximately as a neutral element of >>=.
(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.
In programming language theory, an anonymous function is a function defined, and possibly called, without being bound to an identifier. Anonymous functions are convenient to pass as an argument to a higher-order function and are ubiquitous in languages with first-class functions such as Haskell...
that maps any value x to the expression that follows.
In mathematical notation, the axioms are:
The axioms can also be expressed in do-block style (see below):
do { f x } ≡ do { v <- return x; f v }
do { m } ≡ do { v <- m; return v }
do { x <- m;
y <- f x;
g y }
≡
do { y <- do { x <- m; f x };
g y }
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 >>= (\x -> 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.
An additive monad is a monad endowed with a monadic zero and an operation (called mplus) satisfying the monoid
Monoid
In abstract algebra, a branch of mathematics, a monoid is an algebraic structure with a single associative binary operation and an identity element. Monoids are studied in semigroup theory as they are naturally semigroups with identity. Monoids occur in several branches of mathematics; for...
laws, with the monadic zero as unit. The operation has type M t → M t → M t (where M is the monad constructor and t is the underlying data type), satisfies the associative law and has the zero as both left and right identity. (Thus, an additive monad is also a monoid.)
An introductory example as a control structure
The following example shows usage of a monad as a control structure in the well-known context of real
Real number
In mathematics, a real number is a value that represents a quantity along a continuum, such as -5 , 4/3 , 8.6 , √2 and π...
right|thumb|200px|20 \div 4=5In mathematics, especially in elementary arithmetic, division is an arithmetic operation.Specifically, if c times b equals a, written:c \times b = a\,...
. It uses the Maybe monad, which is designed to handle exceptional cases in operations, to check for divisions by 0.
This requires the definition of a special division operator // to perform a sequence of divisions, either of which could result in an operating error. The // operator checks whether the divisor is 0, in which case it returns a special value Nothing that is chained through the other operations in the procedure. The // operator is defined in terms of the Maybe constructor and its corresponding bind and return operators.
In computer science and numerical computation, pseudocode is a compact and informal high-level description of the operating principle of a computer program or other algorithm. It uses the structural conventions of a programming language, but is intended for human reading rather than machine reading...
defines a safeDivisions function performing a sequence of divisions and assignments
Assignment (computer science)
In computer programming, an assignment statement sets or re-sets the value stored in the storage location denoted by a variable name. In most imperative computer programming languages, assignment statements are one of the basic statements...
to variables. This function is called with the input value 2, which returns the value 1, and input value 0, which performs an invalid division by zero
Division by zero
In mathematics, division by zero is division where the divisor is zero. Such a division can be formally expressed as a / 0 where a is the dividend . Whether this expression can be assigned a well-defined value depends upon the mathematical setting...
operation and returns the special value Nothing.
safeDivisions x = do
val1 <- 6' // x'
val2 <- val1' // 3'
return val2
safeDivisions 2
-> 1'
safeDivisions 0
-> Nothing
The values 6', 3' and the variables x', val1', val2' are modified versions of the equivalent numbers transformed to match the correct type required by the // operator. Operations on these transformed values are augmented with the error-control aspect
Aspect (computer science)
In computer science, an aspect of a program is a feature linked to many other parts of the program, but which is not related to the program's primary function. An aspect crosscuts the program's core concerns, therefore violating its separation of concerns that tries to encapsulate unrelated functions...
provided by the Maybe monad. In this particular case, the monad is used to define the behavior of a not-a-number
NaN
In computing, NaN is a value of the numeric data type representing an undefined or unrepresentable value, especially in floating-point calculations...
special value, which is often found in programming languages as part of the language definition but in this case is provided as a library function.
Motivation
Checking for the presence of a previous error is performed in the Maybe monad definition, so it doesn't need to be replicated in every new operator that uses it. The operator only needs to test for errors it produces, not previous errors in the pipeline; the monad itself abstracts in a reusable way the error-checking in composite functions.
In computer science, functional programming is a programming paradigm that treats computation as the evaluation of mathematical functions and avoids state and mutable data. It emphasizes the application of functions, in contrast to the imperative programming style, which emphasizes changes in state...
style, thus retaining referential transparency. This implies that all computation steps, even jumps in the control flow
Control flow
In computer science, control flow refers to the order in which the individual statements, instructions, or function calls of an imperative or a declarative program are executed or evaluated....
, are expressed as a part of the program. Contrast this with exceptions
Exception handling
Exception handling is a programming language construct or computer hardware mechanism designed to handle the occurrence of exceptions, special conditions that change the normal flow of program execution....
In computer science and automata theory, a state is a unique configuration of information in a program or machine. It is a concept that occasionally extends into some forms of systems programming such as lexers and parsers....
are defined outside the programming language, encapsulated as opaque language primitive
Language primitive
In computing, language primitives are the simplest elements available in a programming language. A primitive can be defined as the smallest 'unit of processing' available to a programmer of a particular machine, or can be an atomic element of an expression in a language.-Machine level primitives:A...
right|thumb|200px|20 \div 4=5In mathematics, especially in elementary arithmetic, division is an arithmetic operation.Specifically, if c times b equals a, written:c \times b = a\,...
function used in the previous example is undefined
Partial function
In mathematics, a partial function from X to Y is a function ƒ: X' → Y, where X' is a subset of X. It generalizes the concept of a function by not forcing f to map every element of X to an element of Y . If X' = X, then ƒ is called a total function and is equivalent to a function...
for some known values, such as zero. Division might occur repeatedly in a calculation. A programmer might want to express a sequence of divisions without caring for error control, like the following one which returns the resistance of two electrical resistors in parallel:
-- par is a function that takes two real numbers and returns another
-- It is an example taken from electrical engineering (see above) to
-- illustrate why implementing NaN
NaN
In computing, NaN is a value of the numeric data type representing an undefined or unrepresentable value, especially in floating-point calculations...
-semantics on top of the current
-- division system is useful; it is not related to Monads.
par :: Float -> Float -> Float -- resistance(R1), resistance(R2) -> resistance(R1 in parallel with R2)
par R1 R2 = 1 / ((1 / R1) + (1 / R2)) -- formula given from electrical engineering
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:
-- // 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
_ // Just 0 = Nothing
Just x // Just y = Just (x / y)
_ // _ = Nothing
parM :: Float -> Float -> Maybe Float
parM R1 R2 = 1' // ((1' // R1') +' (1' // R2'))
-- where 1', R1', R2' are the "Maybe" versions of 1, R1, R2 and +' "adds" Maybe Floats.
-- See below for details.
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; when one // operator returns Nothing, the definition of the Maybe monad ensures that the rest of the expression will not be executed. 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.
do-notation
Although there are times when it makes sense to use the bind operator >>= directly in a program, it is more typical to use a format called do-notation (perform-notation in OCaml, computation expressions in F#), that mimics the appearance of imperative languages. The compiler translates do-notation to expressions involving >>=. For example, the following code:
It is helpful to see the implementation of the list monad, and to know that concatMap maps a function over a list and concatenates (flattens) the resulting lists:
instance Monad [] where
m >>= f = concatMap f m
return x = [x]
fail s = []
Therefore, the following transformations hold and all the following expressions are equivalent:
a = [3..4] >>= (\x -> [1..2] >>= (\_ -> return (x, 42)))
a = [3..4] >>= (\x -> concatMap (\_ -> return (x, 42)) [1..2] )
a = [3..4] >>= (\x -> [(x,42),(x,42)] )
a = concatMap (\x -> [(x,42),(x,42)] ) [3..4]
a = [(3,42),(3,42),(4,42),(4,42)]
Notice that the list [1..2] is not used. The lack of a left-pointing arrow, translated into a binding to a function that ignores its argument, indicates that only the monadic structure is of interest, not the values inside it, e.g. for a state monad this might be used for changing the state without producing any more result values. 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)))
A similar example in F# using a computation expression:
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)
}
The syntactic sugar of the maybe block would get translated internally to the following expression:
maybe.Delay(fun ->
maybe.Bind(readNum, fun x ->
maybe.Bind(readNum, fun y ->
if (y=0) then None else maybe.Return( x/y ))))
Generic monadic functions
Given values produced by safe division, we might want to carry on doing calculations without having to check manually if they are Nothing (i.e. resulted from an attempted division by zero). We can do this using a "lifting
Lift (mathematics)
In the branch of mathematics called category theory, given a morphism f from an object X to an object Y, and a morphism g from an object Z to Y, a lift of f to Z is a morphism h from X to Z such that gh = f.A basic example in topology is lifting a path in one space to a path in a covering space...
" function, which we can define not only for Maybe but for arbitrary monads. In Haskell this is called liftM2:
liftM2 :: Monad m => (a -> b -> c) -> m a -> m b -> m c
liftM2 op mx my = do
x <- mx
y <- my
return (op x y)
Recall that arrows in a type associate to the right, so liftM2 is a function that takes a binary function as an argument and returns another binary function. The type signature says: If m is a monad, we can "lift" any binary function into it. For example:
(.*.) :: (Monad m, Num a) => m a -> m a -> m a
x .*. y = liftM2 (*) x y
defines an operator (.*.) which multiplies two numbers, unless one of them is Nothing (in which case it again returns Nothing). The advantage here is that we need not dive into the details of the implementation of the monad; if we need to do the same kind of thing with another function, or in another monad, using liftM2 makes it immediately clear what is meant (see Code reuse
Code reuse
Code reuse, also called software reuse, is the use of existing software, or software knowledge, to build new software.-Overview:Ad hoc code reuse has been practiced from the earliest days of programming. Programmers have always reused sections of code, templates, functions, and procedures...
).
Mathematically, the liftM2 operator is defined by:
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 ++ "!")
The do notation of this procedure resembles an imperative program. But the expansion of the do-block shows how the procedure is defined in pure functional terms thanks to the I/O monad, and makes explicit the information flow from one action to the next:
putStrLn "What is your name?" >>=
(\_ ->
getLine >>=
(\name ->
putStrLn ("Nice to meet you, " ++ name ++ "!")))
The pipeline structure of the bind operator ensures that the getLine and putStrLn operations get evaluated only once and in the given order, so that the side-effects of extracting text from the input stream and writing to the output stream are correctly handled in the functional pipeline. This remains true even if the language performs out-of-order
Out-of-order execution
In computer engineering, out-of-order execution is a paradigm used in most high-performance microprocessors to make use of instruction cycles that would otherwise be wasted by a certain type of costly delay...
In programming language theory, lazy evaluation or call-by-need is an evaluation strategy which delays the evaluation of an expression until the value of this is actually required and which also avoids repeated evaluations...
In programming languages and type theory, an option type or maybe type is a polymorphic type that represents encapsulation of an optional value; e.g. it is used as the return type of functions which may or may not return a meaningful value when they're applied...
: it handles exceptional cases in operations as special values in an underlying type.
A Maybe type is defined as the combination of "just the underlying type" (represented by wrapping the type with the Just constructor), with a value representing "nothing", i.e. undefined.
data Maybe t = Just t | Nothing
The Maybe value corresponding to an underlying value, is just that value (represented by wrapping with Just).
return x = Just x
Binding a function to something that is just a value means applying it directly to that value (the function must return a monadic type). Binding a function to nothing produces nothing.
(>>=) :: Maybe a -> (a -> Maybe b) -> Maybe b
(Just x) >>= f = f x
Nothing >>= f = Nothing
For the safe division example, (/) is the underlying function, (//) is the safe monadic version. There are two Maybe inputs. If either input is Nothing, then Nothing is returned. Otherwise the inputs are Just x and Just y, from which the operator extracts the x and y values in the underlying type. If y is zero, (/) cannot be applied, so Nothing is returned, otherwise Just (x / y) is returned:
(//) :: Maybe a -> Maybe a -> Maybe a
_ // Nothing = Nothing
Nothing // _ = Nothing
_ // Just 0 = Nothing
Just x // Just y = Just (x / y)
A more general version that applies to all types m such that m is an instance of the Monad class:
(//) :: (Fractional a, Monad m) => a -> a -> m a
_ // 0 = fail "//: divide by zero"
x // y = return (x / y)
This is the definition of the same Maybe monad in the F# language:
type MaybeBuilder =
member this.Bind(x, f) =
match x with
| Some(x) -> f(x)
| _ -> None
member this.Delay(f) = f
member this.Return(x) = Some x
let maybe = MaybeBuilder
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.
The // operator actually requires parameters of type Maybe a, so the pseudocode example in the introduction paragraph is invalid. Here is the correct version which lifts values of the basic type into monadic ones:
safeDivisions x = do
val1 <- return 6 // return x
val2 <- return 3 // return 1
val3 <- val1 // val2
return val3
From the category theory point of view, the Maybe monad is derived from the adjunction between the free functor and the underlying functor between the category of sets
Category of sets
In the mathematical field of category theory, the category of sets, denoted as Set, is the category whose objects are sets. The arrows or morphisms between sets A and B are all functions from A to B...
In mathematics, a pointed set is a set X with a distinguished element x_0\in X, which is called the basepoint. Maps of pointed sets are those functions that map one basepoint to another, i.e. a map f : X \to Y such that f = y_0. This is usually denotedf : \to .Pointed sets may be regarded as a...
s.
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
In computer programming, a variable is a symbolic name given to some known or unknown quantity or information, for the purpose of allowing the name to be used independently of the information it represents...
substitution; do {x <- 2; return 3*x} results in 6.
From the category theory point of view, the identity monad is derived from the adjunction between identity functors.
In computer science, a collection is a grouping of some variable number of data items that have some shared significance to the problem being solved and need to be operated upon together in some controlled fashion. Generally, the data items will be of the same type or, in languages supporting...
In computer science, a linked list is a data structure consisting of a group of nodes which together represent a sequence. Under the simplest form, each node is composed of a datum and a reference to the next node in the sequence; more complex variants add additional links...
In computer science, a set is an abstract data structure that can store certain values, without any particular order, and no repeated values. It is a computer implementation of the mathematical concept of a finite set...
In mathematics, the notion of multiset is a generalization of the notion of set in which members are allowed to appear more than once...
s, are monads. The definition for lists is given here.
-- "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 = []
List comprehensions are a special application of the list monad. For example, the list comprehension [ 2*x | x <- [1..n], isOkay x] corresponds to the computation in the list monad do {x <- [1..n]; if isOkay x then return else mzero; return (2*x)}.
In set theory and its applications to logic, mathematics, and computer science, set-builder notation is a mathematical notation for describing a set by stating the properties that its members must satisfy...
, but sets can't be made into a monad, since there's a restriction on the type of computation to be comparable for equality, whereas a monad does not put any constraints on the types of computations. Actually, the Set is a restricted monad.
The monads for collections naturally represent nondeterministic computation
Nondeterministic algorithm
In computer science, a nondeterministic algorithm is an algorithm that can exhibit different behaviors on different runs, as opposed to a deterministic algorithm. There are several ways an algorithm may behave differently from run to run. A concurrent algorithm can perform differently on different...
. The list (or other collection) represents all the possible results from different nondeterministic paths of computation at that given time. For example, when one executes x <- [1,2,3,4,5], one is saying that the variable x can non-deterministically take on any of the values of that list. If one were to return x, it would evaluate to a list of the results from each path of computation. Notice that the bind operator above follows this theme by performing f on each of the current possible results, and then it concatenates the result lists together.
Statements like if condition x y then return else mzero are also often seen; if the condition is true, the non-deterministic choice is being performed from one dummy path of computation, which returns a value we are not assigning to anything; however, if the condition is false, then the mzero = [] monad value non-deterministically chooses from 0 values, effectively terminating that path of computation. Other paths of computations might still succeed. This effectively serves as a "guard" to enforce that only paths of computation that satisfy certain conditions can continue. So collection monads are very useful for solving logic puzzles, Sudoku, and similar problems.
In programming language theory, lazy evaluation or call-by-need is an evaluation strategy which delays the evaluation of an expression until the value of this is actually required and which also avoids repeated evaluations...
Haskell is a standardized, general-purpose purely functional programming language, with non-strict semantics and strong static typing. It is named after logician Haskell Curry. In Haskell, "a function is a first-class citizen" of the programming language. As a functional programming language, the...
, a list is evaluated only to the degree that its elements are requested: for example, if one asks for the first element of a list, only the first element will be computed. With respect to usage of the list monad for non-deterministic computation that means that we can non-deterministically generate a lazy list of all results of the computation and ask for the first of them, and only as much work will be performed as is needed to get that first result. The process roughly corresponds to backtracking: a path of computation is chosen, and then if it fails at some point (if it evaluates mzero), then it backtracks
Backtracking
Backtracking is a general algorithm for finding all solutions to some computational problem, that incrementally builds candidates to the solutions, and abandons each partial candidate c as soon as it determines that c cannot possibly be completed to a valid solution.The classic textbook example...
to the last branching point, and follows the next path, and so on. If the second element is then requested, it again does just enough work to get the second solution, and so on. So the list monad is a simple way to implement a backtracking algorithm in a lazy language.
From the category theory point of view, collection monads are derived from adjunctions between a free functor and an underlying functor between the category of sets
Category of sets
In the mathematical field of category theory, the category of sets, denoted as Set, is the category whose objects are sets. The arrows or morphisms between sets A and B are all functions from A to B...
and a category of monoids. Taking different types of monoids, we obtain different types of collections.
In mathematics, the notion of multiset is a generalization of the notion of set in which members are allowed to appear more than once...
commutative monoid
finite set
idempotent commutative monoid
finite permutation
idempotent non-commutative monoid
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 along with a return value.
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 -> (, 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 , where S is the underlying state. The return function is simply:
The bind function is:.
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
Cartesian closed category
In category theory, a category is cartesian closed if, roughly speaking, any morphism defined on a product of two objects can be naturally identified with a morphism defined on one of the factors. These categories are particularly important in mathematical logic and the theory of programming, in...
by definition.
Environment monad
The environment monad (also called the reader monad and the 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:
The following monadic operations are useful:
The ask operation is used to retrieve the current context, while local executes a computation in a modified subcontext. As in the 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.
Writer monad
The writer monad allows a program to compute various kinds of auxiliary output which can be "composed" or "accumulated" step-by-step, in addition to the main result of a computation. It is often used for logging or profiling. Given the underlying type T, a value in the writer monad has type W × T, where W is a type endowed with an operation satisfying the monoid
Monoid
In abstract algebra, a branch of mathematics, a monoid is an algebraic structure with a single associative binary operation and an identity element. Monoids are studied in semigroup theory as they are naturally semigroups with identity. Monoids occur in several branches of mathematics; for...
laws. The monad functions are simply:
where ε and * are the identity element of the monoid W and its associative operation, respectively.
The tell monadic operation is defined by:
where 1 and denote the unit type
Unit type
In the area of mathematical logic, and computer science known as type theory, a unit type is a type that allows only one value . The carrier associated with a unit type can be any singleton set. There is an isomorphism between any two such sets, so it is customary to talk about the unit type and...
and its trivial element. It is used in combination with bind to update the auxiliary value without affecting the main computation.
In computer science and programming, a continuation is an abstract representation of the control state of a computer program. A continuation reifies the program control state, i.e...
monad with return type maps type into functions of type . It is used to model continuation-passing style
Continuation-passing style
In functional programming, continuation-passing style is a style of programming in which control is passed explicitly in the form of a continuation. Gerald Jay Sussman and Guy L. Steele, Jr...
In functional programming, the function call-with-current-continuation, commonly abbreviated call/cc, is a control operator that originated in its current form in the Scheme programming language and now exists in several other programming languages....
function is defined as follows:
Others
Other concepts that researchers have expressed as monads include:
Exception handling is a programming language construct or computer hardware mechanism designed to handle the occurrence of exceptions, special conditions that change the normal flow of program execution....
In computing, a graphical user interface is a type of user interface that allows users to interact with electronic devices with images rather than text commands. GUIs can be used in computers, hand-held devices such as MP3 players, portable media players or gaming devices, household appliances and...
In computer science, an interpreter normally means a computer program that executes, i.e. performs, instructions written in a programming language...
s
Strict evaluation
Interfaces to code written in other languages
fmap and join
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 fmap. This formulation fits more closely with the definition of monads in category theory. The fmap 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.
(fmap f) m ≡ m >>= (\x -> return (f x))
join n ≡ n >>= id
m >>= g ≡ join ((fmap g) m)
Here, m has the type M t, n has the type M (M r), f has the type t → u, and g has the type t → M v, where t, r, u and v are underlying types.
In category theory, a branch of mathematics, a functor is a special type of mapping between categories. Functors can be thought of as homomorphisms between categories, or morphisms when in the category of small categories....
in the category of types and functions, not just for monads. It is expected to satisfy the functor laws:
fmap id = id
fmap (f . g) = (fmap f) . (fmap g)
The return function characterizes pointed functors in the same category, by accounting for the ability to "lift" values into the functor. It should satisfy the following law:
return . f = fmap f . return
In addition, the join function characterizes monads:
join . fmap join = join . join
join . fmap return = join . return = id
join . fmap (fmap f) = fmap f . join
Comonads
Comonads are the categorical dual of monads. They are defined by a type constructor W T and two operations: extract with type W T → T for any T, and extend with type (W T → T') → W T → W T' . The operations extend and extract are expected to satisfy these laws:
Alternatively, comonads may be defined in terms of operations fmap, extract and duplicate. The fmap and extract operations define W as a copointed functor. The duplicate operation characterizes comonads: it has type W T → W (W T) and satisfies the following laws:
The two formulations are related as follows:
Whereas monads could be said to represent side-effects, a comonads W represents a kind of context. The extract functions extracts a value from its context, while the extend function may be used to compose a pipeline of "context-dependent functions" of type W A → B.
Identity comonad
The identity comonad is the simplest comonad: it maps type T to itself. The extract operator is the identity and the extend operator is function application.
Product comonad
The product comonad maps type into tuples of type , where is the context type of the comonad. The comonad operations are:
Function comonad
The function comonad maps type into functions of type , where is a type endowed with a monoid
Monoid
In abstract algebra, a branch of mathematics, a monoid is an algebraic structure with a single associative binary operation and an identity element. Monoids are studied in semigroup theory as they are naturally semigroups with identity. Monoids occur in several branches of mathematics; for...
structure. The comonad operations are:
where ε is the identity element of and * is its associative operation.
Costate comonad
The costate comonad maps a type into type , where S is the base type of the store. The comonad operations are:
In computer science, arrows provide a more general interface to computation than monads. Monads essentially provide a sequential interface to computation: one can build a computation out of a value, or sequence two computations. Arrows provide more possibilities, including expressing parallel...
— whereas monads generalize the results of a computation to effects, arrows further generalize the inputs similarly.
In functional programming, a monad transformer is a type constructor which takes a monad as an argument and returns a monad as a result.Monad transformers can be used to compose features encapsulated by monads - such as state, exception handling, and I/O - in a modular way...
s — which allow monads to be composed in a modular and convenient way.
In software engineering, Inversion of Control is an abstract principle describing an aspect of some software architecture designs in which the flow of control of a system is inverted in comparison to procedural programming....
— the abstract principle of calling specific functions from a reusable software entity.
In computing, aspect-oriented programming is a programming paradigm which aims to increase modularity by allowing the separation of cross-cutting concerns...
, a paradigm to increase modularity by isolating secondary or supporting functionality.
In computing, a unique type guarantees that an object is used in a single-threaded way, with at most a single reference to it. If a value has a unique type, a function applied to it can be optimized to update the value in-place in the object code. In-place updates improve the efficiency of...
s - an alternative way of dealing with side-effects in functional languages
Haskell monad tutorials
Monad Tutorials Timeline Probably the most comprehensive collection of links to monad tutorials, ordered by date. — The most famous "blog post" tutorial. — 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. — 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. — Takes a similar point of view, locating monads in a much wider array of Haskell functor classes, of use only in special circumstances. — An extremely detailed set of tutorials, deriving monads from first principles. An explanation of Monads, building on the concepts of Functors, Applicative Functors and Monoids discussed in the previous chapter.
, where S is the underlying state. The return function is simply:
.
maps type 
into functions of type 
. It is used to model continuation-passing style
into tuples of type 
, where 
is the context type of the comonad. The comonad operations are:
into functions of type 
, where 
is a type endowed with a monoid
and * is its associative operation.
into type 
, where S is the base type of the store. The comonad operations are:
