In
functional programming
In computer science, functional programming is a programming paradigm where programs are constructed by Function application, applying and Function composition (computer science), composing Function (computer science), functions. It is a declar ...
, a monad is a
software design pattern
In software engineering, a software design pattern is a general, reusable solution to a commonly occurring problem within a given context in software design. It is not a finished design that can be transformed directly into source or machine code ...
with a structure that combines program fragments (
functions) and wraps their
return value
In computer programming, a return statement causes execution to leave the current subroutine and resume at the point in the code immediately after the instruction which called the subroutine, known as its return address. The return address is sa ...
s in a
type with additional computation. In addition to defining a wrapping monadic type, monads define two
operators
Operator may refer to:
Mathematics
* A symbol indicating a mathematical operation
* Logical operator or logical connective in mathematical logic
* Operator (mathematics), mapping that acts on elements of a space to produce elements of another sp ...
: one to wrap a value in the monad type, and another to compose together functions that output values of the monad type (these are known as monadic functions). General-purpose languages use monads to reduce
boilerplate code needed for common operations (such as dealing with undefined values or fallible functions, or encapsulating bookkeeping code). Functional languages use monads to turn complicated sequences of functions into succinct pipelines that abstract away
control flow
In computer science, control flow (or flow of control) is the order in which individual statements, instructions or function calls of an imperative program are executed or evaluated. The emphasis on explicit control flow distinguishes an ''imper ...
, and
side-effect
In medicine, a side effect is an effect, whether therapeutic or adverse, that is secondary to the one intended; although the term is predominantly employed to describe adverse effects, it can also apply to beneficial, but unintended, consequence ...
s.
Both the concept of a monad and the term originally come from
category theory
Category theory is a general theory of mathematical structures and their relations that was introduced by Samuel Eilenberg and Saunders Mac Lane in the middle of the 20th century in their foundational work on algebraic topology. Nowadays, cate ...
, where a monad is defined as a
functor
In mathematics, specifically category theory, a functor is a Map (mathematics), mapping between Category (mathematics), categories. Functors were first considered in algebraic topology, where algebraic objects (such as the fundamental group) ar ...
with additional structure. 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
monad laws, which should be satisfied by any monad and can be used to
verify
CONFIG.SYS is the primary configuration file for the DOS and OS/2 operating systems. It is a special ASCII text file that contains user-accessible setup or configuration directives evaluated by the operating system's DOS BIOS (typically residing ...
monadic code.
Since monads make
semantics
Semantics (from grc, σημαντικός ''sēmantikós'', "significant") is the study of reference, meaning, or truth. The term can be used to refer to subfields of several distinct disciplines, including philosophy
Philosophy (f ...
explicit for a kind of computation, they can also be used to implement convenient language features. Some languages, such as
Haskell
Haskell () is a general-purpose, statically-typed, purely functional programming language with type inference and lazy evaluation. Designed for teaching, research and industrial applications, Haskell has pioneered a number of programming lan ...
, even offer pre-built definitions in their core
libraries
A library is a collection of materials, books or media that are accessible for use and not just for display purposes. A library provides physical (hard copies) or digital access (soft copies) materials, and may be a physical location or a vir ...
for the general monad structure and common instances.
Overview
"For a monad
m
, a value of type
m a
represents having access to a value of type
a
within the context of the monad." —C. A. McCann
[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
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 ones. Basic types are considered to be built using nullary type constructors. S ...
''M'' and two operations:
* return :: a -> M a
(often also called ''unit''), which receives a value of type a
and wraps it into a ''monadic value'' of type m a
, and
* bind :: (M a) -> (a -> M b) -> (M b)
(typically represented as >>=
), which receives a function f
over type a
and can transform monadic values m a
applying f
to the unwrapped value a
, returning a monadic value M b
.
(An alternative but § equivalent construct using the join
function instead of the bind
operator can be found in the later section '.)
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 >>=
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 m a
some additional information that is not accessible within the function f
, 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
One example of a monad is the Maybe
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
In object-oriented computer programming, a null object is an object with no referenced value or with defined neutral (''null'') behavior. The null object design pattern, which describes the uses of such objects and their behavior (or lack thereof) ...
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 Maybe
type forces the programmer to deal with these potentially undefined results by explicitly defining the two states of a result: Just ⌑result⌑
, or Nothing
. 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 programmer must also handle. With just a little extra functional spice on top, this Maybe
type transforms into a fully-featured monad.
In most languages, the Maybe monad is also known as an option type
In programming languages (especially functional 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 whic ...
, 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 computer programming, an enumerated type (also called enumeration, enum, or factor in the R programming language, and a categorical variable in statistics) is a data type consisting of a set of named values called ''elements'', ''members'', ''en ...
. In this Rust example we will call it Maybe
and variants of this type can either be a value of generic type
Generic programming is a style of computer programming in which algorithms are written in terms of types ''to-be-specified-later'' that are then ''instantiated'' when needed for specific types provided as parameters. This approach, pioneered by ...
T
, or the empty variant: Nothing
.
// The represents a generic type "T"
enum Maybe
Maybe
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
In mathematics, division by zero is division where the divisor (denominator) is zero. Such a division can be formally expressed as \tfrac, where is the dividend (numerator). In ordinary arithmetic, the expression has no meaning, as there is ...
.
fn divide(x: Decimal, y: Decimal) -> Maybe
// divide(1.0, 4.0) -> returns Just(0.25)
// divide(3.0, 0.0) -> returns Nothing
One such way to test whether or not a Maybe
contains a value is to use if
statements.
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 Just(x) = m_x else
Other languages may have pattern matching
In computer science, pattern matching is the act of checking a given sequence of tokens for the presence of the constituents of some pattern. In contrast to pattern recognition, the match usually has to be exact: "either it will or will not be ...
let result = divide(3.0, 2.0);
match result
Monads can compose functions that return Maybe
together. One concrete example to do this might be to have one function take in Maybe
s and return a Maybe
such as:
fn chainable_division(maybe_x: Maybe, maybe_y: Maybe) -> Maybe
chainable_division(chainable_division(Just(2.0), Just(0.0)), Just(1.0)); // inside chainable_division fails, outside chainable_division returns Nothing
Having to rewrite functions to take Maybes in this concrete example requires a lot of boilerplate (look at all those Just
expressions!). Instead, we can use something called a ''bind'' operator. (also known as "map", "flatmap", or "shove"). 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.
// Rust example using ".map". maybe_x is passed through 2 functions that return Maybe and Maybe 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 which then can be unwrapped to a Decimal for the decimal_to_string function)
let maybe_x: Maybe = Just(1.0)
let maybe_result = maybe_x.map(, x, add_one(x)).map(, x, decimal_to_string(x))
In Haskell, there is an operator ''bind'', or (>>=
) that allows for this monadic composition in a more elegant form similar to function composition
In mathematics, function composition is an operation that takes two functions and , and produces a function such that . In this operation, the function is applied to the result of applying the function to . That is, the functions and ...
.
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
With >>=
available, chainable_division
can be expressed much more succinctly with the help of anonymous functions
In computer programming, an anonymous function (function literal, lambda abstraction, lambda function, lambda expression or block) is a function definition that is not bound to an identifier. Anonymous functions are often arguments being passed t ...
(i.e. lambdas). Notice in the expression below how the two nested lambdas each operate on the wrapped value in the passed Maybe
monad using the bind operator.
chainable_division(mx,my) = mx >>= ( λx -> my >>= (λy -> Just (x / y)) )
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 (Maybe
)
;''Unit operation''
:A type converter (Just(x)
)
;''Bind operation''
:A combinator for monadic functions ( >>=
or .map()
)
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.
Definition
The more common definition for a monad in functional programming, used in the above example, is actually based on a Kleisli triple In category theory, a Kleisli category is a category naturally associated to any monad ''T''. It is equivalent to the category of free ''T''-algebras. The Kleisli category is one of two extremal solutions to the question ''Does every monad arise fr ...
⟨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 , , a monad consists of three parts:
* A 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 ones. Basic types are considered to be built using nullary type constructors. S ...
that builds up a monadic type
* A type converter, often called unit or return, that embeds an object in the monad:
* A combinator
Combinatory logic is a notation to eliminate the need for quantified variables in mathematical logic. It was introduced by Moses Schönfinkel and Haskell Curry, and has more recently been used in computer science as a theoretical model of comput ...
, typically called bind (as in binding a variable) and represented with an infix operator
Infix notation is the notation commonly used in arithmetical and logical formulae and statements. It is characterized by the placement of operators between operands—" infixed operators"—such as the plus sign in .
Usage
Binary relations a ...
>>=
or a method called flatMap, that unwraps a monadic variable, then inserts it into a monadic function/expression, resulting in a new monadic value:
To fully qualify as a monad though, these three parts must also respect a few laws:
* is a left-identity for :
* is also a right-identity for :
* is essentially associative
In mathematics, the associative property is a property of some binary operations, which means that rearranging the parentheses in an expression will not change the result. In propositional logic, associativity is a valid rule of replacement f ...
:
Algebraically, this means any monad both gives rise to a category (called the Kleisli category In category theory, a Kleisli category is a category naturally associated to any monad ''T''. It is equivalent to the category of free ''T''-algebras. The Kleisli category is one of two extremal solutions to the question ''Does every monad arise fr ...
) ''and'' a monoid
In abstract algebra, a branch of mathematics, a monoid is a set equipped with an associative binary operation and an identity element. For example, the nonnegative integers with addition form a monoid, the identity element being 0.
Monoids ...
in the category of functors (from values to computations), with monadic composition as a binary operator in the monoid and as identity in the monad.
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
Programming paradigms are a way to classify programming languages based on their features. Languages can be classified into multiple paradigms.
Some paradigms are concerned mainly with implications for the execution model of the language, suc ...
a developer uses, following the monad pattern brings many of the benefits of purely functional programming
In computer science, purely functional programming usually designates a programming paradigm—a style of building the structure and elements of computer programs—that treats all computation as the evaluation of function (mathematics), mathemati ...
.
By reifying a specific kind of computation, a monad not only encapsulates the tedious details of that computational pattern, but it does so in a 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 referentially transparent positions, much like pure expressions can be, allowing for many techniques and optimizations based on rewriting
In mathematics, computer science, and logic, rewriting covers a wide range of methods of replacing subterms of a well-formed formula, formula with other terms. Such methods may be achieved by rewriting systems (also known as rewrite systems, rewr ...
.
Typically, programmers will use to chain monadic functions into a sequence, which has led some to describe monads as "programmable semicolons", a reference to how many imperative languages use semicolons to separate statements
Statement or statements may refer to: Common uses
*Statement (computer science), the smallest standalone element of an imperative programming language
*Statement (logic), declarative sentence that is either true or false
*Statement, a declarative ...
.
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
In computer science, separation of concerns is a design principle for separating a computer program into distinct sections. Each section addresses a separate '' concern'', a set of information that affects the code of a computer program. A concern ...
through abstraction.
The monad structure can also be seen as a uniquely mathematical and compile time
In computer science, compile time (or compile-time) describes the time window during which a computer program is compiled.
The term is used as an adjective to describe concepts related to the context of program compilation, as opposed to concept ...
variation on the decorator pattern
In object-oriented programming, the decorator pattern is a design pattern that allows behavior to be added to an individual object, dynamically, without affecting the behavior of other objects from the same class. The decorator pattern is often ...
.
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
In computing, aspect-oriented programming (AOP) is a programming paradigm that aims to increase modularity by allowing the separation of cross-cutting concerns. It does so by adding behavior to existing code (an advice) ''without'' modifying t ...
.
One other noteworthy use for monads is isolating side-effects, like input/output
In computing, input/output (I/O, or informally io or IO) is the communication between an information processing system, such as a computer, and the outside world, possibly a human or another information processing system. Inputs are the signals ...
or mutable state
State may refer to:
Arts, entertainment, and media Literature
* ''State Magazine'', a monthly magazine published by the U.S. Department of State
* ''The State'' (newspaper), a daily newspaper in Columbia, South Carolina, United States
* ''Our S ...
, 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 In functional programming, continuation-passing style (CPS) is a style of programming in which control is passed explicitly in the form of a continuation. This is contrasted with direct style, which is the usual style of programming. Gerald Jay Suss ...
(CPS) in particular.
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.
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 generic concept and can be defined directly in any language that supports an equivalent feature for 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.
Applications
Discussions of specific monads will typically focus on solving a narrow implementation problem since a given monad represents a specific computational form.
In some situations though, an application can even meet its high-level goals by using appropriate monads within its core logic.
Here are just a few applications that have monads at the heart of their designs:
* The Parsec
The parsec (symbol: pc) is a unit of length used to measure the large distances to astronomical objects outside the Solar System, approximately equal to or (au), i.e. . The parsec unit is obtained by the use of parallax and trigonometry, and ...
parser library uses monads to combine simpler parsing
Parsing, syntax analysis, or syntactic analysis is the process of analyzing a string of symbols, either in natural language, computer languages or data structures, conforming to the rules of a formal grammar. The term ''parsing'' comes from Lati ...
rules into more complex ones, and is particularly useful for smaller domain-specific language
A domain-specific language (DSL) is a computer language specialized to a particular application domain. This is in contrast to a general-purpose language (GPL), which is broadly applicable across domains. There are a wide variety of DSLs, ranging f ...
s.
* xmonad
xmonad is a dynamic window manager (tiling) for the X Window System, noted for being written in the functional programming language Haskell.
Window manager
Begun in March 2007, version 0.1 was announced in April 2007 as 500 lines of Haskell ...
is a tiling window manager
In computing, a tiling window manager is a window manager with an organization of the screen into mutually non-overlapping frames, as opposed to the more common approach (used by stacking window managers) of coordinate-based stacking of overlap ...
centered on the zipper data structure, which itself can be treated monadically as a specific case of delimited continuation In programming languages, a delimited continuation, composable continuation or partial continuation, is a "slice" of a continuation frame that has been reified into a function. Unlike regular continuations, delimited continuations return a value, a ...
s.
* LINQ
Language Integrated Query (LINQ, pronounced "link") is a Microsoft .NET Framework component that adds native data querying capabilities to .NET languages, originally released as a major part of .NET Framework 3.5 in 2007.
LINQ extends the langu ...
by Microsoft
Microsoft Corporation is an American multinational technology corporation producing computer software, consumer electronics, personal computers, and related services headquartered at the Microsoft Redmond campus located in Redmond, Washing ...
provides a query language
Query languages, data query languages or database query languages (DQL) are computer languages used to make queries in databases and information systems. A well known example is the Structured Query Language (SQL).
Types
Broadly, query language ...
for the .NET Framework
The .NET Framework (pronounced as "''dot net"'') is a proprietary software framework developed by Microsoft that runs primarily on Microsoft Windows. It was the predominant implementation of the Common Language Infrastructure (CLI) until bein ...
that is heavily influenced by functional programming concepts, including core operators for composing queries monadically.
* ZipperFS is a simple, experimental file system
In computing, file system or filesystem (often abbreviated to fs) is a method and data structure that the operating system uses to control how data is stored and retrieved. Without a file system, data placed in a storage medium would be one larg ...
that also uses the zipper structure primarily to implement its features.
* The Reactive extensions framework essentially provides a (co)monadic interface to data stream
In connection-oriented communication, a data stream is the transmission of a sequence of digitally encoded coherent signals to convey information. Typically, the transmitted symbols are grouped into a series of packets.
Data streaming has bec ...
s that realizes the observer pattern
In software design and engineering, the observer pattern is a software design pattern in which an object, named the subject, maintains a list of its dependents, called observers, and notifies them automatically of any state changes, usually by ca ...
.
History
The term "monad" in programming actually goes all the way back to the APL and J programming languages, which do tend toward being purely functional. However, in those languages, "monad" is only shorthand for a function taking one parameter (a function with two parameters being a "dyad", and so on).
The mathematician Roger Godement
Roger Godement (; 1 October 1921 – 21 July 2016) was a French mathematician, known for his work in functional analysis as well as his expository books.
Biography
Godement started as a student at the École normale supérieure in 1940, where he ...
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
Saunders Mac Lane (4 August 1909 – 14 April 2005) was an American mathematician who co-founded category theory with Samuel Eilenberg.
Early life and education
Mac Lane was born in Norwich, Connecticut, near where his family lived in Taftvill ...
. The form defined above using , however, was originally described in 1965 by mathematician Heinrich Kleisli
Heinrich Kleisli (; October 19, 1930 – April 5, 2011) was a Swiss mathematician. He is the namesake of several constructions in category theory, including the Kleisli category and Kleisli triples. He is also the namesake of the Kleisli Quer ...
in order to prove that any monad could be characterized as an adjunction between two (covariant) functors.
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
Philip Lee Wadler (born April 8, 1956) is an American computer scientist known for his contributions to programming language design and type theory. He is the chair of Theoretical Computer Science at the Laboratory for Foundations of Computer S ...
, computer scientist John C. Reynolds
John Charles Reynolds (June 1, 1935 – April 28, 2013) was an American computer scientist.
Education and affiliations
John Reynolds studied at Purdue University and then earned a Doctor of Philosophy (Ph.D.) in theoretical physics from Harvard U ...
anticipated several facets of it in the 1970s and early 1980s, when he discussed the value of continuation-passing style In functional programming, continuation-passing style (CPS) is a style of programming in which control is passed explicitly in the form of a continuation. This is contrasted with direct style, which is the usual style of programming. Gerald Jay Suss ...
, category theory as a rich source for formal semantics, and the type distinction between values and computations.
The research language Opal
Opal is a hydrated amorphous form of silica (SiO2·''n''H2O); its water content may range from 3 to 21% by weight, but is usually between 6 and 10%. Due to its amorphous property, it is classified as a mineraloid, unlike crystalline forms ...
, 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.
The computer scientist Eugenio Moggi
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:
* PhD in Computer Science, University of Edinburgh 19 ...
was the first to explicitly link the monad of category theory to functional programming, in a conference paper in 1989, followed by a more refined journal submission in 1991. In earlier work, several computer scientists had advanced using category theory to provide semantics for the lambda calculus
Lambda calculus (also written as ''λ''-calculus) is a formal system in mathematical logic for expressing computation based on function abstraction and application using variable binding and substitution. It is a universal model of computation ...
. 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.
Several others popularized and built on this idea, including Philip Wadler and Simon Peyton Jones
Simon Peyton Jones (born 18 January 1958) is a British computer scientist who researches the implementation and applications of functional programming languages, particularly lazy functional programming.
Education
Peyton Jones graduated fr ...
, 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
In programming language theory, lazy evaluation, or call-by-need, is an evaluation strategy which delays the evaluation of an expression until its value is needed (non-strict evaluation) and which also avoids repeated evaluations (sharing).
The b ...
, until switching over to a more flexible monadic interface. 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 functors;[ Brent Yorge]
Typeclassopedia
/ref> and that both monads and arrow
An arrow is a fin-stabilized projectile launched by a bow. A typical arrow usually consists of a long, stiff, straight shaft with a weighty (and usually sharp and pointed) arrowhead attached to the front end, multiple fin-like stabilizers c ...
s are monoid
In abstract algebra, a branch of mathematics, a monoid is a set equipped with an associative binary operation and an identity element. For example, the nonnegative integers with addition form a monoid, the identity element being 0.
Monoids ...
s.[ Brent Yorge]
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 A scheme is a systematic plan for the implementation of a certain idea.
Scheme or schemer may refer to:
Arts and entertainment
* ''The Scheme'' (TV series), a BBC Scotland documentary series
* The Scheme (band), an English pop band
* ''The Schem ...
, Perl
Perl is a family of two high-level, general-purpose, interpreted, dynamic programming languages. "Perl" refers to Perl 5, but from 2000 to 2019 it also referred to its redesigned "sister language", Perl 6, before the latter's name was offici ...
, Python
Python may refer to:
Snakes
* Pythonidae, a family of nonvenomous snakes found in Africa, Asia, and Australia
** ''Python'' (genus), a genus of Pythonidae found in Africa and Asia
* Python (mythology), a mythical serpent
Computing
* Python (pro ...
, Racket, Clojure
Clojure (, like ''closure'') is a dynamic and functional dialect of the Lisp programming language on the Java platform. Like other Lisp dialects, Clojure treats code as data and has a Lisp macro system. The current development process is comm ...
, Scala, F#, and have also been considered for a new ML standard.
Analysis
One benefit of the monad pattern is bringing mathematical precision on the composition of computations.
Not only can the monad laws be used to check an instance's validity, but features from related structures (like functors) can be used through subtyping
In programming language theory, subtyping (also subtype polymorphism or inclusion polymorphism) is a form of type polymorphism in which a subtype is a datatype that is related to another datatype (the supertype) by some notion of substitutabilit ...
.
Verifying the monad laws
Returning to the Maybe
example, its components were declared to make up a monad, but no proof was given that it satisfies the monad laws.
This can be rectified by plugging the specifics of Maybe
into one side of the general laws, then algebraically building a chain of equalities to reach the other side:
Law 1: eta(a) >>= f(x) ⇔ (Just a) >>= f(x) ⇔ f(a)
Law 2: ma >>= eta(x) ⇔ ma
if ma is (Just a) then
eta(a) ⇔ Just a
else or
Nothing ⇔ Nothing
end if
Law 3: (ma >>= f(x)) >>= g(y) ⇔ ma >>= (f(x) >>= g(y))
if (ma >>= f(x)) is (Just b) then if ma is (Just a) then
g(ma >>= f(x)) (f(x) >>= g(y)) a
else else
Nothing Nothing
end if end if
⇔ if ma is (Just a) and f(a) is (Just b) then
(g ∘ f) a
else if ma is (Just a) and f(a) is Nothing then
Nothing
else
Nothing
end if
Derivation from functors
Though rarer in computer science, one can use category theory directly, which defines a monad as a functor
In mathematics, specifically category theory, a functor is a Map (mathematics), mapping between Category (mathematics), categories. Functors were first considered in algebraic topology, where algebraic objects (such as the fundamental group) ar ...
with two additional natural transformation
In category theory, a branch of mathematics, a natural transformation provides a way of transforming one functor into another while respecting the internal structure (i.e., the composition of morphisms) of the categories involved. Hence, a natur ...
s.
So to begin, a structure requires a higher-order function
In mathematics and computer science, a higher-order function (HOF) is a function that does at least one of the following:
* takes one or more functions as arguments (i.e. a procedural parameter, which is a parameter of a procedure that is itself ...
(or "functional") named map
A map is a symbolic depiction emphasizing relationships between elements of some space, such as objects, regions, or themes.
Many maps are static, fixed to paper or some other durable medium, while others are dynamic or interactive. Although ...
to qualify as a functor:
This is not always a major issue, however, especially when a monad is derived from a pre-existing functor, whereupon the monad inherits automatically. (For historical reasons, this map
is instead called fmap
in Haskell.)
A monad's first transformation is actually the same from the Kleisli triple, but following the hierarchy of structures closely, it turns out characterizes an applicative functor, an intermediate structure between a monad and a basic functor. In the applicative context, is sometimes referred to as pure but is still the same function. What does differ in this construction is the law must satisfy; as is not defined, the constraint is given in terms of instead:
The final leap from applicative functor to monad comes with the second transformation, the join function (in category theory this is a natural transformation usually called ), which "flattens" nested applications of the monad:
As the characteristic function, must also satisfy three variations on the monad laws:
Regardless of whether a developer defines a direct monad or a Kleisli triple, the underlying structure will be the same, and the forms can be derived from each other easily:
Another example: List
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 List
type constructor and operator (represented with ++
for infix notation) are assumed as already given here.
Embedding a plain value in a list is also trivial in most languages:
unit(x) =
From here, applying a function iteratively with a list comprehension
A list comprehension is a Syntax of programming languages, syntactic construct available in some programming languages for creating a list based on existing list (computing), lists. It follows the form of the mathematical ''set-builder notation'' ( ...
may seem like an easy choice for and converting lists to a full monad.
The difficulty with this approach is that expects monadic functions, which in this case will output lists themselves;
as more functions are applied, layers of nested lists will accumulate, requiring more than a basic comprehension.
However, a procedure to apply any ''simple'' function over the whole list, in other words , is straightforward:
(map φ) xlist = φ(x1), φ(x2), ..., φ(xn)
Now, these two procedures already promote List
to an applicative functor.
To fully qualify as a monad, only a correct notion of to flatten repeated structure is needed, but for lists, that just means unwrapping an outer list to append the inner ones that contain values:
join(xlistlist) = join( list1, xlist2, ..., xlistn
= xlist1 ++ xlist2 ++ ... ++ xlistn
The resulting monad is not only a list, but one that automatically resizes and condenses itself as functions are applied.
can now also be derived with just a formula, then used to feed List
values through a pipeline of monadic functions:
(xlist >>= f) = join ∘ (map f) xlist
One application for this monadic list is representing nondeterministic computation.
List
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).
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.
A second situation where List
shines is composing multivalued function
In mathematics, a multivalued function, also called multifunction, many-valued function, set-valued function, is similar to a function, but may associate several values to each input. More precisely, a multivalued function from a domain to a ...
s.
For instance, the th complex root of a number should yield distinct complex numbers, but if another th root is then taken of those results, the final values should be identical to the output of the th root.
List
completely automates this issue away, condensing the results from each step into a flat, mathematically correct list.
Techniques
Monads present opportunities for interesting techniques beyond just organizing program logic. Monads can lay the groundwork for useful syntactic features while their high-level and mathematical nature enable significant abstraction.
Syntactic sugar
Although using openly often makes sense, many programmers prefer a syntax that mimics imperative statements
(called ''do-notation'' in Haskell, ''perform-notation'' in OCaml
OCaml ( , formerly Objective Caml) is a general-purpose programming language, general-purpose, multi-paradigm programming language which extends the Caml dialect of ML (programming language), ML with object-oriented programming, object-oriented ...
, ''computation expressions'' in F#, and ''for comprehension'' in Scala). This is only syntactic sugar
In computer science, syntactic sugar is syntax within a programming language that is designed to make things easier to read or to express. It makes the language "sweeter" for human use: things can be expressed more clearly, more concisely, or in an ...
that disguises a monadic pipeline as a code block
In computer programming, a block or code block or block of code is a lexical structure of source code which is grouped together. Blocks consist of one or more declarations and statements. A programming language that permits the creation of bl ...
; the compiler will then quietly translate these expressions into underlying functional code.
Translating the add
function from the Maybe
into Haskell can show this feature in action. A non-monadic version of add
in Haskell looks like this:
add mx my =
case mx of
Nothing -> Nothing
Just x -> case my of
Nothing -> Nothing
Just y -> Just (x + y)
In monadic Haskell, return
is the standard name for , plus lambda expressions must be handled explicitly, but even with these technicalities, the Maybe
monad makes for a cleaner definition:
add mx my =
mx >>= (\x ->
my >>= (\y ->
return (x + y)))
With do-notation though, this can be distilled even further into a very intuitive sequence:
add mx my = do
x <- mx
y <- my
return (x + y)
A second example shows how Maybe
can be used in an entirely different language: F#.
With computation expressions, a "safe division" function that returns None
for an undefined operand ''or'' division by zero can be written as:
let readNum () =
let s = Console.ReadLine()
let succ,v = Int32.TryParse(s)
if (succ) then Some(v) else None
let secure_div =
maybe
At build-time, the compiler will internally "de-sugar" this function into a denser chain of calls:
maybe.Delay(fun () ->
maybe.Bind(readNum(), fun x ->
maybe.Bind(readNum(), fun y ->
if (y=0) then None else maybe.Return(x / y))))
For a last example, even the general monad laws themselves can be expressed in do-notation:
do do
do do
do do
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 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.
General interface
Every monad needs a specific implementation that meets the monad laws, but other aspects like the relation to other structures or standard idioms within a language are shared by all monads.
As a result, a language or library may provide a general Monad
interface with function prototype
In computer programming, a function prototype or function interface is a declaration of a function that specifies the function’s name and type signature (arity, data types of parameters, and return type), but omits the function body. While a f ...
s, subtyping relationships, and other general facts.
Besides providing a head-start to development and guaranteeing a new monad inherits features from a supertype (such as functors), checking a monad's design against the interface adds another layer of quality control.
Operators
Monadic code can often be simplified even further through the judicious use of operators.
The functional can be especially helpful since it works on more than just ad-hoc monadic functions; so long as a monadic function should work analogously to a predefined operator, can be used to instantly "lift
Lift or LIFT may refer to:
Physical devices
* Elevator, or lift, a device used for raising and lowering people or goods
** Paternoster lift, a type of lift using a continuous chain of cars which do not stop
** Patient lift, or Hoyer lift, mobil ...
" the simpler operator into a monadic one.
With this technique, the definition of add
from the Maybe
example could be distilled into:
add(mx,my) = map (+)
The process could be taken even one step further by defining add
not just for Maybe
, but for the whole Monad
interface.
By doing this, any new monad that matches the structure interface and implements its own will immediately inherit a lifted version of add
too.
The only change to the function needed is generalizing the type signature:
add : (Monad Number, Monad Number) → Monad Number
Another monadic operator that is also useful for analysis is monadic composition (represented as infix >=>
here), which allows chaining monadic functions in a more mathematical style:
(f >=> g)(x) = f(x) >>= g
With this operator, the monad laws can be written in terms of functions alone, highlighting the correspondence to associativity and existence of an identity:
(unit >=> g) ↔ g
(f >=> unit) ↔ f
(f >=> g) >=> h ↔ f >=> (g >=> h)
In turn, the above shows the meaning of the "do" block in Haskell:
do
_p <- f(x)
_q <- g(_p)
h(_q) ↔ ( f >=> g >=> h )(x)
More examples
Identity monad
The simplest monad is the Identity monad, which just annotates plain values and functions to satisfy the monad laws:
newtype Id T = T
unit(x) = x
(x >>= f) = f(x)
Identity
does actually have valid uses though, such as providing a base case for recursive monad transformer
In functional programming, a monad transformer is a type constructor which takes a monads in functional programming, monad as an argument and returns a monad as a result.
Monad transformers can be used to compose features encapsulated by monads †...
s.
It can also be used to perform basic variable assignment within an imperative-style block.
Collections
Any collection with a proper is already a free monoid, but it turns out that List
is not the only collection
Collection or Collections may refer to:
* Cash collection, the function of an accounts receivable department
* Collection (church), money donated by the congregation during a church service
* Collection agency, agency to collect cash
* Collectio ...
that also has a well-defined and qualifies as a monad.
One can even mutate List
into these other monadic collections by simply imposing special properties on :
IO monad (Haskell)
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 IO a
can be seen as describing an action to be performed in the world, optionally providing information about the world of type a
. An action that provides no information about the world has the type IO ()
, "providing" the dummy value ()
.
When a programmer binds an IO
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.). 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
In computer science, referential transparency and referential opacity are properties of parts of computer programs. An expression is called ''referentially transparent'' if it can be replaced with its corresponding value (and vice-versa) withou ...
.
For example, Haskell has several functions for acting on the wider file system
In computing, file system or filesystem (often abbreviated to fs) is a method and data structure that the operating system uses to control how data is stored and retrieved. Without a file system, data placed in a storage medium would be one larg ...
, including one that checks whether a file exists and another that deletes a file.
Their two type signatures are:
doesFileExist :: FilePath -> IO Bool
removeFile :: FilePath -> IO ()
The first is interested in whether a given file really exists, and as a result, outputs a Boolean value
In mathematics and mathematical logic, Boolean algebra is a branch of algebra. It differs from elementary algebra in two ways. First, the values of the variables are the truth values ''true'' and ''false'', usually denoted 1 and 0, whereas in ...
within the IO
monad.
The second function, on the other hand, is only concerned with acting on the file system so the IO
container it outputs is empty.
IO
is not limited just to file I/O though; it even allows for user I/O, and along with imperative syntax sugar, can mimic a typical "Hello, World!" program
A "Hello, World!" program is generally a computer program that ignores any input and outputs or displays a message similar to "Hello, World!". A small piece of code in most general-purpose programming languages, this program is used to illustra ...
:
main :: IO ()
main = do
putStrLn "Hello, world!"
putStrLn "What is your name, user?"
name <- getLine
putStrLn ("Nice to meet you, " ++ name ++ "!")
Desugared, this translates into the following monadic pipeline (>>
in Haskell is just a variant of for when only monadic effects matter and the underlying result can be discarded):
main :: IO ()
main =
putStrLn "Hello, world!" >>
putStrLn "What is your name, user?" >>
getLine >>= (\name ->
putStrLn ("Nice to meet you, " ++ name ++ "!"))
Writer monad (JavaScript)
Another common situation is keeping a log file
In computing, logging is the act of keeping a log of events that occur in a computer system, such as problems, errors or just information on current operations. These events may occur in the operating system or in other software. A message or lo ...
or otherwise reporting a program's progress.
Sometimes, a programmer may want to log even more specific, technical data for later profiling or debugging
In computer programming and software development, debugging is the process of finding and resolving '' bugs'' (defects or problems that prevent correct operation) within computer programs, software, or systems.
Debugging tactics can involve in ...
.
The Writer monad can handle these tasks by generating auxiliary output that accumulates step-by-step.
To show how the monad pattern is not restricted to primarily functional languages, this example implements a Writer
monad in JavaScript
JavaScript (), often abbreviated as JS, is a programming language that is one of the core technologies of the World Wide Web, alongside HTML and CSS. As of 2022, 98% of Website, websites use JavaScript on the Client (computing), client side ...
.
First, an array (with nested tails) allows constructing the Writer
type as a linked list
In computer science, a linked list is a linear collection of data elements whose order is not given by their physical placement in memory. Instead, each element points to the next. It is a data structure consisting of a collection of nodes whic ...
.
The underlying output value will live in position 0 of the array, and position 1 will implicitly hold a chain of auxiliary notes:
const writer = value => alue, [;
Defining is also very simple:
const unit = value => alue, [;
Only is needed to define simple functions that output Writer
objects with debugging notes:
const squared = x => [x * x, [`$ was squared.`;
const halved = x => [x / 2, [`$ was halved.`;
A true monad still requires , but for Writer
, this amounts simply to concatenating a function's output to the monad's linked list:
const bind = (writer, transform) => ;
The sample functions can now be chained together using , but defining a version of monadic composition (called pipelog
here) allows applying these functions even more succinctly:
const pipelog = (writer, ...transforms) =>
transforms.reduce(bind, writer);
The final result is a clean separation of concerns between stepping through computations and logging them to audit later:
pipelog(unit(4), squared, halved);
// Resulting writer object = , ['4 was squared.', '16 was halved.'
Environment monad
An environment monad (also called a ''reader monad'' and a ''function monad'') allows a computation to depend on values from a shared environment. The monad type constructor maps a type to functions of type , where is the type of the shared environment. The monad functions are:
The following monadic operations are useful:
The operation is used to retrieve the current context, while executes a computation in a modified subcontext. As in a state monad, computations in the environment monad may be invoked by simply providing an environment value and applying it to an instance of the monad.
Formally, a value in an environment monad is equivalent to a function with an additional, anonymous argument; and are equivalent to the and combinators, respectively, in the SKI combinator calculus.
State monads
A state monad allows a programmer to attach state information of any type to a calculation. Given any value type, the corresponding type in the state monad is a function which accepts a state, then outputs a new state (of type s
) along with a return value (of type t
). This is similar to an environment monad, except that it also returns a new state, and thus allows modeling a ''mutable'' environment.
type State s t = s -> (t, s)
Note that this monad takes a type parameter, the type of the state information. The monad operations are defined as follows:
-- "return" produces the given value without changing the state.
return x = \s -> (x, s)
-- "bind" modifies m so that it applies f to its result.
m >>= f = \r -> let (x, s) = m r in (f x) s
Useful state operations include:
get = \s -> (s, s) -- Examine the state at this point in the computation.
put s = \_ -> ((), s) -- Replace the state.
modify f = \s -> ((), f s) -- Update the state
Another operation applies a state monad to a given initial state:
runState :: State s a -> s -> (a, s)
runState t s = t s
do-blocks in a state monad are sequences of operations that can examine and update the state data.
Informally, a state monad of state type maps the type of return values into functions of type , where is the underlying state. The and function are:
:.
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
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 ma ...
by definition.
Continuation monad
A continuation
In computer science, a continuation is an abstract representation of the control state of a computer program. A continuation implements ( reifies) the program control state, i.e. the continuation is a data structure that represents the computati ...
monad with return type maps type into functions of type . It is used to model continuation-passing style In functional programming, continuation-passing style (CPS) is a style of programming in which control is passed explicitly in the form of a continuation. This is contrasted with direct style, which is the usual style of programming. Gerald Jay Suss ...
. The return and bind functions are as follows:
:
The call-with-current-continuation
In the Scheme computer programming language, the procedure call-with-current-continuation, abbreviated call/cc, is used as a control flow operator. It has been adopted by several other programming languages.
Taking a function f as its only argum ...
function is defined as follows:
:
Program logging
The following code is pseudocode. Suppose we have two functions foo
and bar
, with types
foo : int -> int
bar : int -> int
That is, both functions take in an integer and return another integer. Then we can apply the functions in succession like so:
foo (bar x)
Where the result is the result of foo
applied to the result of bar
applied to x
.
But suppose we are debugging our program, and we would like to add logging messages to foo
and bar
.
So we change the types as so:
foo : int -> int * string
bar : int -> int * string
So that both functions return a tuple, with the result of the application as the integer,
and a logging message with information about the applied function and all the previously applied functions as the string.
Unfortunately, this means we can no longer compose
Composition or Compositions may refer to:
Arts and literature
*Composition (dance), practice and teaching of choreography
*Composition (language), in literature and rhetoric, producing a work in spoken tradition and written discourse, to include v ...
foo
and bar
, as their input type int
is not compatible with their output type int * string
. And although we can again gain composability by modifying the types of each function to be int * string -> int * string
, this would require us to add boilerplate code to each function to extract the integer from the tuple, which would get tedious as the number of such functions increases.
Instead, let us define a helper function to abstract away this boilerplate for us:
bind : int * string -> (int -> int * string) -> int * string
bind
takes in an integer and string tuple, then takes in a function (like foo
) that maps from an integer to an integer and string tuple. Its output is an integer and string tuple, which is the result of applying the input function to the integer within the input integer and string tuple.
In this way, we only need to write boilerplate code to extract the integer from the tuple once, in bind
.
Now we have regained some composability. For example:
bind (bind (x,s) bar) foo
Where (x,s)
is an integer and string tuple.
To make the benefits even clearer, let us define an infix operator as an alias for bind
:
(>>=) : int * string -> (int -> int * string) -> int * string
So that t >>= f
is the same as bind t f
.
Then the above example becomes:
((x,s) >>= bar) >>= foo
Finally, it would be nice to not have to write (x, "")
every time we wish to create an empty logging message, where ""
is the empty string.
So let us define a new function:
return : int -> int * string
Which wraps x
in the tuple described above.
Now we have a nice pipeline for logging messages:
((return x) >>= bar) >>= foo
That allows us to more easily log the effects of bar
and foo
on x
.
int * string
denotes a pseudo-coded monadic value. bind
and return
are analogous to the corresponding functions of the same name.
In fact, int * string
, bind
, and return
form a monad.
Variations
At a mathematical level, some monads have particularly nice properties and are uniquely fitted to certain problems.
Additive monads
An additive monad is a monad endowed with an additional closed, associative, binary operator mplus and an identity element
In mathematics, an identity element, or neutral element, of a binary operation operating on a set is an element of the set that leaves unchanged every element of the set when the operation is applied. This concept is used in algebraic structures su ...
under , called mzero.
The Maybe
monad can be considered additive, with Nothing
as and a variation on the OR operator as .
List
is also an additive monad, with the empty list []
acting as and the concatenation operator ++
as .
Intuitively, represents a monadic wrapper with no value from an underlying type, but is also considered a "zero" (rather than a "one") since it acts as an absorber
In high energy physics experiments, an absorber is a block of material used to absorb some of the energy of an incident particle. Absorbers can be made of a variety of materials, depending on the purpose; lead, tungsten and liquid hydrogen are c ...
for , returning whenever bound to a monadic function.
This property is two-sided, and will also return when any value is bound to a monadic zero function
0 (zero) is a number representing an empty quantity. In place-value notation such as the Hindu–Arabic numeral system, 0 also serves as a placeholder numerical digit, which works by multiplying digits to the left of 0 by the radix, usual ...
.
In category-theoretic terms, an additive monad qualifies once as a monoid over monadic functions with (as all monads do), and again over monadic values via .
Free monads
Sometimes, the general outline of a monad may be useful, but no simple pattern recommends one monad or another.
This is where a free monad comes in; as a free object
In mathematics, the idea of a free object is one of the basic concepts of abstract algebra. Informally, a free object over a set ''A'' can be thought of as being a "generic" algebraic structure over ''A'': the only equations that hold between ele ...
in the category of monads, it can represent monadic structure without any specific constraints beyond the monad laws themselves.
Just as a free monoid In abstract algebra, the free monoid on a set is the monoid whose elements are all the finite sequences (or strings) of zero or more elements from that set, with string concatenation as the monoid operation and with the unique sequence of zero eleme ...
concatenates elements without evaluation, a free monad allows chaining computations with markers to satisfy the type system, but otherwise imposes no deeper semantics itself.
For example, by working entirely through the Just
and Nothing
markers, the Maybe
monad is in fact a free monad.
The List
monad, on the other hand, is not a free monad since it brings extra, specific facts about lists (like ) into its definition.
One last example is an abstract free monad:
data Free f a
= Pure a
, Free (f (Free f a))
unit :: a -> Free f a
unit x = Pure x
bind :: Functor f => Free f a -> (a -> Free f b) -> Free f b
bind (Pure x) f = f x
bind (Free x) f = Free (fmap (\y -> bind y f) x)
Free monads, however, are ''not'' restricted to a linked-list like in this example, and can be built around other structures like tree
In botany, a tree is a perennial plant with an elongated stem, or trunk, usually supporting branches and leaves. In some usages, the definition of a tree may be narrower, including only woody plants with secondary growth, plants that are ...
s.
Using free monads intentionally may seem impractical at first, but their formal nature is particularly well-suited for syntactic problems.
A free monad can be used to track syntax and type while leaving semantics for later, and has found use in parsers and interpreters as a result.
Others have applied them to more dynamic, operational problems too, such as providing iteratee In functional programming, an iteratee is a composable abstraction for incrementally processing sequentially presented chunks of input data in a purely functional fashion. With iteratees, it is possible to lazily transform how a resource will emi ...
s within a language.
Comonads
Besides generating monads with extra properties, for any given monad, one can also define a comonad.
Conceptually, if monads represent computations built up from underlying values, then comonads can be seen as reductions back down to values.
Monadic code, in a sense, cannot be fully "unpacked"; once a value is wrapped within a monad, it remains quarantined there along with any side-effects (a good thing in purely functional programming).
Sometimes though, a problem is more about consuming contextual data, which comonads can model explicitly.
Technically, a comonad is the categorical dual
In category theory, a branch of mathematics, duality is a correspondence between the properties of a category ''C'' and the dual properties of the opposite category ''C''op. Given a statement regarding the category ''C'', by interchanging the sou ...
of a monad, which loosely means that it will have the same required components, only with the direction of the type signatures ''reversed''.
Starting from the -centric monad definition, a comonad consists of:
* A type constructor that marks the higher-order type
* The dual of , called counit here, extracts the underlying value from the comonad:
counit(wa) : W T → T
* A reversal of (also represented with =>>
) that extends a chain of reducing functions:
(wa =>> f) : (W U, W U → T) → W T
and must also satisfy duals of the monad laws:
counit ∘ ( (wa =>> f) → wb ) ↔ f(wa) → b
wa =>> counit ↔ wa
wa ( (=>> f(wx = wa)) → wb (=>> g(wy = wb)) → wc ) ↔ ( wa (=>> f(wx = wa)) → wb ) (=>> g(wy = wb)) → wc
Analogous to monads, comonads can also be derived from functors using a dual of :
* duplicate takes an already comonadic value and wraps it in another layer of comonadic structure:
duplicate(wa) : W T → W (W T)
While operations like are reversed, however, a comonad does ''not'' reverse functions it acts on, and consequently, comonads are still functors with , not cofunctors.
The alternate definition with , , and must also respect its own comonad laws:
((map duplicate) ∘ duplicate) wa ↔ (duplicate ∘ duplicate) wa ↔ wwwa
((map counit) ∘ duplicate) wa ↔ (counit ∘ duplicate) wa ↔ wa
((map map φ) ∘ duplicate) wa ↔ (duplicate ∘ (map φ)) wa ↔ wwb
And as with monads, the two forms can be converted automatically:
(map φ) wa ↔ wa =>> (φ ∘ counit) wx
duplicate wa ↔ wa =>> wx
wa =>> f(wx) ↔ ((map f) ∘ duplicate) wa
A simple example is the Product comonad, which outputs values based on an input value and shared environment data.
In fact, the Product
comonad is just the dual of the Writer
monad and effectively the same as the Reader
monad (both discussed below).
Product
and Reader
differ only in which function signatures they accept, and how they complement those functions by wrapping or unwrapping values.
A less trivial example is the Stream comonad, which can be used to represent data stream
In connection-oriented communication, a data stream is the transmission of a sequence of digitally encoded coherent signals to convey information. Typically, the transmitted symbols are grouped into a series of packets.
Data streaming has bec ...
s and attach filters to the incoming signals with .
In fact, while not as popular as monads, researchers have found comonads particularly useful for stream processing
In computer science, stream processing (also known as event stream processing, data stream processing, or distributed stream processing) is a programming paradigm which views data streams, or sequences of events in time, as the central input and ou ...
and modeling dataflow programming
In computer programming, dataflow programming is a programming paradigm that models a program as a directed graph of the data flowing between operations, thus implementing dataflow principles and architecture. Dataflow programming languages share ...
.
Due to their strict definitions, however, one cannot simply move objects back and forth between monads and comonads.
As an even higher abstraction, arrow
An arrow is a fin-stabilized projectile launched by a bow. A typical arrow usually consists of a long, stiff, straight shaft with a weighty (and usually sharp and pointed) arrowhead attached to the front end, multiple fin-like stabilizers c ...
s can subsume both structures, but finding more granular ways to combine monadic and comonadic code is an active area of research.
See also
Alternatives for modeling computations:
* Effect system
In computing, an effect system is a formal system that describes the computational effects of computer programs, such as side effects. An effect system can be used to provide a compile-time check of the possible effects of the program.
The effect ...
s (particularly algebraic effect handlers) are a different way to describe side effects as types
* Uniqueness type
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 ...
s are a third approach to handling side-effects in functional languages
Related design concepts:
* Aspect-oriented programming
In computing, aspect-oriented programming (AOP) is a programming paradigm that aims to increase modularity by allowing the separation of cross-cutting concerns. It does so by adding behavior to existing code (an advice) ''without'' modifying t ...
emphasizes separating out ancillary bookkeeping code to improve modularity and simplicity
* Inversion of control
In software engineering, inversion of control (IoC) is a design pattern in which custom-written portions of a computer program receive the flow of control from a generic framework. A software architecture with this design inverts control as co ...
is the abstract principle of calling specific functions from an overarching framework
* Type class
In computer science, a type class is a type system construct that supports ad hoc polymorphism. This is achieved by adding constraints to type variables in parametrically polymorphic types. Such a constraint typically involves a type class T and ...
es are a specific language feature used to implement monads and other structures in Haskell
* The decorator pattern
In object-oriented programming, the decorator pattern is a design pattern that allows behavior to be added to an individual object, dynamically, without affecting the behavior of other objects from the same class. The decorator pattern is often ...
is a more concrete, ad-hoc way to achieve similar benefits in object-oriented programming
Generalizations of monads:
* Applicative functors generalize from monads by keeping only and laws relating it to
* Arrow
An arrow is a fin-stabilized projectile launched by a bow. A typical arrow usually consists of a long, stiff, straight shaft with a weighty (and usually sharp and pointed) arrowhead attached to the front end, multiple fin-like stabilizers c ...
s use additional structure to bring plain functions and monads under a single interface
* Monad transformer
In functional programming, a monad transformer is a type constructor which takes a monads in functional programming, monad as an argument and returns a monad as a result.
Monad transformers can be used to compose features encapsulated by monads †...
s act on distinct monads to combine them modularly
Notes
References
External links
HaskellWiki references:
*
All About Monads
(originally by Jeff Newbern) — A comprehensive discussion of all the common monads and how they work in Haskell; includes the "mechanized assembly line" analogy.
*
Typeclassopedia
(originally by Brent Yorgey) — A detailed exposition of how the leading typeclasses in Haskell, including monads, interrelate.
Tutorials:
*
A Fistful of Monads
(from the online Haskell textbook
Learn You a Haskell for Great Good!
' — A chapter introducing monads from the starting-point of functor and applicative functor typeclasses, including examples.
*
For a Few Monads More
— A second chapter explaining more details and examples, including a Probability
monad for Markov chain
A Markov chain or Markov process is a stochastic model describing a sequence of possible events in which the probability of each event depends only on the state attained in the previous event. Informally, this may be thought of as, "What happe ...
s.
*
Functors, Applicatives, And Monads In Pictures
(by Aditya Bhargava) — A quick, humorous, and visual tutorial on monads.
Interesting cases:
*
(by Oleg Kiselyov) — A short essay explaining how Unix pipes are effectively monadic.
*
Pro Scala: Monadic Design Patterns for the Web
' (by Gregory Meredith) — An unpublished, full-length manuscript on how to improve many facets of web development in Scala with monads.
{{DEFAULTSORT:Monad (Functional Programming)
1991 in computing
Functional programming
Articles with example Haskell code
Software design patterns
Programming idioms