Monad (functional programming): Difference between revisions

Revision as of 09:27, 30 August 2022

Latest revision as of 12:35, 20 August 2025

(71 intermediate revisions by 44 users not shown)

Line 2:

{{for|the concept in category theory|Monad (category theory)}}

In [[functional programming]], a '''monadmonads''' isare a [[softwareway designto pattern]]structure withcomputations as a structuresequence thatof combinessteps, programwhere fragmentseach ([[Functionstep (computernot programming)|functions]])only andproduces wrapsa theirvalue [[returnbut value]]salso insome extra information about the computation, such as a [[Typepotential system|type]]failure, withnon-determinism, additionalor computationside effect. InMore additionformally, toa definingmonad is a wrapping[[type '''monadicconstructor]] type''',M monadsequipped definewith two [[Operatoroperations, {{Code|return : <A>(computera programming: A) -> M(A)|operators]]:typescript}} onewhich to wraplifts a value ininto the monadmonadic typecontext, and another{{Code|bind to: compose<A,B>(m_a together: functionsM(A), thatf output: valuesA of-> theM(B)) monad type-> M(theseB)|typescript}} arewhich knownchains as '''monadic functions''')computations. General-purposeIn languagessimpler useterms, monads tocan reducebe thought of as [[boilerplateInterface code(computing)|interfaces]] neededimplemented foron commontype operationsconstructors, (suchthat asallow dealing with undefined values or falliblefor functions, or encapsulating bookkeeping code). Functional languages use monads to turnabstract complicatedover sequencesvarious oftype functionsconstructor into succinct pipelinesvariants that abstractimplement awaymonad [[control(e.g. flow]]{{Code|Option}}, and{{Code|List}}, [[side-effect (computer scienceetc.)|side-effect]]s.<ref name="RealWorldHaskell">{{cite book|last1=O'Sullivan|first1=Bryan|url=http://book.realworldhaskell.org/|title=Real World Haskell|last2=Goerzen|first2=John|last3=Stewart|first3=Don|publisher=O'Reilly Media|year=2009|isbn=978-0596514983|___location=Sebastopol, California|at=chapter 14|chapter=Monads|chapter-url=http://book.realworldhaskell.org/read/monads.html}}</ref><ref name="Wadler1990">{{cite conference|last=Wadler|first=Philip|author-link=Philip Wadler|date=June 1990|title=Comprehending Monads|conference=ACM Conference on LISP and Functional Programming|___location=Nice, France|citeseerx=10.1.1.33.5381}}</ref>

Both the concept of a monad and the term originally come from [[category theory]], where a monad is defined as an [[endofunctor]] with additional structure.{{efn|More formally, a monad is a [[Functor_monoid (functional_programmingcategory theory)|functormonoid]] within additionalthe structurecategory of [[endofunctor]]s.}}{{efn|Due to the fact that functions on multiple [[free variable]]s are common in programming, monads as described in this article are technically what category theorists would call [[strong monad]]s.<ref name="Moggi1991" />}} Research beginning in the late 1980s and early 1990s established that monads could bring seemingly disparate computer-science problems under a unified, functional model. Category theory also provides a few formal requirements, known as the '''[[#Definition|monad laws]]''', which should be satisfied by any monad and can be used to [[formal verification|verify]] monadic code.<ref name="Moggi1991">{{cite journal | author-link = Eugenio Moggi | last = Moggi | first = Eugenio | year = 1991 | title = Notions of computation and monads | journal = Information and Computation | volume = 93 | issue = 1 | pages = 55–92 | url = http://www.disi.unige.it/person/MoggiE/ftp/ic91.pdf | citeseerx = 10.1.1.158.5275 | doi=10.1016/0890-5401(91)90052-4}}</ref><ref name="Wadler1992">{{cite conference | author-link = Philip Wadler | last = Wadler | first = Philip | title = The essence of functional programming | conference = 19th Annual ACM Symposium on Principles of Programming Languages | ___location = Albuquerque, New Mexico | date = January 1992 | citeseerx = 10.1.1.38.9516}}</ref>

Since monads make [[semantics (computer science)|semantics]] explicit for a kind of computation, they can also be used to implement convenient language features. Some languages, such as [[Haskell (programming language)|Haskell]], even offer pre-built definitions in their core [[library (computing)|libraries]] for the general monad structure and common instances.<ref name="RealWorldHaskell" /><ref name="GentleIntroHaskell">{{cite book | author-link1 = Paul Hudak | last1 = Hudak | first1 = Paul | last2 = Peterson | first2 = John | last3 = Fasel | first3 = Joseph | title = A Gentle Introduction to Haskell 98 | year = 1999 | chapter = About Monads | at = chapter 9 | chapter-url = https://www.haskell.org/tutorial/monads.html | url = https://www.haskell.org/tutorial/index.html}}</ref>

Line 13:

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</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>, using the type constructor,

* <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>return :: a -> M a</code>

and* <code>bind :: (M a) -> (a -> M b) -> (M b)</code> (typically represented as <code>>>=</code>), which receives a functionmonadic value of type <code>fM a</code> overand typea function <code>af</code> andthat canaccepts transformvalues monadicof valuesthe base type <code>ma</code>. Bind unwraps <code>a</code>, applyingapplies <code>f</code> to it, and can process the unwrappedresult valueof <code>af</code>, returningas a monadic value <code>M b</code>:.

and <code>bind</code> (typically represented as <code>>>=</code>), which receives a function <code>f</code> over type <code>a</code> and can transform monadic values <code>m a</code> applying <code>f</code> to the unwrapped value <code>a</code>, returning a monadic value <code>M b</code>:

* <code>bind :: (M a) -> (a -> M b) -> (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}}''.)

(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.

Line 29 ⟶ 25:

=== An example: Maybe ===

{{SeeFurther|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-151148–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 thisthe [[Rust example(programming welanguage)|Rust]] willprogramming calllanguage it is called <code>MaybeOption<T></code> and variants of this type can either be a value of [[generic type]] <code>T</code>, or the empty variant: <code>NothingNone</code>.

<syntaxhighlight lang="rust">

// The <T> represents a generic type "T"

enum MaybeOption<T> {

JustSome(T),

NothingNone,

}

</syntaxhighlight>

<code>MaybeOption<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 <code>Maybe</code> type, there are functions that aid in their use such as composing '''monadic functions''' with each other and testing if a <code>Maybe</code> contains a value.

In the following hard-coded example, a <code>Maybe</code> 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 }

fn divide(x: Decimal, y: Decimal) -> Maybe<Decimal> {

ifelse y{ ==return 0Some(x {/ return Nothingy) }

else { return Just(x / y) }

}

// divide(1.0, 4.0) -> returns JustSome(0.25)

// divide(3.0, 0.0) -> returns None</syntaxhighlight>One such way to test whether or not a <code>Maybe</code> contains a value is to use <code>if</code> statements.<syntaxhighlight lang="rust">

// divide(3.0, 0.0) -> returns Nothing

</syntaxhighlight>One such way to test whether or not a <code>Maybe</code> 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 JustSome(x) = m_x {

printprintln!("answer: ", x)

} else {

printprintln!("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 {

JustSome(x) => printprintln!("answerAnswer: ", x),

NothingNone => printprintln!("division failed,; we'll get 'em next time."),

}

</syntaxhighlight>Monads can compose functions that return <code>Maybe</code>, putting them together. OneA concrete example to do this might be to have one function take in <code>several Maybe</code>s parameters, and return a <code>single Maybe</code> suchwhose value is Nothing when any of the parameters are Nothing, as in the following:

<syntaxhighlight lang="rust">

fn chainable_division(maybe_x: MaybeOption<Decimal>, maybe_y: MaybeOption<Decimal>) -> MaybeOption<Decimal> {

match (maybe_x, maybe_y) {

(JustSome(x), JustSome(y)) => { // If both inputs are JustSome, returncheck for division by zero and divide accordingly

returnif Just(xy /== y);0 { return None }

else { return JustSome(x / y) }

},

_ => return NothingNone // Otherwise return NothingNone

}

}

chainable_division(chainable_division(JustSome(2.0), JustSome(0.0)), JustSome(1.0)); // inside chainable_division fails, outside chainable_division returns NothingNone

</syntaxhighlight>

Having to rewrite functions to take Maybes in this concrete example requires a lotInstead of boilerplate (look at all thoserepeating <code>JustSome</code> expressions!). Instead, we can use something called a ''bind'' operator. (also known as "map", "flatmap", or "shove"<ref name= BeckermanBeckman>{{Cite web|last=BeckermanBeckman|first=Brian|date=21 November 2012|title=Don't fear the Monad|website=[[YouTube]]|url=https://www.youtube.com/watch?v=ZhuHCtR3xq8&t=2205s|url-status=live}}</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 Maybe<Decimal> and Maybe<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 Maybe<Decimal> which then can be unwrappedpassed to a Decimal for the decimal_to_string function)

let maybe_x: MaybeOption<Decimal> = JustSome(1.0)

let maybe_result = maybe_x.map(|x| add_one(x)).map(|x| decimal_to_string(x))

</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-151150–151}}

<syntaxhighlight lang="haskell">

Line 96 ⟶ 92:

</syntaxhighlight>

With <code>>>=</code> available, <code>chainable_division</code> can be expressed much more succinctly with the help of [[Anonymousanonymous function|anonymous functions]]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">

Line 105 ⟶ 101:

;''Monadic Type''

:A type (<code>Maybe</code>){{efn|name= gHutton2ndMaybe}}{{rp|148-151148–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>.mapflatMap()</code>){{efn|name= gHutton2ndBind}}{{rp|150-151150–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>}}}}

Line 125 ⟶ 121:

* {{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=BeckermanBeckman />{{rp|2450s}} and {{mvar|unit}} as identity in the monadmonoid.

=== Usage ===

Line 134 ⟶ 130:

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, it should be stressed that 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>

Line 157 ⟶ 153:

* [[xmonad]] is a [[tiling window manager]] centered on the [[zipper (data structure)|zipper data structure]], which itself can be treated monadically as a specific case of [[delimited continuation]]s.<ref name="xmonad">{{cite web | url = https://donsbot.wordpress.com/2007/05/17/roll-your-own-window-manager-tracking-focus-with-a-zipper/ | title = Roll Your Own Window Manager: Tracking Focus with a Zipper | last = Stewart | first = Don | date = 17 May 2007 | website = Control.Monad.Writer | archive-url = https://web.archive.org/web/20180220194721/https://donsbot.wordpress.com/2007/05/17/roll-your-own-window-manager-tracking-focus-with-a-zipper/ | archive-date = 20 February 2018 | url-status = live | access-date = 19 November 2018}}</ref>

* [[LINQ]] by [[Microsoft]] provides a [[query language]] for the [[.NET Framework]] that is heavily influenced by functional programming concepts, including core operators for composing queries monadically.<ref name="Benton2015">{{cite journal | last = Benton | first = Nick | date = 2015 | title = Categorical Monads and Computer Programming | url = https://www.lms.ac.uk/sites/lms.ac.uk/files/2.%20Benton%20-%20Categorical%20Monads%20and%20Computer%20Programming.pdf | journal = London Mathematical Society Impact150 Stories | volume = 1 | access-date = 19 November 2018}}</ref>

* [[ZipperFS]] is a simple, experimental [[file system]] that also uses the zipper structure primarily to implement its features.<ref name="10.1007/978-3-540-74255-5_22">{{cite journalbook | last = Kiselyov | first = Olag | date = 2007 | journaltitle = Modeling and Using Context | publisherchapter = SpringerDelimited BerlinContinuations Heidelbergin Operating Systems | titledate = Delimited2007 Continuations| inpublisher Operating= SystemsSpringer Berlin Heidelberg | series = Lecture Notes in Computer Science | volume = 4635 | doi = 10.1007/978-3-540-74255-5_22 | isbn = 978-3-540-74255-5 | at = pages 291--302 }}</ref>

* The [[Reactive extensions]] framework essentially provides a (co)monadic interface to [[stream (computing)|data stream]]s that realizes the [[observer pattern]].<ref name="Meijer2012">{{cite journal | author-link = Erik Meijer (computer scientist) | last = Meijer | first = Erik | date = 27 March 2012 | title = Your Mouse is a Database | url = https://queue.acm.org/detail.cfm?id=2169076 | journal = ACM Queue | volume = 10 | issue = 3 | pages = 20–33 | doi = 10.1145/2168796.2169076 | access-date = 19 November 2018| doi-access = free }}</ref>

==History==

The term "monad" in programming actually goes all the way backdates to the [[APL (programming language)|APL]] and [[J (programming language)|J]] programming languages, which do tend toward being purely functional. However, in those languages, "monad" is only shorthand for a function taking one parameter (a function with two parameters being a "dyad", and so on).<ref name="APL">{{cite journal | author-link = Kenneth E. Iverson | last = Iverson | first = Kenneth | date = September 1987 | title = A dictionary of APL | url = http://www.jsoftware.com/papers/APLDictionary.htm | journal = APL Quote Quad | volume = 18 | issue = 1 | pages = 5–40 | doi = 10.1145/36983.36984 | s2cid = 18301178 | issn = 1088-6826 | access-date = 19 November 2018| url-access = subscription }}</ref>

The mathematician [[Roger Godement]] was the first to formulate the concept of a monad (dubbing it a "standard construction") in the late 1950s, though the term "monad" that came to dominate was popularized by category-theorist [[Saunders Mac Lane]].{{Citation needed|reason=Don't have a copy of Mac Lane's book right now, but that could probably work as a source here|date=October 2018}} The form defined above using {{mvar|bind}}, however, was originally described in 1965 by mathematician [[Heinrich Kleisli]] in order to prove that any monad could be characterized as an [[adjunction (category theory)|adjunction]] between two (covariant) functors.<ref name="Kleisli1965">{{cite journal | author-link = Heinrich Kleisli | last = Kleisli | first = Heinrich | date = 1965 | title = Every standard construction is induced by a pair of adjoint functors | url = https://www.ams.org/journals/proc/1965-016-03/S0002-9939-1965-0177024-4/S0002-9939-1965-0177024-4.pdf | journal = Proceedings of the American Mathematical Society | volume = 16 | issue = 3 | pages = 544–546 | doi = 10.1090/S0002-9939-1965-0177024-4 | access-date = 19 November 2018| doi-access = free }}</ref>

Starting in the 1980s, a vague notion of the monad pattern began to surface in the computer science community.

According to programming language researcher [[Philip Wadler]], computer scientist [[John C. Reynolds]] anticipated several facets of it in the 1970s and early 1980s, when he discussed the value of [[continuation-passing style]], of category theory as a rich source for formal semantics, and of the type distinction between values and computations.<ref name="Wadler1992" />

The research language [[Opal programming language|Opal]], which was actively designed up until 1990, also effectively based I/O on a monadic type, but the connection was not realized at the time.<ref name="Opal">{{cite techreporttech report | editor = Peter Pepper | collaboration = The Opal Group | institution = Fachbereich Informatik, Technische Universität Berlin | title = The Programming Language Opal | date = November 1997 | edition = 5th corrected | citeseerx = 10.1.1.40.2748}}</ref>

The computer scientist [[Eugenio Moggi]] was the first to explicitly link the monad of category theory to functional programming, in a conference paper in 1989,<ref name="Moggi89">{{cite conference | author-link = Eugenio Moggi | last = Moggi | first = Eugenio | title = Computational lambda-calculus and monads | conference = Fourth Annual Symposium on Logic in computer science | ___location = Pacific Grove, California | date = June 1989 | url = https://www.disi.unige.it/person/MoggiE/ftp/lics89.pdf | citeseerx = 10.1.1.26.2787}}</ref> followed by a more refined journal submission in 1991. In earlier work, several computer scientists had advanced using category theory to provide semantics for the [[lambda calculus]]. Moggi's key insight was that a real-world program is not just a function from values to other values, but rather a transformation that forms ''computations'' on those values. When formalized in category-theoretic terms, this leads to the conclusion that monads are the structure to represent these computations.<ref name="Moggi1991" />

Several others popularized and built on this idea, including Philip Wadler and [[Simon Peyton Jones]], both of whom were involved in the specification of Haskell. In particular, Haskell used a problematic "lazy stream" model up through v1.2 to reconcile I/O with [[lazy evaluation]], until switching over to a more flexible monadic interface.<ref name="PeytonWadler1993">{{cite conference | author-link1 = Simon Peyton Jones | author-link2 = Philip Wadler | last1 = Peyton Jones | first1 = Simon L. | last2 = Wadler | first2 = Philip | title = Imperative functional programming | date = January 1993 | conference = 20th Annual ACM Symposium on Principles of Programming Languages | ___location = Charleston, South Carolina | url = https://www.microsoft.com/en-us/research/wp-content/uploads/1993/01/imperative.pdf | citeseerx = 10.1.1.53.2504}}</ref> The Haskell community would go on to apply monads to many problems in functional programming, and in the 2010s, researchers working with Haskell eventually recognized that monads are [[applicative functor]]s;<ref name= yorgey> Brent Yorgey [https://wiki.haskell.org/Typeclassopedia#Applicative Typeclassopedia]</ref>{{efn|By GHC version 7.10.1, and going forward, Haskell began enforcing Haskell's 2014 Applicative Monad proposal (AMP) which requires the insertion of 7 lines of code into any existing modules which use monads.<ref name= applMonadProposal>Stack overflow [https://stackoverflow.com/questions/31652475/defining-a-new-monad-in-haskell-raises-no-instance-for-applicative (8 Sep 2017) Defining a new monad in haskell raises no instance for Applicative]</ref>}} and that both monads and [[arrow (computer science)|arrow]]s are [[monoid]]s.<ref> Brent Yorgey [https://wiki.haskell.org/Typeclassopedia#Monoid Monoids]</ref>

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

Line 212 ⟶ 208:

Though rarer in computer science, one can use category theory directly, which defines a monad as a [[functor]] with two additional [[natural transformation]]s.{{efn|name= kleisli|1= These natural transformations are usually denoted as morphisms η, μ. That is: η, μ denote ''unit'', and ''join'' respectively. }}

So to begin, a structure requires a [[higher-order function]] (or "functional") named '''[[map (higher-order function)|map]]''' to qualify as a functor:

{{block indent|<code>map φ : (a → b) → (ma → mb)</code>}}

This is not always a major issue, however, especially when a monad is derived from a pre-existing functor, whereupon the monad inherits {{mvar|map}} automatically. (For historical reasons, this <code>map</code> is instead called <code>fmap</code> in Haskell.)

A monad's first transformation is actually the same {{mvar|unit}} from the Kleisli triple, but following the hierarchy of structures closely, it turns out {{mvar|unit}} characterizes an [[applicative functor]], an intermediate structure between a monad and a basic functor. In the applicative context, {{mvar|unit}} is sometimes referred to as '''pure''' but is still the same function. What does differ in this construction is the law {{mvar|unit}} must satisfy; as {{mvar|bind}} is not defined, the constraint is given in terms of {{mvar|map}} instead:

{{block indent|<code>(unit ∘ φ) x ↔ ((map φ) ∘ unit) x ↔ x</code><ref name="Applicative">{{cite web | title = Applicative functor | url = https://wiki.haskell.org/Applicative_functor | date = 7 May 2018 | website = HaskellWiki | publisher = Haskell.org | archive-url = https://web.archive.org/web/20181030090822/https://wiki.haskell.org/Applicative_functor | archive-date = 30 October 2018 | url-status = live | access-date = 20 November 2018}}</ref>}}

{{anchor|muIsJoin}}

Line 222 ⟶ 218:

{{block indent|<code>join(mma) : M (M T) → M T</code>}}

As the characteristic function, {{mvar|join}} must also satisfy three variations on the monad laws:{{citation needed|reason=Of all the standard sources, only the Haskell wikibook appears to give the join-based laws; they can, however, be translated from the coherence conditions of category theory|date=October 2018}}

{{block indent|1=<code>(join ∘ (map join)) mmma ↔ (join ∘ join) mmma ↔ ma</code>}}

Line 234 ⟶ 230:

=== Another example: List <span id="List monad"></span> ===

{{See also|Monad (category theory)#The list and set monads}}

The '''List monad''' naturally demonstrates how deriving a monad from a simpler functor can come in handy.

In many languages, a list structure comes pre-defined along with some basic features, so a <code>List</code> type constructor and {{mvar|[[append]]}} operator (represented with <code>++</code> for infix notation) are assumed as already given here.

Line 258 ⟶ 257:

One application for this monadic list is representing [[nondeterministic algorithm|nondeterministic computation]].

<code>List</code> can hold results for all execution paths in an algorithm, then condense itself at each step to "forget" which paths led to which results (a sometimes important distinction from deterministic, exhaustive algorithms).{{cncitation needed|date=March 2021}}

Another benefit is that checks can be embedded in the monad; specific paths can be pruned transparently at their first point of failure, with no need to rewrite functions in the pipeline.<ref name="MonadContainers" />

Line 270 ⟶ 269:

=== Syntactic sugar {{visible anchor|do-notation}} ===

Although using {{mvar|bind}} openly often makes sense, many programmers prefer a syntax that mimics imperative statements

(called ''do-notation'' in Haskell, ''perform-notation'' in [[OCaml]], ''computation expressions'' in [[F Sharp (programming language)|F#]],<ref name="F#Expressions">{{cite web | url = https://blogs.msdn.microsoft.com/dsyme/2007/09/21/some-details-on-f-computation-expressions/ | title = Some Details on F# Computation Expressions | date = 21 September 2007 | access-date = 9 October 2018}}</ref> and ''for comprehension'' in [[Scala (programming language)|Scala]]). This is only [[syntactic sugar]] that disguises a monadic pipeline as a [[code block]]; the compiler will then quietly translate these expressions into underlying functional code.

Translating the <code>add</code> function from the <code>Maybe</code> into Haskell can show this feature in action. A non-monadic version of <code>add</code> in Haskell looks like this:

Line 330 ⟶ 329:

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

</syntaxhighlight>

While convenient, a developer should always remember that this block style is purely syntactic and can be replaced with outwardly monadic (or even non-monadic CPS) expressions.

Using {{mvar|bind}} to express the monadic pipeline can still be clearer in many cases, and some functional programming advocates even argue that since block-style allows novices to carry over habits from imperative programming, it should be avoided by default and only used when obviously superior.<ref name="DoHarmful">{{cite web | title = Do notation considered harmful | url = https://wiki.haskell.org/Do_notation_considered_harmful | publisher = HaskellWiki | access-date = 12 October 2018}}</ref><ref name="RealWorldHaskell" />

=== General interface ===

Line 351 ⟶ 347:

Another monadic operator that is also useful for analysis is monadic composition (represented as infix <code>>=></code> here), which allows chaining monadic functions in a more mathematical style:

(f >=> g) (x) = (f(x) → mb) >>= g(y = b)

With this operator, the monad laws can be written in terms of functions alone, highlighting the correspondence to associativity and existence of an identity:

Line 377 ⟶ 373:

=== Collections ===

Any collection with a proper {{mvar|append}} is already a free monoid, but it turns out that <code>List</code> is not the only [[Collection (abstract data type)|collection]] that also has a well-defined {{mvar|join}} and qualifies as a monad.

One can even mutate <code>List</code> into these other monadic collections by simply imposing special properties on {{mvar|append}}:{{efn|Category theory views these collection monads as adjunctions between the [[free functor]] and different functors from the [[category of sets]] to the [[category of monoids]].}}{{efn|name= monoid|1= Here the task for the programmer is to construct an appropriate monoid, or perhaps to choose a monoid from a library.}}

{| class="wikitable"

|-

! rowspan=2 | Collection !! colspan=3 | Monoid properties !! colspan=2 | Combinatoric properties

! Collection

! Monoid properties

|-

! Commutative? !! Idempotent? !! Details !! Ordered? !! Unique items?

| List

| Free

|-

| List || {{No}} || {{No}} || [[Free monoid]] || {{Yes}} || {{No}}

| Finite [[multiset]]

| [[commutative monoid|Commutative]]

|-

| Finite [[multiset]] || {{Yes}} || {{No}} || || {{No}} || {{No}}

| Finite set

| Commutative and [[idempotent]]

|-

| Finite [[set (mathematics)|set]] || {{Yes}} || {{Yes}} || || {{No}} || {{Yes}}

| Finite [[permutation]]s

| Non-commutative and idempotent

|}

Line 400 ⟶ 391:

As already mentioned, pure code should not have unmanaged side effects, but that does not preclude a program from ''explicitly'' describing and managing effects.

This idea is central to Haskell's '''IO monad''', where an object of type <code>IO a</code> can be seen as describing an action to be performed in the world, optionally providing information about the world of type <code>a</code>. An action that provides no information about the world has the type <code>IO ()</code>, "providing" the dummy value <code>()</code>.

When a programmer binds an <code>IO</code> value to a function, the function computes the next action to be performed based on the information about the world provided by the previous action (input from users, files, etc.).<ref name="PeytonWadler1993">{{cite conference | author-link1 = Simon Peyton Jones | author-link2 = Philip Wadler | last1 = Peyton Jones | first1 = Simon L. | last2 = Wadler | first2 = Philip | title = Imperative functional programming | date = January 1993 | conference = 20th Annual ACM Symposium on Principles of Programming Languages | ___location = Charleston, South Carolina | url = https://www.microsoft.com/en-us/research/wp-content/uploads/1993/01/imperative.pdf | citeseerx = 10.1.1.53.2504}}</ref> Most significantly, because the value of the IO monad can only be bound to a function that computes another IO monad, the bind function imposes a discipline of a sequence of actions where the result of an action can only be provided to a function that will compute the next action to perform. This means that actions which do not need to be performed never are, and actions that do need to be performed have a well defined sequence, solving the problem of (IO) actions not being [[referentially transparent]].

For example, Haskell has several functions for acting on the wider [[file system]], including one that checks whether a file exists and another that deletes a file.

Line 473 ⟶ 464:

===Environment monad===

{{See also|Monad (category theory)#The environment monad}}

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

<math display="block">\begin{array}{ll}

Line 492 ⟶ 486:

===State monads===

{{See also|Monad (category theory)#The state monad}}

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

Line 598 ⟶ 595:

</syntaxhighlight>

Finally, itwe woulddefine bea nicenew function to not have toavoid writewriting <code>(x, "")</code> every time we wish to create an empty logging message, where <code>""</code> is the empty string.

So let us define a new function:

<syntaxhighlight lang="haskell">

return : int -> int * string

Line 606 ⟶ 602:

Which wraps <code>x</code> in the tuple described above.

NowThe weresult haveis a nice pipeline for logging messages:

<syntaxhighlight lang="haskell">

((return x) >>= bar) >>= foo

Line 615 ⟶ 611:

<code>int * string</code> denotes a pseudo-coded '''monadic value'''.{{efn|name= paste}} <code>bind</code> and <code>return</code> are analogous to the corresponding functions of the same name.

In fact, <code>int * string</code>, <code>bind</code>, and <code>return</code> form a monad.

== Variations ==

At a mathematical level, some monads have particularly nice properties and are uniquely fitted to certain problems.

=== Additive monads ===