Editing Monad (functional programming) (section)

== Overview ==
"For a monad <code>m</code>, a value of type <code>m a</code> represents having access to a value of type <code>a</code> within the context of the monad." —C. A. McCann<ref name=so3322540 >[https://stackoverflow.com/questions/3322540/how-and-why-does-the-haskell-cont-monad-work C. A. McCann's answer (Jul 23 '10 at 23:39) How and why does the Haskell Cont monad work?]</ref>

More exactly, a monad can be used where unrestricted access to a value is inappropriate for reasons specific to the scenario. In the case of the Maybe monad, it is because the value may not exist. In the case of the IO monad, it is because the value may not be known yet, such as when the monad represents user input that will only be provided after a prompt is displayed. In all cases the scenarios in which access makes sense are captured by the bind operation defined for the monad; for the Maybe monad a value is bound only if it exists, and for the IO monad a value is bound only after the previous operations in the sequence have been performed.

A monad can be created by defining a [[type constructor]] ''M'' and two operations:

* <code>return :: a -> M a</code> (often also called ''unit''), which receives a value of type <code>a</code> and wraps it into a ''monadic value'' of type <code>M a</code>, and
* <code>bind :: (M a) -> (a -> M b) -> (M b)</code> (typically represented as <code>>>=</code>), which receives a monadic value of type <code>M a</code> and a function <code>f</code> that accepts values of the base type <code>a</code>. Bind unwraps <code>a</code>, applies <code>f</code> to it, and can process the result of <code>f</code> as a monadic value <code>M b</code>.

(An alternative but [[#muIsJoin|equivalent construct]] using the <code>join</code>  function instead of the <code>bind</code> operator can be found in the later section ''{{section link|#Derivation from functors}}''.)

With these elements, the programmer composes a sequence of function calls (a "pipeline") with several ''bind'' operators chained together in an expression. Each function call transforms its input plain-type value, and the bind operator handles the returned monadic value, which is fed into the next step in the sequence.

Typically, the bind operator <code>>>=</code> may contain code unique to the monad that performs additional computation steps not available in the function received as a parameter. Between each pair of composed function calls, the bind operator can inject into the monadic value <code>m a</code> some additional information that is not accessible within the function <code>f</code>, and pass it along down the pipeline. It can also exert finer control of the flow of execution, for example by calling the function only under some conditions, or executing the function calls in a particular order.

=== An example: Maybe ===
{{Further|Option type}}
{{See also|Monad (category theory)#The maybe monad}}

One example of a monad is the <code>Maybe</code> type. Undefined null results are one particular pain point that many procedural languages don't provide specific tools for dealing with, requiring use of the [[null object pattern]] or checks to test for invalid values at each operation to handle undefined values. This causes bugs and makes it harder to build robust software that gracefully handles errors. The <code>Maybe</code> type forces the programmer to deal with these potentially undefined results by explicitly defining the two states of a result: <code>Just ⌑result⌑</code>, or <code>Nothing</code>. For example the programmer might be constructing a parser, which is to return an intermediate result, or else signal a condition which the parser has detected, and which the programmer must also handle. With just a little extra functional spice on top, this <code>Maybe</code> type transforms into a fully-featured monad.{{efn|name= gHutton2ndMaybe|Specific motivation for Maybe can be found in (Hutton 2016).<ref name=gHutton2016 >Graham Hutton (2016) ''Programming in Haskell'' 2nd Edition</ref>}}{{rp|12.3 pages 148–151}}

In most languages, the Maybe monad is also known as an [[option type]], which is just a type that marks whether or not it contains a value. Typically they are expressed as some kind of [[enumerated type]]. In the [[Rust (programming language)|Rust]] programming language it is called <code>Option<T></code> and variants of this type can either be a value of [[generic type]] <code>T</code>, or the empty variant: <code>None</code>.

<syntaxhighlight lang="rust">
// The <T> represents a generic type "T"
enum Option<T> {
    Some(T),
    None,
}
</syntaxhighlight>

<code>Option<T></code> can also be understood as a "wrapping" type, and this is where its connection to monads comes in. In languages with some form of the Maybe type, there are functions that aid in their use such as composing '''monadic functions''' with each other and testing if a Maybe contains a value.

In the following hard-coded example, a Maybe type is used as a result of functions that may fail, in this case the type returns nothing if there is a [[divide-by-zero]].<syntaxhighlight lang="rust">
fn divide(x: Decimal, y: Decimal) -> Option<Decimal> {
    if y == 0 { return None }
    else { return Some(x / y) }
}
// divide(1.0, 4.0) -> returns Some(0.25)
// divide(3.0, 0.0) -> returns None
</syntaxhighlight>One such way to test whether or not a Maybe contains a value is to use <code>if</code> statements.<syntaxhighlight lang="rust">
let m_x = divide(3.14, 0.0); // see divide function above
// The if statement extracts x from m_x if m_x is the Just variant of Maybe
if let Some(x) = m_x {
    println!("answer: ", x)
} else {
    println!("division failed, divide by zero error...")
}
</syntaxhighlight>Other languages may have [[pattern matching]]<syntaxhighlight lang="rust">
let result = divide(3.0, 2.0);
match result {
    Some(x) => println!("Answer: ", x),
    None => println!("division failed; we'll get 'em next time."),
}
</syntaxhighlight>Monads can compose functions that return Maybe, putting them together. A concrete example might have one function take in several Maybe parameters, and return a single Maybe whose value is Nothing when any of the parameters are Nothing, as in the following:

<syntaxhighlight lang="rust">
fn chainable_division(maybe_x: Option<Decimal>, maybe_y: Option<Decimal>) -> Option<Decimal> {
    match (maybe_x, maybe_y) {
        (Some(x), Some(y)) => { // If both inputs are Some, check for division by zero and divide accordingly
            if y == 0 { return None }
            else { return Some(x / y) }
        },
        _ => return None // Otherwise return None
    }
}
chainable_division(chainable_division(Some(2.0), Some(0.0)), Some(1.0)); // inside chainable_division fails, outside chainable_division returns None
</syntaxhighlight>

Instead of repeating <code>Some</code> expressions, we can use something called a ''bind'' operator. (also known as "map", "flatmap", or "shove"<ref name= Beckerman>{{Cite web|last=Beckerman|first=Brian|date=21 November 2012|title=Don't fear the Monad|website=[[YouTube]]|url=https://www.youtube.com/watch?v=ZhuHCtR3xq8&t=2205s}}</ref>{{rp|2205s}}). This operation takes a monad and a function that returns a monad and runs the function on the inner value of the passed monad, returning the monad from the function.<syntaxhighlight lang="rust">
// Rust example using ".map". maybe_x is passed through 2 functions that return Some<Decimal> and Some<String> respectively.
// As with normal function composition the inputs and outputs of functions feeding into each other should match wrapped types. (i.e. the add_one function should return a Some<Decimal> which then can be unwrapped to a Decimal for the decimal_to_string function)
let maybe_x: Some<Decimal> = Option(1.0)
let maybe_result = maybe_x.map(add_one).map(decimal_to_string)
</syntaxhighlight>In Haskell, there is an operator ''bind'', or (<code>>>=</code>) that allows for this monadic composition in a more elegant form similar to [[function composition]].{{efn|name= gHutton2ndBind|Hutton abstracts a <code>bind</code> which when given a type ''a'' that may fail, and a mapping ''a''→''b'' that may fail, produces a result ''b'' that may fail. (Hutton, 2016)<ref name=gHutton2016/> }}{{rp|150–151}}

<syntaxhighlight lang="haskell">
halve :: Int -> Maybe Int
halve x
  | even x = Just (x `div` 2)
  | odd x  = Nothing
 -- This code halves x twice. it evaluates to Nothing if x is not a multiple of 4
halve x >>= halve 
</syntaxhighlight>

With <code>>>=</code> available, <code>chainable_division</code> can be expressed much more succinctly with the help of [[anonymous function]]s (i.e. lambdas). Notice in the expression below how the two nested lambdas each operate on the wrapped value in the passed <code>Maybe</code> monad using the bind operator.{{efn|name= gHutton2ndJust|(Hutton 2016) notes that Just might denote Success, and Nothing might denote Failure.<ref name=gHutton2016 />}}{{rp|93}}

<syntaxhighlight lang="haskell">
 chainable_division(mx,my) =   mx >>=  ( λx ->   my >>= (λy -> Just (x / y))   )
</syntaxhighlight>

What has been shown so far is basically a monad, but to be more concise, the following is a strict list of qualities necessary for a monad as defined by the following section.

;''Monadic Type''
:A type (<code>Maybe</code>){{efn|name= gHutton2ndMaybe}}{{rp|148–151}}
;''Unit operation''
:A type converter (<code>Just(x)</code>){{efn|name= gHutton2ndJust}}{{rp|93}}
;''Bind operation''
:A combinator for monadic functions ( <code>>>=</code> or <code>.flatMap()</code>){{efn|name= gHutton2ndBind}}{{rp|150–151}}

These are the 3 things necessary to form a monad. Other monads may embody different logical processes, and some may have additional properties, but all of them will have these three similar components.<ref name="RealWorldHaskell" /><ref name="Spivey1990">{{cite journal|last1=Spivey|first1=Mike|year=1990|title=A functional theory of exceptions|url=https://www.cs.tufts.edu/comp/150FP/archive/mike-spivey/functional-exns.pdf|journal=Science of Computer Programming|volume=14|issue=1|pages=25–42|doi=10.1016/0167-6423(90)90056-J|doi-access=free}}</ref>

=== Definition ===
The more common definition for a monad in functional programming, used in the above example, is actually based on a [[Kleisli triple]] ⟨T, η, μ⟩ rather than category theory's standard definition. The two constructs turn out to be mathematically equivalent, however, so either definition will yield a valid monad. Given any well-defined basic types {{mvar|T}} and {{mvar|U}}, a monad consists of three parts:
* A [[type constructor]] {{mvar|M}} that builds up a monadic type {{mvar|M T}}{{efn|Semantically, {{mvar|M}} is not trivial and represents an [[endofunctor]] over the [[category (mathematics)|category]] of all well-typed values: <math>M: \mathit{Val} \to \mathit{Val}</math>}}
* A [[type conversion|type converter]], often called '''unit''' or '''return''', that embeds an object {{mvar|x}} in the monad:{{block indent|1=<code>unit : T → M T</code>{{efn|While a (parametrically polymorphic) function in programming terms, {{mvar|unit}} (often called {{mvar|&eta;}} in category theory) is mathematically a [[natural transformation]], which maps between ''functors'': <math>\eta_{A} : \mathrm{id}(\mathit{Val}_{A}) \to M(\mathit{Val}_{A})</math>}}}}
* {{anchor|Bind}} A [[combinator]], typically called '''bind''' (as in [[bound variable|binding a variable]]) and represented with an [[Infix notation#Usage|infix operator]] <code>>>=</code> or a method called '''flatMap''', that unwraps a monadic variable, then inserts it into a monadic function/expression, resulting in a new monadic value:{{block indent|1=<code>(>>=) : (M T, T → M U) → M U</code>{{efn| name= bindIsaLift|1= {{mvar|bind}}, on the other hand, is not a natural transformation in category theory, but rather an extension <math>-^{*}</math> that [[lift (mathematics)|lift]]s a mapping (from values to computations) into a morphism between computations: <math>\forall f : \mathit{Val}_{A} \to M(\mathit{Val}_{B}),   f^{*}: M(\mathit{Val}_{A}) \to M(\mathit{Val}_{B})</math>}} so if <code>mx : M T</code> and <code>f : T → M U</code>, then <code> (mx >>= f) : M U</code>}}

{{anchor|Monad laws}}
To fully qualify as a monad though, these three parts must also respect a few laws:
* {{mvar|unit}} is a [[identity element|left-identity]] for {{mvar|bind}}:{{block indent|1=<code>unit(x) >>= f</code> '''↔''' <code>f(x)</code>}}
* {{mvar|unit}} is also a right-identity for {{mvar|bind}}:{{block indent|1=<code>ma >>= unit</code> '''↔''' <code>ma</code>}}
* {{mvar|bind}} is essentially [[associative]]:{{efn|Strictly speaking, {{mvar|bind}} may not be formally associative in all contexts because it corresponds to application within [[lambda calculus]], not mathematics. In rigorous lambda-calculus, evaluating a {{mvar|bind}} may require first wrapping the right term (when binding two monadic values) or the bind itself (between two monadic functions) in an [[anonymous function]] to still accept input from the left.<ref name="MonadLaws">{{cite web | title=Monad laws | url=http://www.haskell.org/haskellwiki/Monad_laws | work=HaskellWiki | publisher=haskell.org | access-date=14 October 2018}}</ref>}}{{block indent|1=<code>ma >>= λx → (f(x) >>= g)</code> '''↔''' <code>(ma >>= f) >>= g</code><ref name="RealWorldHaskell" />}}

Algebraically, this means any monad both gives rise to a category (called the [[Kleisli category]]) ''and'' a [[monoid]] in the category of functors (from values to computations), with monadic composition as a binary operator in the monoid<ref name=Beckerman />{{rp|2450s}} and {{mvar|unit}} as identity in the monoid.

=== Usage ===
The value of the monad pattern goes beyond merely condensing code and providing a link to mathematical reasoning.
Whatever language or default [[programming paradigm]] a developer uses, following the monad pattern brings many of the benefits of [[purely functional programming]].
By [[reification (computer science)|reifying]] a specific kind of computation, a monad not only [[encapsulation (computer programming)|encapsulates]] the tedious details of that computational pattern, but it does so in a [[declarative programming|declarative]] way, improving the code's clarity.
As monadic values explicitly represent not only computed values, but computed ''effects'', a monadic expression can be replaced with its value in [[referential transparency|referentially transparent positions]], much like pure expressions can be, allowing for many techniques and optimizations based on [[rewriting]].<ref name="Wadler1992" />

Typically, programmers will use {{mvar|bind}} to chain monadic functions into a sequence, which has led some to describe monads as "programmable semicolons", a reference to how many [[imperative programming|imperative]] languages use semicolons to separate [[Statement (computer programming)|statements]].<ref name="RealWorldHaskell" /><ref name="GentleIntroHaskell" />
However, monads do not actually order computations; even in languages that use them as central features, simpler function composition can arrange steps within a program.
A monad's general utility rather lies in simplifying a program's structure and improving [[separation of concerns]] through abstraction.<ref name="Wadler1992" /><ref name="MonadsAreNot">{{cite web | title = What a Monad is not | url = https://wiki.haskell.org/What_a_Monad_is_not | date = 7 October 2018}}</ref>

The monad structure can also be seen as a uniquely mathematical and [[compile time]] variation on the [[decorator pattern]].
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.
Because they let application programmers implement [[domain logic]] while offloading boilerplate code onto pre-developed modules, monads can even be considered a tool for [[aspect-oriented programming]].<ref name="deMeuter1997">{{cite conference | last = De Meuter | first = Wolfgang | title = Monads as a theoretical foundation for AOP | conference = International Workshop on Aspect Oriented Programming at ECOOP | date = 1997 | location = Jyväskylä, Finland | url = http://soft.vub.ac.be/Publications/1997/vub-prog-tr-97-10.pdf | citeseerx = 10.1.1.25.8262}}</ref>

One other noteworthy use for monads is isolating side-effects, like [[input/output]] or mutable [[state (computer science)|state]], in otherwise purely functional code.
Even purely functional languages ''can'' still implement these "impure" computations without monads, via an intricate mix of function composition and [[continuation-passing style]] (CPS) in particular.<ref name="Wadler1990" />
With monads though, much of this scaffolding can be abstracted away, essentially by taking each recurring pattern in CPS code and bundling it into a distinct monad.<ref name="Wadler1992" />

If a language does not support monads by default, it is still possible to implement the pattern, often without much difficulty.
When translated from category-theory to programming terms, the monad structure is a [[concept (generic programming)|generic concept]] and can be defined directly in any language that supports an equivalent feature for [[parametric polymorphism#Bounded parametric polymorphism|bounded polymorphism]].
A concept's ability to remain agnostic about operational details while working on underlying types is powerful, but the unique features and stringent behavior of monads set them apart from other concepts.<ref name="MonadSansMetaphors">{{cite web | url = https://wiki.haskell.org/Monad_(sans_metaphors) | title = Monad (sans metaphors) | website = HaskellWiki | date = 1 November 2009 | access-date = 24 October 2018}}</ref>