Monad (functional programming)

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 parser library uses monads to combine simpler parsing rules into more complex ones, and is particularly useful for smaller domain-specific languages.
• xmonad is a tiling window manager centered on the zipper data structure, which itself can be treated monadically as a specific case of delimited continuations.
• 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.
• ZipperFS is a simple, experimental file system that also uses the zipper structure primarily to implement its features.
• The Reactive extensions framework essentially provides a (co)monadic interface to data streams that realizes the observer pattern.

History

The term "monad" in programming dates to the APL and J programming languages, which 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 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. The form defined above using bind, however, was originally described in 1965 by mathematician Heinrich Kleisli 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, 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. The research 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.

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

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. 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; and that both monads and arrows are monoids.

At first, programming with monads was confined mostly 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, Perl, Python, Racket, Clojure, 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. Monad laws can be used to check an instance's validity, plus features from related structures (like functors) can be used through subtyping.

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:

<b id="mwA7s">Law 1:</b> eta(a) >>= f(x) ⇔ (Just a) >>= f(x) ⇔ f(a)

<b id="mwA70">Law 2:</b> <!--@ col 8 --> ma >>= eta(x) <!--@ col 32 --> ⇔ ma <!--@ col 8 --> <b id="mwA74">if</b> ma <b id="mwA78">is</b> (Just a) <b id="mwA8A">then</b> <!--@ col 12 --> eta(a) <!--@ col 32 --> ⇔ Just a <!--@ col 8 --> <b id="mwA8E">else</b> <!--@ col 36--> <b id="mwA8I">or</b> <!--@ col 12 --> Nothing <!--@ col 32 --> ⇔ Nothing <!--@ col 8 --> <b id="mwA8M">end if</b>

<b id="mwA8U">Law 3:</b> <!--@ col 8 --> <b id="mwA8Y">(</b>ma >>= f(x)<b id="mwA8c">)</b> >>= g(y) <!--@ col 52 --> ⇔ ma >>= <b id="mwA8g">(</b>f(x) >>= g(y)<b id="mwA8k">)</b> <!--@ col 8 --> <b id="mwA8o">if</b> (ma >>= f(x)) <b id="mwA8s">is</b> (Just b) <b id="mwA8w">then</b> <!--@ col 52 --> <b id="mwA80">if</b> ma <b id="mwA84">is</b> (Just a) <b id="mwA88">then</b> <!--@ col 12 --> g(ma >>= f(x)) <!--@ col 56 --> (f(x) >>= g(y)) a <!--@ col 8 --> <b id="mwA9A">else</b> <!--@ col 52 --> <b id="mwA9E">else</b> <!--@ col 12 --> Nothing <!--@ col 56 --> Nothing <!--@ col 8 --> <b id="mwA9I">end if</b> <!--@ col 52 --> <b id="mwA9M">end if</b> <!--@ col 16 --> ⇔ <b id="mwA9Q">if</b> ma <b id="mwA9U">is</b> (Just a) <b id="mwA9Y">and</b> f(a) <b id="mwA9c">is</b> (Just b) <b id="mwA9g">then</b> <!--@ col 20 --> (g ∘ f) a <!--@ col 16 --> <b id="mwA9k">else if</b> ma <b id="mwA9o">is</b> (Just a) <b id="mwA9s">and</b> f(a) <b id="mwA9w">is Nothing then</b> <!--@ col 20 --> Nothing <!--@ col 16 --> <b id="mwA90">else</b> <!--@ col 20 --> Nothing <!--@ col 16 --> <b id="mwA94">end if</b>

Derivation from functors

Though rarer in computer science, one can use category theory directly, which defines a monad as a functor with two added natural transformations. So to begin, a structure requires a higher-order function (or "functional") named map to qualify as a functor:

map : (a → b) → (ma → mb)

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

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

(unit ∘ φ) x ↔ ((map φ) ∘ unit) x ↔ x

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:

join(mma) : M (M T) → M T

As the characteristic function, join must also satisfy three variations on the monad laws:

(join ∘ (map join)) mmma ↔ (join ∘ join) mmma ↔ ma(join ∘ (map unit)) ma ↔ (join ∘ unit) ma ↔ ma(join ∘ (map map φ)) mma ↔ ((map φ) ∘ join) mma ↔ mb

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:

(map φ) ma ↔ ma >>= (unit ∘ φ)join(mma) ↔ mma >>= idma >>= f ↔ (join ∘ (map f)) ma

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 append 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) = [x]

From here, applying a function iteratively with a list comprehension may seem like an easy choice for bind and converting lists to a full monad. The difficulty with this approach is that bind 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 map, 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 join 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([xlist1, 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. bind 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 functions. For instance, the nth complex root of a number should yield n distinct complex numbers, but if another mth root is then taken of those results, the final m•n values should be identical to the output of the m•nth root. List completely automates this issue away, condensing the results from each step into a flat, mathematically correct list.

Techniques

Monads enable various techniques beyond structuring program logic. They provide the basis for specific syntactic features and allow abstraction through their mathematical properties.

Syntactic sugar do-notation

Although using 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#, and for comprehension in Scala). This is only syntactic sugar that disguises a monadic pipeline as a code block; the compiler then automatically translates 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:

<span id="mwBGw"></span><span class="nf" id="mwBG0">add</span><span class="w" id="mwBG4"> </span><span class="n" id="mwBG8">mx</span><span class="w" id="mwBHA"> </span><span class="n" id="mwBHE">my</span><span class="w" id="mwBHI"> </span><span class="ow" id="mwBHM">=</span> <span class="w" id="mwBHQ"> </span><span class="kr" id="mwBHU">case</span><span class="w" id="mwBHY"> </span><span class="n" id="mwBHc">mx</span><span class="w" id="mwBHg"> </span><span class="kr" id="mwBHk">of</span> <span class="w" id="mwBHo"> </span><span class="kt" id="mwBHs">Nothing</span><span class="w" id="mwBHw"> </span><span class="ow" id="mwBH0">-></span><span class="w" id="mwBH4"> </span><span class="kt" id="mwBH8">Nothing</span> <span class="w" id="mwBIA"> </span><span class="kt" id="mwBIE">Just</span><span class="w" id="mwBII"> </span><span class="n" id="mwBIM">x</span><span class="w" id="mwBIQ"> </span><span class="ow" id="mwBIU">-></span><span class="w" id="mwBIY"> </span><span class="kr" id="mwBIc">case</span><span class="w" id="mwBIg"> </span><span class="n" id="mwBIk">my</span><span class="w" id="mwBIo"> </span><span class="kr" id="mwBIs">of</span> <span class="w" id="mwBIw"> </span><span class="kt" id="mwBI0">Nothing</span><span class="w" id="mwBI4"> </span><span class="ow" id="mwBI8">-></span><span class="w" id="mwBJA"> </span><span class="kt" id="mwBJE">Nothing</span> <span class="w" id="mwBJI"> </span><span class="kt" id="mwBJM">Just</span><span class="w" id="mwBJQ"> </span><span class="n" id="mwBJU">y</span><span class="w" id="mwBJY"> </span><span class="ow" id="mwBJc">-></span><span class="w" id="mwBJg"> </span><span class="kt" id="mwBJk">Just</span><span class="w" id="mwBJo"> </span><span class="p" id="mwBJs">(</span><span class="n" id="mwBJw">x</span><span class="w" id="mwBJ0"> </span><span class="o" id="mwBJ4">+</span><span class="w" id="mwBJ8"> </span><span class="n" id="mwBKA">y</span><span class="p" id="mwBKE">)</span>

In monadic Haskell, return is the standard name for unit, plus lambda expressions must be handled explicitly, but even with these technicalities, the Maybe monad makes for a cleaner definition:

<span id="mwBKg"></span><span class="nf" id="mwBKk">add</span><span class="w" id="mwBKo"> </span><span class="n" id="mwBKs">mx</span><span class="w" id="mwBKw"> </span><span class="n" id="mwBK0">my</span><span class="w" id="mwBK4"> </span><span class="ow" id="mwBK8">=</span> <span class="w" id="mwBLA"> </span><span class="n" id="mwBLE">mx</span><span class="w" id="mwBLI"> </span><span class="o" id="mwBLM">>>=</span><span class="w" id="mwBLQ"> </span><span class="p" id="mwBLU">(</span><span class="nf" id="mwBLY">\</span><span class="n" id="mwBLc">x</span><span class="w" id="mwBLg"> </span><span class="ow" id="mwBLk">-></span> <span class="w" id="mwBLo"> </span><span class="n" id="mwBLs">my</span><span class="w" id="mwBLw"> </span><span class="o" id="mwBL0">>>=</span><span class="w" id="mwBL4"> </span><span class="p" id="mwBL8">(</span><span class="nf" id="mwBMA">\</span><span class="n" id="mwBME">y</span><span class="w" id="mwBMI"> </span><span class="ow" id="mwBMM">-></span> <span class="w" id="mwBMQ"> </span><span class="n" id="mwBMU">return</span><span class="w" id="mwBMY"> </span><span class="p" id="mwBMc">(</span><span class="n" id="mwBMg">x</span><span class="w" id="mwBMk"> </span><span class="o" id="mwBMo">+</span><span class="w" id="mwBMs"> </span><span class="n" id="mwBMw">y</span><span class="p" id="mwBM0">)))</span>

With do-notation though, this can be distilled even further into a very intuitive sequence:

<span id="mwBNE"></span><span class="nf" id="mwBNI">add</span><span class="w" id="mwBNM"> </span><span class="n" id="mwBNQ">mx</span><span class="w" id="mwBNU"> </span><span class="n" id="mwBNY">my</span><span class="w" id="mwBNc"> </span><span class="ow" id="mwBNg">=</span><span class="w" id="mwBNk"> </span><span class="kr" id="mwBNo">do</span> <span class="w" id="mwBNs"> </span><span class="n" id="mwBNw">x</span><span class="w" id="mwBN0"> </span><span class="ow" id="mwBN4"><-</span><span class="w" id="mwBN8"> </span><span class="n" id="mwBOA">mx</span> <span class="w" id="mwBOE"> </span><span class="n" id="mwBOI">y</span><span class="w" id="mwBOM"> </span><span class="ow" id="mwBOQ"><-</span><span class="w" id="mwBOU"> </span><span class="n" id="mwBOY">my</span> <span class="w" id="mwBOc"> </span><span class="n" id="mwBOg">return</span><span class="w" id="mwBOk"> </span><span class="p" id="mwBOo">(</span><span class="n" id="mwBOs">x</span><span class="w" id="mwBOw"> </span><span class="o" id="mwBO0">+</span><span class="w" id="mwBO4"> </span><span class="n" id="mwBO8">y</span><span class="p" id="mwBPA">)</span>

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:

<span id="mwBPc"></span><span class="k" id="mwBPg">let</span> <span class="n" id="mwBPk">readNum</span> <span class="bp" id="mwBPo">()</span> <span class="o" id="mwBPs">=</span> <span class="k" id="mwBPw">let</span> <span class="n" id="mwBP0">s</span> <span class="o" id="mwBP4">=</span> <span class="nn" id="mwBP8">Console</span><span class="p" id="mwBQA">.</span><span class="nc" id="mwBQE">ReadLine</span><span class="bp" id="mwBQI">()</span> <span class="k" id="mwBQM">let</span> <span class="n" id="mwBQQ">succ</span><span class="o" id="mwBQU">,</span><span class="n" id="mwBQY">v</span> <span class="o" id="mwBQc">=</span> <span class="nn" id="mwBQg">Int32</span><span class="p" id="mwBQk">.</span><span class="nc" id="mwBQo">TryParse</span><span class="o" id="mwBQs">(</span><span class="n" id="mwBQw">s</span><span class="o" id="mwBQ0">)</span> <span class="k" id="mwBQ4">if</span> <span class="o" id="mwBQ8">(</span><span class="n" id="mwBRA">succ</span><span class="o" id="mwBRE">)</span> <span class="k" id="mwBRI">then</span> <span class="nc" id="mwBRM">Some</span><span class="o" id="mwBRQ">(</span><span class="n" id="mwBRU">v</span><span class="o" id="mwBRY">)</span> <span class="k" id="mwBRc">else</span> <span class="nc" id="mwBRg">None</span> <span class="k" id="mwBRk">let</span> <span class="n" id="mwBRo">secure_div</span> <span class="o" id="mwBRs">=</span> <span class="n" id="mwBRw">maybe</span> <span class="o" id="mwBR0">{</span> <span class="k" id="mwBR4">let</span><span class="o" id="mwBR8">!</span> <span class="n" id="mwBSA">x</span> <span class="o" id="mwBSE">=</span> <span class="n" id="mwBSI">readNum</span><span class="bp" id="mwBSM">()</span> <span class="k" id="mwBSQ">let</span><span class="o" id="mwBSU">!</span> <span class="n" id="mwBSY">y</span> <span class="o" id="mwBSc">=</span> <span class="n" id="mwBSg">readNum</span><span class="bp" id="mwBSk">()</span> <span class="k" id="mwBSo">if</span> <span class="o" id="mwBSs">(</span><span class="n" id="mwBSw">y</span> <span class="o" id="mwBS0">=</span> <span class="mi" id="mwBS4">0</span><span class="o" id="mwBS8">)</span> <span class="k" id="mwBTA">then</span> <span class="nc" id="mwBTE">None</span> <span class="k" id="mwBTI">else</span> <span class="n" id="mwBTM">return</span> <span class="o" id="mwBTQ">(</span><span class="n" id="mwBTU">x</span> <span class="o" id="mwBTY">/</span> <span class="n" id="mwBTc">y</span><span class="o" id="mwBTg">)</span> <span class="o" id="mwBTk">}</span>

At build-time, the compiler will internally "de-sugar" this function into a denser chain of bind calls:

<span id="mwBT4"></span><span class="n" id="mwBT8">maybe</span><span class="o" id="mwBUA">.</span><span class="nc" id="mwBUE">Delay</span><span class="o" id="mwBUI">(</span><span class="k" id="mwBUM">fun</span> <span class="bp" id="mwBUQ">()</span> <span class="o" id="mwBUU">-></span> <span class="n" id="mwBUY">maybe</span><span class="o" id="mwBUc">.</span><span class="nc" id="mwBUg">Bind</span><span class="o" id="mwBUk">(</span><span class="n" id="mwBUo">readNum</span><span class="bp" id="mwBUs">()</span><span class="o" id="mwBUw">,</span> <span class="k" id="mwBU0">fun</span> <span class="n" id="mwBU4">x</span> <span class="o" id="mwBU8">-></span> <span class="n" id="mwBVA">maybe</span><span class="o" id="mwBVE">.</span><span class="nc" id="mwBVI">Bind</span><span class="o" id="mwBVM">(</span><span class="n" id="mwBVQ">readNum</span><span class="bp" id="mwBVU">()</span><span class="o" id="mwBVY">,</span> <span class="k" id="mwBVc">fun</span> <span class="n" id="mwBVg">y</span> <span class="o" id="mwBVk">-></span> <span class="k" id="mwBVo">if</span> <span class="o" id="mwBVs">(</span><span class="n" id="mwBVw">y</span><span class="o" id="mwBV0">=</span><span class="mi" id="mwBV4">0</span><span class="o" id="mwBV8">)</span> <span class="k" id="mwBWA">then</span> <span class="nc" id="mwBWE">None</span> <span class="k" id="mwBWI">else</span> <span class="n" id="mwBWM">maybe</span><span class="o" id="mwBWQ">.</span><span class="nc" id="mwBWU">Return</span><span class="o" id="mwBWY">(</span><span class="n" id="mwBWc">x</span> <span class="o" id="mwBWg">/</span> <span class="n" id="mwBWk">y</span><span class="o" id="mwBWo">))))</span>

For a last example, even the general monad laws themselves can be expressed in do-notation:

<span id="mwBW4"></span><span class="kr" id="mwBW8">do</span><span class="w" id="mwBXA"> </span><span class="p" id="mwBXE">{</span><span class="w" id="mwBXI"> </span><span class="n" id="mwBXM">x</span><span class="w" id="mwBXQ"> </span><span class="ow" id="mwBXU"><-</span><span class="w" id="mwBXY"> </span><span class="n" id="mwBXc">return</span><span class="w" id="mwBXg"> </span><span class="n" id="mwBXk">v</span><span class="p" id="mwBXo">;</span><span class="w" id="mwBXs"> </span><span class="n" id="mwBXw">f</span><span class="w" id="mwBX0"> </span><span class="n" id="mwBX4">x</span><span class="w" id="mwBX8"> </span><span class="p" id="mwBYA">}</span><span class="w" id="mwBYE"> </span><span class="o" id="mwBYI">==</span><span class="w" id="mwBYM"> </span><span class="kr" id="mwBYQ">do</span><span class="w" id="mwBYU"> </span><span class="p" id="mwBYY">{</span><span class="w" id="mwBYc"> </span><span class="n" id="mwBYg">f</span><span class="w" id="mwBYk"> </span><span class="n" id="mwBYo">v</span><span class="w" id="mwBYs"> </span><span class="p" id="mwBYw">}</span> <span class="kr" id="mwBY0">do</span><span class="w" id="mwBY4"> </span><span class="p" id="mwBY8">{</span><span class="w" id="mwBZA"> </span><span class="n" id="mwBZE">x</span><span class="w" id="mwBZI"> </span><span class="ow" id="mwBZM"><-</span><span class="w" id="mwBZQ"> </span><span class="n" id="mwBZU">m</span><span class="p" id="mwBZY">;</span><span class="w" id="mwBZc"> </span><span class="n" id="mwBZg">return</span><span class="w" id="mwBZk"> </span><span class="n" id="mwBZo">x</span><span class="w" id="mwBZs"> </span><span class="p" id="mwBZw">}</span><span class="w" id="mwBZ0"> </span><span class="o" id="mwBZ4">==</span><span class="w" id="mwBZ8"> </span><span class="kr" id="mwBaA">do</span><span class="w" id="mwBaE"> </span><span class="p" id="mwBaI">{</span><span class="w" id="mwBaM"> </span><span class="n" id="mwBaQ">m</span><span class="w" id="mwBaU"> </span><span class="p" id="mwBaY">}</span> <span class="kr" id="mwBac">do</span><span class="w" id="mwBag"> </span><span class="p" id="mwBak">{</span><span class="w" id="mwBao"> </span><span class="n" id="mwBas">y</span><span class="w" id="mwBaw"> </span><span class="ow" id="mwBa0"><-</span><span class="w" id="mwBa4"> </span><span class="kr" id="mwBa8">do</span><span class="w" id="mwBbA"> </span><span class="p" id="mwBbE">{</span><span class="w" id="mwBbI"> </span><span class="n" id="mwBbM">x</span><span class="w" id="mwBbQ"> </span><span class="ow" id="mwBbU"><-</span><span class="w" id="mwBbY"> </span><span class="n" id="mwBbc">m</span><span class="p" id="mwBbg">;</span><span class="w" id="mwBbk"> </span><span class="n" id="mwBbo">f</span><span class="w" id="mwBbs"> </span><span class="n" id="mwBbw">x</span><span class="w" id="mwBb0"> </span><span class="p" id="mwBb4">};</span><span class="w" id="mwBb8"> </span><span class="n" id="mwBcA">g</span><span class="w" id="mwBcE"> </span><span class="n" id="mwBcI">y</span><span class="w" id="mwBcM"> </span><span class="p" id="mwBcQ">}</span><span class="w" id="mwBcU"> </span><span class="o" id="mwBcY">==</span><span class="w" id="mwBcc"> </span><span class="kr" id="mwBcg">do</span><span class="w" id="mwBck"> </span><span class="p" id="mwBco">{</span><span class="w" id="mwBcs"> </span><span class="n" id="mwBcw">x</span><span class="w" id="mwBc0"> </span><span class="ow" id="mwBc4"><-</span><span class="w" id="mwBc8"> </span><span class="n" id="mwBdA">m</span><span class="p" id="mwBdE">;</span><span class="w" id="mwBdI"> </span><span class="n" id="mwBdM">y</span><span class="w" id="mwBdQ"> </span><span class="ow" id="mwBdU"><-</span><span class="w" id="mwBdY"> </span><span class="n" id="mwBdc">f</span><span class="w" id="mwBdg"> </span><span class="n" id="mwBdk">x</span><span class="p" id="mwBdo">;</span><span class="w" id="mwBds"> </span><span class="n" id="mwBdw">g</span><span class="w" id="mwBd0"> </span><span class="n" id="mwBd4">y</span><span class="w" id="mwBd8"> </span><span class="p" id="mwBeA">}</span>

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 prototypes, 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 map 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, map can be used to instantly "lift" 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 map 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<sup about="#mwt289" class="mw-ref reference" id="cite_ref-Lifting_43-0" rel="dc:references" typeof="mw:Extension/ref" data-mw='{"name":"ref","attrs":{"name":"Lifting"},"body":{"id":"mw-reference-text-cite_note-Lifting-43"}}'><a href="./Monad_(functional_programming)#cite_note-Lifting-43" id="mwBfo"><span class="mw-reflink-text" id="mwBfs"><span class="cite-bracket" id="mwBfw">[</span>31<span class="cite-bracket" id="mwBf0">]</span></span></a></sup>

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)<sup about="#mwt290" class="mw-ref reference" id="cite_ref-RealWorldHaskell_1-5" rel="dc:references" typeof="mw:Extension/ref" data-mw='{"name":"ref","attrs":{"name":"RealWorldHaskell"}}'><a href="./Monad_(functional_programming)#cite_note-RealWorldHaskell-1" id="mwBgM"><span class="mw-reflink-text" id="mwBgQ"><span class="cite-bracket" id="mwBgU">[</span>1<span class="cite-bracket" id="mwBgY">]</span></span></a></sup>

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:

<b id="mwBg4">newtype</b> 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 transformers. It can also be used to perform basic variable assignment within an imperative-style block.

Collections

Any collection with a proper append is already a monoid, but it turns out that List is not the only collection that also has a well-defined join and qualifies as a monad. One can even mutate List into these other monadic collections by simply imposing special properties on append:

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

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. Their two type signatures are:

<span id="mwBl4"></span><span class="nf" id="mwBl8">doesFileExist</span><span class="w" id="mwBmA"> </span><span class="ow" id="mwBmE">::</span><span class="w" id="mwBmI"> </span><span class="kt" id="mwBmM">FilePath</span><span class="w" id="mwBmQ"> </span><span class="ow" id="mwBmU">-></span><span class="w" id="mwBmY"> </span><span class="kt" id="mwBmc">IO</span><span class="w" id="mwBmg"> </span><span class="kt" id="mwBmk">Bool</span> <span class="nf" id="mwBmo">removeFile</span><span class="w" id="mwBms"> </span><span class="ow" id="mwBmw">::</span><span class="w" id="mwBm0"> </span><span class="kt" id="mwBm4">FilePath</span><span class="w" id="mwBm8"> </span><span class="ow" id="mwBnA">-></span><span class="w" id="mwBnE"> </span><span class="kt" id="mwBnI">IO</span><span class="w" id="mwBnM"> </span><span class="nb" id="mwBnQ">()</span>

The first is interested in whether a given file really exists, and as a result, outputs a Boolean value within the IO monad. The second function, in contrast, 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:

<span id="mwBn4"></span><span class="nf" id="mwBn8">main</span><span class="w" id="mwBoA"> </span><span class="ow" id="mwBoE">::</span><span class="w" id="mwBoI"> </span><span class="kt" id="mwBoM">IO</span><span class="w" id="mwBoQ"> </span><span class="nb" id="mwBoU">()</span> <span class="nf" id="mwBoY">main</span><span class="w" id="mwBoc"> </span><span class="ow" id="mwBog">=</span><span class="w" id="mwBok"> </span><span class="kr" id="mwBoo">do</span> <span class="w" id="mwBos"> </span><span class="n" id="mwBow">putStrLn</span><span class="w" id="mwBo0"> </span><span class="s" id="mwBo4">"Hello, world!"</span> <span class="w" id="mwBo8"> </span><span class="n" id="mwBpA">putStrLn</span><span class="w" id="mwBpE"> </span><span class="s" id="mwBpI">"What is your name, user?"</span> <span class="w" id="mwBpM"> </span><span class="n" id="mwBpQ">name</span><span class="w" id="mwBpU"> </span><span class="ow" id="mwBpY"><-</span><span class="w" id="mwBpc"> </span><span class="n" id="mwBpg">getLine</span> <span class="w" id="mwBpk"> </span><span class="n" id="mwBpo">putStrLn</span><span class="w" id="mwBps"> </span><span class="p" id="mwBpw">(</span><span class="s" id="mwBp0">"Nice to meet you, "</span><span class="w" id="mwBp4"> </span><span class="o" id="mwBp8">++</span><span class="w" id="mwBqA"> </span><span class="n" id="mwBqE">name</span><span class="w" id="mwBqI"> </span><span class="o" id="mwBqM">++</span><span class="w" id="mwBqQ"> </span><span class="s" id="mwBqU">"!"</span><span class="p" id="mwBqY">)</span>

Desugared, this translates into the following monadic pipeline (>> in Haskell is just a variant of bind for when only monadic effects matter and the underlying result can be discarded):

<span id="mwBqw"></span><span class="nf" id="mwBq0">main</span><span class="w" id="mwBq4"> </span><span class="ow" id="mwBq8">::</span><span class="w" id="mwBrA"> </span><span class="kt" id="mwBrE">IO</span><span class="w" id="mwBrI"> </span><span class="nb" id="mwBrM">()</span> <span class="nf" id="mwBrQ">main</span><span class="w" id="mwBrU"> </span><span class="ow" id="mwBrY">=</span> <span class="w" id="mwBrc"> </span><span class="n" id="mwBrg">putStrLn</span><span class="w" id="mwBrk"> </span><span class="s" id="mwBro">"Hello, world!"</span><span class="w" id="mwBrs"> </span><span class="o" id="mwBrw">>></span> <span class="w" id="mwBr0"> </span><span class="n" id="mwBr4">putStrLn</span><span class="w" id="mwBr8"> </span><span class="s" id="mwBsA">"What is your name, user?"</span><span class="w" id="mwBsE"> </span><span class="o" id="mwBsI">>></span><span class="w" id="mwBsM"> </span> <span class="w" id="mwBsQ"> </span><span class="n" id="mwBsU">getLine</span><span class="w" id="mwBsY"> </span><span class="o" id="mwBsc">>>=</span><span class="w" id="mwBsg"> </span><span class="p" id="mwBsk">(</span><span class="nf" id="mwBso">\</span><span class="n" id="mwBss">name</span><span class="w" id="mwBsw"> </span><span class="ow" id="mwBs0">-></span> <span class="w" id="mwBs4"> </span><span class="n" id="mwBs8">putStrLn</span><span class="w" id="mwBtA"> </span><span class="p" id="mwBtE">(</span><span class="s" id="mwBtI">"Nice to meet you, "</span><span class="w" id="mwBtM"> </span><span class="o" id="mwBtQ">++</span><span class="w" id="mwBtU"> </span><span class="n" id="mwBtY">name</span><span class="w" id="mwBtc"> </span><span class="o" id="mwBtg">++</span><span class="w" id="mwBtk"> </span><span class="s" id="mwBto">"!"</span><span class="p" id="mwBts">))</span>

Writer monad (Java)

Another common situation is keeping a log file or otherwise reporting a program's progress. Sometimes, a programmer may want to log even more specific, technical data for later profiling or debugging. 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 Java, stored in a class representing the Writer monad.

<span id="mwBug"></span><span class="kn" id="mwBuk">import</span><span class="w" id="mwBuo"> </span><span class="nn" id="mwBus">java.util.ArrayList</span><span class="p" id="mwBuw">;</span> <span class="kn" id="mwBu0">import</span><span class="w" id="mwBu4"> </span><span class="nn" id="mwBu8">java.util.List</span><span class="p" id="mwBvA">;</span> <span class="kn" id="mwBvE">import</span><span class="w" id="mwBvI"> </span><span class="nn" id="mwBvM">java.util.function.Function</span><span class="p" id="mwBvQ">;</span> <span class="kd" id="mwBvU">record</span> <span class="nc" id="mwBvY">Writer</span><span class="o" id="mwBvc"><</span><span class="n" id="mwBvg">T</span><span class="o" id="mwBvk">></span><span class="p" id="mwBvo">(</span><span class="n" id="mwBvs">T</span><span class="w" id="mwBvw"> </span><span class="n" id="mwBv0">value</span><span class="p" id="mwBv4">,</span><span class="w" id="mwBv8"> </span><span class="n" id="mwBwA">List</span><span class="o" id="mwBwE"><</span><span class="n" id="mwBwI">String</span><span class="o" id="mwBwM">></span><span class="w" id="mwBwQ"> </span><span class="n" id="mwBwU">log</span><span class="p" id="mwBwY">)</span><span class="w" id="mwBwc"> </span><span class="p" id="mwBwg">{</span> <span class="w" id="mwBwk"> </span><span class="c1" id="mwBwo">// Internals here...</span> <span class="p" id="mwBws">}</span>

Defining unit is also very simple:

<span id="mwBxA"></span><span class="kd" id="mwBxE">record</span> <span class="nc" id="mwBxI">Writer</span><span class="o" id="mwBxM"><</span><span class="n" id="mwBxQ">T</span><span class="o" id="mwBxU">></span><span class="p" id="mwBxY">(</span><span class="n" id="mwBxc">T</span><span class="w" id="mwBxg"> </span><span class="n" id="mwBxk">value</span><span class="p" id="mwBxo">,</span><span class="w" id="mwBxs"> </span><span class="n" id="mwBxw">List</span><span class="o" id="mwBx0"><</span><span class="n" id="mwBx4">String</span><span class="o" id="mwBx8">></span><span class="w" id="mwByA"> </span><span class="n" id="mwByE">log</span><span class="p" id="mwByI">)</span><span class="w" id="mwByM"> </span><span class="p" id="mwByQ">{</span> <span class="w" id="mwByU"> </span><span class="c1" id="mwByY">// ...</span> <span class="w" id="mwByc"> </span><span class="kd" id="mwByg">public</span><span class="w" id="mwByk"> </span><span class="kd" id="mwByo">static</span><span class="w" id="mwBys"> </span><span class="o" id="mwByw"><</span><span class="n" id="mwBy0">T</span><span class="o" id="mwBy4">></span><span class="w" id="mwBy8"> </span><span class="n" id="mwBzA">Writer</span><span class="o" id="mwBzE"><</span><span class="n" id="mwBzI">T</span><span class="o" id="mwBzM">></span><span class="w" id="mwBzQ"> </span><span class="nf" id="mwBzU">unit</span><span class="p" id="mwBzY">(</span><span class="n" id="mwBzc">T</span><span class="w" id="mwBzg"> </span><span class="n" id="mwBzk">value</span><span class="p" id="mwBzo">)</span><span class="w" id="mwBzs"> </span><span class="p" id="mwBzw">{</span> <span class="w" id="mwBz0"> </span><span class="k" id="mwBz4">return</span><span class="w" id="mwBz8"> </span><span class="k" id="mwB0A">new</span><span class="w" id="mwB0E"> </span><span class="n" id="mwB0I">Writer</span><span class="o" id="mwB0M"><></span><span class="p" id="mwB0Q">(</span><span class="n" id="mwB0U">value</span><span class="p" id="mwB0Y">,</span><span class="w" id="mwB0c"> </span><span class="k" id="mwB0g">new</span><span class="w" id="mwB0k"> </span><span class="n" id="mwB0o">ArrayList</span><span class="o" id="mwB0s"><></span><span class="p" id="mwB0w">());</span> <span class="w" id="mwB00"> </span><span class="p" id="mwB04">}</span> <span class="p" id="mwB08">}</span>

Only unit is needed to define simple functions that output Writer objects with debugging notes:

<span id="mwB1U"></span><span class="kn" id="mwB1Y">import</span><span class="w" id="mwB1c"> </span><span class="nn" id="mwB1g">java.util.List</span><span class="p" id="mwB1k">;</span> <span class="kd" id="mwB1o">class</span> <span class="nc" id="mwB1s">Ops</span><span class="w" id="mwB1w"> </span><span class="p" id="mwB10">{</span> <span class="w" id="mwB14"> </span><span class="kd" id="mwB18">private</span><span class="w" id="mwB2A"> </span><span class="nf" id="mwB2E">Ops</span><span class="p" id="mwB2I">()</span><span class="w" id="mwB2M"> </span><span class="p" id="mwB2Q">{}</span> <span class="w" id="mwB2U"> </span><span class="kd" id="mwB2Y">public</span><span class="w" id="mwB2c"> </span><span class="kd" id="mwB2g">static</span><span class="w" id="mwB2k"> </span><span class="n" id="mwB2o">Writer</span><span class="o" id="mwB2s"><</span><span class="n" id="mwB2w">Integer</span><span class="o" id="mwB20">></span><span class="w" id="mwB24"> </span><span class="nf" id="mwB28">squared</span><span class="p" id="mwB3A">(</span><span class="kt" id="mwB3E">int</span><span class="w" id="mwB3I"> </span><span class="n" id="mwB3M">x</span><span class="p" id="mwB3Q">)</span><span class="w" id="mwB3U"> </span><span class="p" id="mwB3Y">{</span> <span class="w" id="mwB3c"> </span><span class="k" id="mwB3g">return</span><span class="w" id="mwB3k"> </span><span class="k" id="mwB3o">new</span><span class="w" id="mwB3s"> </span><span class="n" id="mwB3w">Writer</span><span class="o" id="mwB30"><></span><span class="p" id="mwB34">(</span><span class="n" id="mwB38">x</span><span class="w" id="mwB4A"> </span><span class="o" id="mwB4E">*</span><span class="w" id="mwB4I"> </span><span class="n" id="mwB4M">x</span><span class="p" id="mwB4Q">,</span><span class="w" id="mwB4U"> </span><span class="n" id="mwB4Y">List</span><span class="p" id="mwB4c">.</span><span class="na" id="mwB4g">of</span><span class="p" id="mwB4k">(</span><span class="n" id="mwB4o">String</span><span class="p" id="mwB4s">.</span><span class="na" id="mwB4w">format</span><span class="p" id="mwB40">(</span><span class="s" id="mwB44">"%d was squared."</span><span class="p" id="mwB48">,</span><span class="w" id="mwB5A"> </span><span class="n" id="mwB5E">x</span><span class="p" id="mwB5I">)));</span> <span class="w" id="mwB5M"> </span><span class="p" id="mwB5Q">}</span> <span class="w" id="mwB5U"> </span><span class="kd" id="mwB5Y">public</span><span class="w" id="mwB5c"> </span><span class="kd" id="mwB5g">static</span><span class="w" id="mwB5k"> </span><span class="n" id="mwB5o">Writer</span><span class="o" id="mwB5s"><</span><span class="n" id="mwB5w">Integer</span><span class="o" id="mwB50">></span><span class="w" id="mwB54"> </span><span class="nf" id="mwB58">halved</span><span class="p" id="mwB6A">(</span><span class="kt" id="mwB6E">int</span><span class="w" id="mwB6I"> </span><span class="n" id="mwB6M">x</span><span class="p" id="mwB6Q">)</span><span class="w" id="mwB6U"> </span><span class="p" id="mwB6Y">{</span> <span class="w" id="mwB6c"> </span><span class="k" id="mwB6g">return</span><span class="w" id="mwB6k"> </span><span class="k" id="mwB6o">new</span><span class="w" id="mwB6s"> </span><span class="n" id="mwB6w">Writer</span><span class="o" id="mwB60"><></span><span class="p" id="mwB64">(</span><span class="n" id="mwB68">x</span><span class="w" id="mwB7A"> </span><span class="o" id="mwB7E">/</span><span class="w" id="mwB7I"> </span><span class="mi" id="mwB7M">2</span><span class="p" id="mwB7Q">,</span><span class="w" id="mwB7U"> </span><span class="n" id="mwB7Y">List</span><span class="p" id="mwB7c">.</span><span class="na" id="mwB7g">of</span><span class="p" id="mwB7k">(</span><span class="n" id="mwB7o">String</span><span class="p" id="mwB7s">.</span><span class="na" id="mwB7w">format</span><span class="p" id="mwB70">(</span><span class="s" id="mwB74">"%d was halved."</span><span class="p" id="mwB78">,</span><span class="w" id="mwB8A"> </span><span class="n" id="mwB8E">x</span><span class="p" id="mwB8I">)));</span> <span class="w" id="mwB8M"> </span><span class="p" id="mwB8Q">}</span> <span class="p" id="mwB8U">}</span>

A true monad still requires bind, but for Writer, this operation combines the current log with the log produced by applying a transformation:

<span id="mwB8s"></span><span class="kd" id="mwB8w">record</span> <span class="nc" id="mwB80">Writer</span><span class="o" id="mwB84"><</span><span class="n" id="mwB88">T</span><span class="o" id="mwB9A">></span><span class="p" id="mwB9E">(</span><span class="n" id="mwB9I">T</span><span class="w" id="mwB9M"> </span><span class="n" id="mwB9Q">value</span><span class="p" id="mwB9U">,</span><span class="w" id="mwB9Y"> </span><span class="n" id="mwB9c">List</span><span class="o" id="mwB9g"><</span><span class="n" id="mwB9k">String</span><span class="o" id="mwB9o">></span><span class="w" id="mwB9s"> </span><span class="n" id="mwB9w">log</span><span class="p" id="mwB90">)</span><span class="w" id="mwB94"> </span><span class="p" id="mwB98">{</span> <span class="w" id="mwB-A"> </span><span class="c1" id="mwB-E">// ...</span> <span class="w" id="mwB-I"> </span><span class="kd" id="mwB-M">public</span><span class="w" id="mwB-Q"> </span><span class="o" id="mwB-U"><</span><span class="n" id="mwB-Y">U</span><span class="o" id="mwB-c">></span><span class="w" id="mwB-g"> </span><span class="n" id="mwB-k">Writer</span><span class="o" id="mwB-o"><</span><span class="n" id="mwB-s">U</span><span class="o" id="mwB-w">></span><span class="w" id="mwB-0"> </span><span class="nf" id="mwB-4">bind</span><span class="p" id="mwB-8">(</span><span class="n" id="mwB_A">Function</span><span class="o" id="mwB_E"><</span><span class="n" id="mwB_I">T</span><span class="p" id="mwB_M">,</span><span class="w" id="mwB_Q"> </span><span class="n" id="mwB_U">Writer</span><span class="o" id="mwB_Y"><</span><span class="n" id="mwB_c">U</span><span class="o" id="mwB_g">>></span><span class="w" id="mwB_k"> </span><span class="n" id="mwB_o">transform</span><span class="p" id="mwB_s">)</span><span class="w" id="mwB_w"> </span><span class="p" id="mwB_0">{</span> <span class="w" id="mwB_4"> </span><span class="n" id="mwB_8">Writer</span><span class="o" id="mwCAA"><</span><span class="n" id="mwCAE">U</span><span class="o" id="mwCAI">></span><span class="w" id="mwCAM"> </span><span class="n" id="mwCAQ">result</span><span class="w" id="mwCAU"> </span><span class="o" id="mwCAY">=</span><span class="w" id="mwCAc"> </span><span class="n" id="mwCAg">transform</span><span class="p" id="mwCAk">.</span><span class="na" id="mwCAo">apply</span><span class="p" id="mwCAs">(</span><span class="k" id="mwCAw">this</span><span class="p" id="mwCA0">.</span><span class="na" id="mwCA4">value</span><span class="p" id="mwCA8">);</span> <span class="w" id="mwCBA"> </span><span class="n" id="mwCBE">List</span><span class="o" id="mwCBI"><</span><span class="n" id="mwCBM">String</span><span class="o" id="mwCBQ">></span><span class="w" id="mwCBU"> </span><span class="n" id="mwCBY">newLog</span><span class="w" id="mwCBc"> </span><span class="o" id="mwCBg">=</span><span class="w" id="mwCBk"> </span><span class="k" id="mwCBo">new</span><span class="w" id="mwCBs"> </span><span class="n" id="mwCBw">ArrayList</span><span class="o" id="mwCB0"><></span><span class="p" id="mwCB4">(</span><span class="k" id="mwCB8">this</span><span class="p" id="mwCCA">.</span><span class="na" id="mwCCE">log</span><span class="p" id="mwCCI">);</span> <span class="w" id="mwCCM"> </span><span class="n" id="mwCCQ">newLog</span><span class="p" id="mwCCU">.</span><span class="na" id="mwCCY">addAll</span><span class="p" id="mwCCc">(</span><span class="n" id="mwCCg">result</span><span class="p" id="mwCCk">.</span><span class="na" id="mwCCo">log</span><span class="p" id="mwCCs">());</span> <span class="w" id="mwCCw"> </span><span class="k" id="mwCC0">return</span><span class="w" id="mwCC4"> </span><span class="k" id="mwCC8">new</span><span class="w" id="mwCDA"> </span><span class="n" id="mwCDE">Writer</span><span class="o" id="mwCDI"><></span><span class="p" id="mwCDM">(</span><span class="n" id="mwCDQ">result</span><span class="p" id="mwCDU">.</span><span class="na" id="mwCDY">value</span><span class="p" id="mwCDc">(),</span><span class="w" id="mwCDg"> </span><span class="n" id="mwCDk">newLog</span><span class="p" id="mwCDo">);</span> <span class="w" id="mwCDs"> </span><span class="p" id="mwCDw">}</span> <span class="p" id="mwCD0">}</span>

The sample functions can now be chained together using bind, which can be represented using method chaining:

<span id="mwCEM"></span><span class="n" id="mwCEQ">Writer</span><span class="o" id="mwCEU"><</span><span class="n" id="mwCEY">Integer</span><span class="o" id="mwCEc">></span><span class="w" id="mwCEg"> </span><span class="n" id="mwCEk">result</span><span class="w" id="mwCEo"> </span><span class="o" id="mwCEs">=</span><span class="w" id="mwCEw"> </span><span class="n" id="mwCE0">Writer</span><span class="p" id="mwCE4">.</span><span class="na" id="mwCE8">unit</span><span class="p" id="mwCFA">(</span><span class="mi" id="mwCFE">4</span><span class="p" id="mwCFI">)</span> <span class="w" id="mwCFM"> </span><span class="p" id="mwCFQ">.</span><span class="na" id="mwCFU">bind</span><span class="p" id="mwCFY">(</span><span class="n" id="mwCFc">Ops</span><span class="p" id="mwCFg">::</span><span class="n" id="mwCFk">squared</span><span class="p" id="mwCFo">)</span> <span class="w" id="mwCFs"> </span><span class="p" id="mwCFw">.</span><span class="na" id="mwCF0">bind</span><span class="p" id="mwCF4">(</span><span class="n" id="mwCF8">Ops</span><span class="p" id="mwCGA">::</span><span class="n" id="mwCGE">halved</span><span class="p" id="mwCGI">);</span>

The final result is a clean separation of concerns between performing computations and accumulating log output for later inspection:

<span id="mwCGY"></span><span class="n" id="mwCGc">System</span><span class="p" id="mwCGg">.</span><span class="na" id="mwCGk">out</span><span class="p" id="mwCGo">.</span><span class="na" id="mwCGs">println</span><span class="p" id="mwCGw">(</span><span class="n" id="mwCG0">result</span><span class="p" id="mwCG4">.</span><span class="na" id="mwCG8">value</span><span class="p" id="mwCHA">());</span><span class="w" id="mwCHE"> </span><span class="c1" id="mwCHI">// 8</span> <span class="n" id="mwCHM">System</span><span class="p" id="mwCHQ">.</span><span class="na" id="mwCHU">out</span><span class="p" id="mwCHY">.</span><span class="na" id="mwCHc">println</span><span class="p" id="mwCHg">(</span><span class="n" id="mwCHk">result</span><span class="p" id="mwCHo">.</span><span class="na" id="mwCHs">log</span><span class="p" id="mwCHw">());</span><span class="w" id="mwCH0"> </span><span class="c1" id="mwCH4">// [4 was squared., 16 was halved.]</span>

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 T to functions of type E → T, where E is the type of the shared environment. The monad functions are: $${\displaystyle \begin{array}{ll}\text{return}:& T\to E\to T=t\mapsto e\mapsto t\\ \text{bind}:& (E\to T)\to (T\to E\to T^{\prime })\to E\to T^{\prime }=r\mapsto f\mapsto e\mapsto f(re)e\end{array}}$$

The following monadic operations are useful: $${\displaystyle \begin{array}{ll}\text{ask}:& E\to E={\text{id}}_E\\ \text{local}:& (E\to E)\to (E\to T)\to E\to T=f\mapsto c\mapsto e\mapsto c(fe)\end{array}}$$

The ask operation is used to retrieve the current context, while local 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 added, anonymous argument; return and bind are equivalent to the K and S 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.

<span id="mwCJ0"></span><span class="kr" id="mwCJ4">type</span><span class="w" id="mwCJ8"> </span><span class="kt" id="mwCKA">State</span><span class="w" id="mwCKE"> </span><span class="n" id="mwCKI">s</span><span class="w" id="mwCKM"> </span><span class="n" id="mwCKQ">t</span><span class="w" id="mwCKU"> </span><span class="ow" id="mwCKY">=</span><span class="w" id="mwCKc"> </span><span class="n" id="mwCKg">s</span><span class="w" id="mwCKk"> </span><span class="ow" id="mwCKo">-></span><span class="w" id="mwCKs"> </span><span class="p" id="mwCKw">(</span><span class="n" id="mwCK0">t</span><span class="p" id="mwCK4">,</span><span class="w" id="mwCK8"> </span><span class="n" id="mwCLA">s</span><span class="p" id="mwCLE">)</span>

Note that this monad takes a type parameter, the type of the state information. The monad operations are defined as follows:

<span id="mwCLU"></span><span class="c1" id="mwCLY">-- "return" produces the given value without changing the state.</span> <span class="nf" id="mwCLc">return</span><span class="w" id="mwCLg"> </span><span class="n" id="mwCLk">x</span><span class="w" id="mwCLo"> </span><span class="ow" id="mwCLs">=</span><span class="w" id="mwCLw"> </span><span class="nf" id="mwCL0">\</span><span class="n" id="mwCL4">s</span><span class="w" id="mwCL8"> </span><span class="ow" id="mwCMA">-></span><span class="w" id="mwCME"> </span><span class="p" id="mwCMI">(</span><span class="n" id="mwCMM">x</span><span class="p" id="mwCMQ">,</span><span class="w" id="mwCMU"> </span><span class="n" id="mwCMY">s</span><span class="p" id="mwCMc">)</span> <span class="c1" id="mwCMg">-- "bind" modifies m so that it applies f to its result.</span> <span class="nf" id="mwCMk">m</span><span class="w" id="mwCMo"> </span><span class="o" id="mwCMs">>>=</span><span class="w" id="mwCMw"> </span><span class="n" id="mwCM0">f</span><span class="w" id="mwCM4"> </span><span class="ow" id="mwCM8">=</span><span class="w" id="mwCNA"> </span><span class="nf" id="mwCNE">\</span><span class="n" id="mwCNI">r</span><span class="w" id="mwCNM"> </span><span class="ow" id="mwCNQ">-></span><span class="w" id="mwCNU"> </span><span class="kr" id="mwCNY">let</span><span class="w" id="mwCNc"> </span><span class="p" id="mwCNg">(</span><span class="n" id="mwCNk">x</span><span class="p" id="mwCNo">,</span><span class="w" id="mwCNs"> </span><span class="n" id="mwCNw">s</span><span class="p" id="mwCN0">)</span><span class="w" id="mwCN4"> </span><span class="ow" id="mwCN8">=</span><span class="w" id="mwCOA"> </span><span class="n" id="mwCOE">m</span><span class="w" id="mwCOI"> </span><span class="n" id="mwCOM">r</span><span class="w" id="mwCOQ"> </span><span class="kr" id="mwCOU">in</span><span class="w" id="mwCOY"> </span><span class="p" id="mwCOc">(</span><span class="n" id="mwCOg">f</span><span class="w" id="mwCOk"> </span><span class="n" id="mwCOo">x</span><span class="p" id="mwCOs">)</span><span class="w" id="mwCOw"> </span><span class="n" id="mwCO0">s</span>

Useful state operations include:

<span id="mwCPE"></span><span class="nf" id="mwCPI">get</span><span class="w" id="mwCPM"> </span><span class="ow" id="mwCPQ">=</span><span class="w" id="mwCPU"> </span><span class="nf" id="mwCPY">\</span><span class="n" id="mwCPc">s</span><span class="w" id="mwCPg"> </span><span class="ow" id="mwCPk">-></span><span class="w" id="mwCPo"> </span><span class="p" id="mwCPs">(</span><span class="n" id="mwCPw">s</span><span class="p" id="mwCP0">,</span><span class="w" id="mwCP4"> </span><span class="n" id="mwCP8">s</span><span class="p" id="mwCQA">)</span><span class="w" id="mwCQE"> </span><span class="c1" id="mwCQI">-- Examine the state at this point in the computation.</span> <span class="nf" id="mwCQM">put</span><span class="w" id="mwCQQ"> </span><span class="n" id="mwCQU">s</span><span class="w" id="mwCQY"> </span><span class="ow" id="mwCQc">=</span><span class="w" id="mwCQg"> </span><span class="nf" id="mwCQk">\</span><span class="kr" id="mwCQo">_</span><span class="w" id="mwCQs"> </span><span class="ow" id="mwCQw">-></span><span class="w" id="mwCQ0"> </span><span class="p" id="mwCQ4">(</span><span class="nb" id="mwCQ8">()</span><span class="p" id="mwCRA">,</span><span class="w" id="mwCRE"> </span><span class="n" id="mwCRI">s</span><span class="p" id="mwCRM">)</span><span class="w" id="mwCRQ"> </span><span class="c1" id="mwCRU">-- Replace the state.</span> <span class="nf" id="mwCRY">modify</span><span class="w" id="mwCRc"> </span><span class="n" id="mwCRg">f</span><span class="w" id="mwCRk"> </span><span class="ow" id="mwCRo">=</span><span class="w" id="mwCRs"> </span><span class="nf" id="mwCRw">\</span><span class="n" id="mwCR0">s</span><span class="w" id="mwCR4"> </span><span class="ow" id="mwCR8">-></span><span class="w" id="mwCSA"> </span><span class="p" id="mwCSE">(</span><span class="nb" id="mwCSI">()</span><span class="p" id="mwCSM">,</span><span class="w" id="mwCSQ"> </span><span class="n" id="mwCSU">f</span><span class="w" id="mwCSY"> </span><span class="n" id="mwCSc">s</span><span class="p" id="mwCSg">)</span><span class="w" id="mwCSk"> </span><span class="c1" id="mwCSo">-- Update the state</span>

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

<span id="mwCS4"></span><span class="nf" id="mwCS8">runState</span><span class="w" id="mwCTA"> </span><span class="ow" id="mwCTE">::</span><span class="w" id="mwCTI"> </span><span class="kt" id="mwCTM">State</span><span class="w" id="mwCTQ"> </span><span class="n" id="mwCTU">s</span><span class="w" id="mwCTY"> </span><span class="n" id="mwCTc">a</span><span class="w" id="mwCTg"> </span><span class="ow" id="mwCTk">-></span><span class="w" id="mwCTo"> </span><span class="n" id="mwCTs">s</span><span class="w" id="mwCTw"> </span><span class="ow" id="mwCT0">-></span><span class="w" id="mwCT4"> </span><span class="p" id="mwCT8">(</span><span class="n" id="mwCUA">a</span><span class="p" id="mwCUE">,</span><span class="w" id="mwCUI"> </span><span class="n" id="mwCUM">s</span><span class="p" id="mwCUQ">)</span> <span class="nf" id="mwCUU">runState</span><span class="w" id="mwCUY"> </span><span class="n" id="mwCUc">t</span><span class="w" id="mwCUg"> </span><span class="n" id="mwCUk">s</span><span class="w" id="mwCUo"> </span><span class="ow" id="mwCUs">=</span><span class="w" id="mwCUw"> </span><span class="n" id="mwCU0">t</span><span class="w" id="mwCU4"> </span><span class="n" id="mwCU8">s</span>

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

Informally, a state monad of state type S maps the type of return values T into functions of type ${\displaystyle S\to T\times S}$, where S is the underlying state. The return and bind function are:

${\displaystyle \begin{array}{ll}\text{return}:& T\to S\to T\times S=t\mapsto s\mapsto (t,s)\\ \text{bind}:& (S\to T\times S)\to (T\to S\to T^{\prime }\times S)\to S\to T^{\prime }\times S=m\mapsto k\mapsto s\mapsto (kt{s}^{\prime })\text{where}(t,s^{\prime })=ms\end{array}}$.

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 by definition.

Continuation monad

A continuation monad with return type R maps type T into functions of type ${\displaystyle \left(T\to R\right)\to R}$. It is used to model continuation-passing style. The return and bind functions are as follows:

${\displaystyle \begin{array}{ll}\text{return}:& T\to \left(T\to R\right)\to R=t\mapsto f\mapsto ft\\ \text{bind}:& \left(\left(T\to R\right)\to R\right)\to \left(T\to \left(T^{\prime }\to R\right)\to R\right)\to \left(T^{\prime }\to R\right)\to R=c\mapsto f\mapsto k\mapsto c\left(t\mapsto ftk\right)\end{array}}$

The call-with-current-continuation function is defined as follows:

${\displaystyle \text{call/cc}:\left(\left(T\to \left(T^{\prime }\to R\right)\to R\right)\to \left(T\to R\right)\to R\right)\to \left(T\to R\right)\to R=f\mapsto k\mapsto \left(f\left(t\mapsto x\mapsto kt\right)k\right)}$

Program logging

The following code is pseudocode. Suppose we have two functions foo and bar, with types

<span id="mwCXY"></span><span class="nf" id="mwCXc">foo</span><span class="w" id="mwCXg"> </span><span class="kt" id="mwCXk">:</span><span class="w" id="mwCXo"> </span><span class="n" id="mwCXs">int</span><span class="w" id="mwCXw"> </span><span class="ow" id="mwCX0">-></span><span class="w" id="mwCX4"> </span><span class="n" id="mwCX8">int</span> <span class="nf" id="mwCYA">bar</span><span class="w" id="mwCYE"> </span><span class="kt" id="mwCYI">:</span><span class="w" id="mwCYM"> </span><span class="n" id="mwCYQ">int</span><span class="w" id="mwCYU"> </span><span class="ow" id="mwCYY">-></span><span class="w" id="mwCYc"> </span><span class="n" id="mwCYg">int</span>

That is, both functions take in an integer and return another integer. Then we can apply the functions in succession like so:

<span id="mwCYw"></span><span class="nf" id="mwCY0">foo</span><span class="w" id="mwCY4"> </span><span class="p" id="mwCY8">(</span><span class="n" id="mwCZA">bar</span><span class="w" id="mwCZE"> </span><span class="n" id="mwCZI">x</span><span class="p" id="mwCZM">)</span>

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:

<span id="mwCZ0"></span><span class="nf" id="mwCZ4">foo</span><span class="w" id="mwCZ8"> </span><span class="kt" id="mwCaA">:</span><span class="w" id="mwCaE"> </span><span class="n" id="mwCaI">int</span><span class="w" id="mwCaM"> </span><span class="ow" id="mwCaQ">-></span><span class="w" id="mwCaU"> </span><span class="n" id="mwCaY">int</span><span class="w" id="mwCac"> </span><span class="o" id="mwCag">*</span><span class="w" id="mwCak"> </span><span class="n" id="mwCao">string</span> <span class="nf" id="mwCas">bar</span><span class="w" id="mwCaw"> </span><span class="kt" id="mwCa0">:</span><span class="w" id="mwCa4"> </span><span class="n" id="mwCa8">int</span><span class="w" id="mwCbA"> </span><span class="ow" id="mwCbE">-></span><span class="w" id="mwCbI"> </span><span class="n" id="mwCbM">int</span><span class="w" id="mwCbQ"> </span><span class="o" id="mwCbU">*</span><span class="w" id="mwCbY"> </span><span class="n" id="mwCbc">string</span>

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 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:

<span id="mwCcM"></span><span class="nf" id="mwCcQ">bind</span><span class="w" id="mwCcU"> </span><span class="kt" id="mwCcY">:</span><span class="w" id="mwCcc"> </span><span class="n" id="mwCcg">int</span><span class="w" id="mwCck"> </span><span class="o" id="mwCco">*</span><span class="w" id="mwCcs"> </span><span class="n" id="mwCcw">string</span><span class="w" id="mwCc0"> </span><span class="ow" id="mwCc4">-></span><span class="w" id="mwCc8"> </span><span class="p" id="mwCdA">(</span><span class="n" id="mwCdE">int</span><span class="w" id="mwCdI"> </span><span class="ow" id="mwCdM">-></span><span class="w" id="mwCdQ"> </span><span class="n" id="mwCdU">int</span><span class="w" id="mwCdY"> </span><span class="o" id="mwCdc">*</span><span class="w" id="mwCdg"> </span><span class="n" id="mwCdk">string</span><span class="p" id="mwCdo">)</span><span class="w" id="mwCds"> </span><span class="ow" id="mwCdw">-></span><span class="w" id="mwCd0"> </span><span class="n" id="mwCd4">int</span><span class="w" id="mwCd8"> </span><span class="o" id="mwCeA">*</span><span class="w" id="mwCeE"> </span><span class="n" id="mwCeI">string</span>

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:

<span id="mwCeo"></span><span class="nf" id="mwCes">bind</span><span class="w" id="mwCew"> </span><span class="p" id="mwCe0">(</span><span class="n" id="mwCe4">bind</span><span class="w" id="mwCe8"> </span><span class="p" id="mwCfA">(</span><span class="n" id="mwCfE">x</span><span class="p" id="mwCfI">,</span><span class="n" id="mwCfM">s</span><span class="p" id="mwCfQ">)</span><span class="w" id="mwCfU"> </span><span class="n" id="mwCfY">bar</span><span class="p" id="mwCfc">)</span><span class="w" id="mwCfg"> </span><span class="n" id="mwCfk">foo</span>

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:

<span id="mwCgQ"></span><span class="p" id="mwCgU">(</span><span class="o" id="mwCgY">>>=</span><span class="p" id="mwCgc">)</span><span class="w" id="mwCgg"> </span><span class="kt" id="mwCgk">:</span><span class="w" id="mwCgo"> </span><span class="n" id="mwCgs">int</span><span class="w" id="mwCgw"> </span><span class="o" id="mwCg0">*</span><span class="w" id="mwCg4"> </span><span class="n" id="mwCg8">string</span><span class="w" id="mwChA"> </span><span class="ow" id="mwChE">-></span><span class="w" id="mwChI"> </span><span class="p" id="mwChM">(</span><span class="n" id="mwChQ">int</span><span class="w" id="mwChU"> </span><span class="ow" id="mwChY">-></span><span class="w" id="mwChc"> </span><span class="n" id="mwChg">int</span><span class="w" id="mwChk"> </span><span class="o" id="mwCho">*</span><span class="w" id="mwChs"> </span><span class="n" id="mwChw">string</span><span class="p" id="mwCh0">)</span><span class="w" id="mwCh4"> </span><span class="ow" id="mwCh8">-></span><span class="w" id="mwCiA"> </span><span class="n" id="mwCiE">int</span><span class="w" id="mwCiI"> </span><span class="o" id="mwCiM">*</span><span class="w" id="mwCiQ"> </span><span class="n" id="mwCiU">string</span>

So that t >>= f is the same as bind t f.

Then the above example becomes:

<span id="mwCiw"></span><span class="p" id="mwCi0">((</span><span class="n" id="mwCi4">x</span><span class="p" id="mwCi8">,</span><span class="n" id="mwCjA">s</span><span class="p" id="mwCjE">)</span><span class="w" id="mwCjI"> </span><span class="o" id="mwCjM">>>=</span><span class="w" id="mwCjQ"> </span><span class="n" id="mwCjU">bar</span><span class="p" id="mwCjY">)</span><span class="w" id="mwCjc"> </span><span class="o" id="mwCjg">>>=</span><span class="w" id="mwCjk"> </span><span class="n" id="mwCjo">foo</span>

Finally, we define a new function to avoid writing (x, "") every time we wish to create an empty logging message, where "" is the empty string.

<span id="mwCkA"></span><span class="nf" id="mwCkE">return</span><span class="w" id="mwCkI"> </span><span class="kt" id="mwCkM">:</span><span class="w" id="mwCkQ"> </span><span class="n" id="mwCkU">int</span><span class="w" id="mwCkY"> </span><span class="ow" id="mwCkc">-></span><span class="w" id="mwCkg"> </span><span class="n" id="mwCkk">int</span><span class="w" id="mwCko"> </span><span class="o" id="mwCks">*</span><span class="w" id="mwCkw"> </span><span class="n" id="mwCk0">string</span>

Which wraps x in the tuple described above.

The result is a pipeline for logging messages:

<span id="mwClM"></span><span class="p" id="mwClQ">((</span><span class="n" id="mwClU">return</span><span class="w" id="mwClY"> </span><span class="n" id="mwClc">x</span><span class="p" id="mwClg">)</span><span class="w" id="mwClk"> </span><span class="o" id="mwClo">>>=</span><span class="w" id="mwCls"> </span><span class="n" id="mwClw">bar</span><span class="p" id="mwCl0">)</span><span class="w" id="mwCl4"> </span><span class="o" id="mwCl8">>>=</span><span class="w" id="mwCmA"> </span><span class="n" id="mwCmE">foo</span>

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. int * string, bind, and return form a monad.

Additive monads

An additive monad is a monad endowed with an added closed, associative, binary operator mplus and an identity element under mplus, called mzero. The Maybe monad can be considered additive, with Nothing as mzero and a variation on the OR operator as mplus. List is also an additive monad, with the empty list [] acting as mzero and the concatenation operator ++ as mplus.

Intuitively, mzero 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 for bind, returning mzero whenever bound to a monadic function. This property is two-sided, and bind will also return mzero when any value is bound to a monadic zero function.

In category-theoretic terms, an additive monad qualifies once as a monoid over monadic functions with bind (as all monads do), and again over monadic values via mplus.

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 the category of monads, it can represent monadic structure without any specific constraints beyond the monad laws themselves. Just as a free monoid 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 a free monad. The List monad, in contrast, is not a free monad since it brings extra, specific facts about lists (like append) into its definition. One last example is an abstract free monad:

<span id="mwCqM"></span><span class="kr" id="mwCqQ">data</span><span class="w" id="mwCqU"> </span><span class="kt" id="mwCqY">Free</span><span class="w" id="mwCqc"> </span><span class="n" id="mwCqg">f</span><span class="w" id="mwCqk"> </span><span class="n" id="mwCqo">a</span> <span class="w" id="mwCqs"> </span><span class="ow" id="mwCqw">=</span><span class="w" id="mwCq0"> </span><span class="kt" id="mwCq4">Pure</span><span class="w" id="mwCq8"> </span><span class="n" id="mwCrA">a</span> <span class="w" id="mwCrE"> </span><span class="o" id="mwCrI">|</span><span class="w" id="mwCrM"> </span><span class="kt" id="mwCrQ">Free</span><span class="w" id="mwCrU"> </span><span class="p" id="mwCrY">(</span><span class="n" id="mwCrc">f</span><span class="w" id="mwCrg"> </span><span class="p" id="mwCrk">(</span><span class="kt" id="mwCro">Free</span><span class="w" id="mwCrs"> </span><span class="n" id="mwCrw">f</span><span class="w" id="mwCr0"> </span><span class="n" id="mwCr4">a</span><span class="p" id="mwCr8">))</span> <span class="nf" id="mwCsA">unit</span><span class="w" id="mwCsE"> </span><span class="ow" id="mwCsI">::</span><span class="w" id="mwCsM"> </span><span class="n" id="mwCsQ">a</span><span class="w" id="mwCsU"> </span><span class="ow" id="mwCsY">-></span><span class="w" id="mwCsc"> </span><span class="kt" id="mwCsg">Free</span><span class="w" id="mwCsk"> </span><span class="n" id="mwCso">f</span><span class="w" id="mwCss"> </span><span class="n" id="mwCsw">a</span> <span class="nf" id="mwCs0">unit</span><span class="w" id="mwCs4"> </span><span class="n" id="mwCs8">x</span><span class="w" id="mwCtA"> </span><span class="ow" id="mwCtE">=</span><span class="w" id="mwCtI"> </span><span class="kt" id="mwCtM">Pure</span><span class="w" id="mwCtQ"> </span><span class="n" id="mwCtU">x</span> <span class="nf" id="mwCtY">bind</span><span class="w" id="mwCtc"> </span><span class="ow" id="mwCtg">::</span><span class="w" id="mwCtk"> </span><span class="kt" id="mwCto">Functor</span><span class="w" id="mwCts"> </span><span class="n" id="mwCtw">f</span><span class="w" id="mwCt0"> </span><span class="ow" id="mwCt4">=></span><span class="w" id="mwCt8"> </span><span class="kt" id="mwCuA">Free</span><span class="w" id="mwCuE"> </span><span class="n" id="mwCuI">f</span><span class="w" id="mwCuM"> </span><span class="n" id="mwCuQ">a</span><span class="w" id="mwCuU"> </span><span class="ow" id="mwCuY">-></span><span class="w" id="mwCuc"> </span><span class="p" id="mwCug">(</span><span class="n" id="mwCuk">a</span><span class="w" id="mwCuo"> </span><span class="ow" id="mwCus">-></span><span class="w" id="mwCuw"> </span><span class="kt" id="mwCu0">Free</span><span class="w" id="mwCu4"> </span><span class="n" id="mwCu8">f</span><span class="w" id="mwCvA"> </span><span class="n" id="mwCvE">b</span><span class="p" id="mwCvI">)</span><span class="w" id="mwCvM"> </span><span class="ow" id="mwCvQ">-></span><span class="w" id="mwCvU"> </span><span class="kt" id="mwCvY">Free</span><span class="w" id="mwCvc"> </span><span class="n" id="mwCvg">f</span><span class="w" id="mwCvk"> </span><span class="n" id="mwCvo">b</span> <span class="nf" id="mwCvs">bind</span><span class="w" id="mwCvw"> </span><span class="p" id="mwCv0">(</span><span class="kt" id="mwCv4">Pure</span><span class="w" id="mwCv8"> </span><span class="n" id="mwCwA">x</span><span class="p" id="mwCwE">)</span><span class="w" id="mwCwI"> </span><span class="n" id="mwCwM">f</span><span class="w" id="mwCwQ"> </span><span class="ow" id="mwCwU">=</span><span class="w" id="mwCwY"> </span><span class="n" id="mwCwc">f</span><span class="w" id="mwCwg"> </span><span class="n" id="mwCwk">x</span> <span class="nf" id="mwCwo">bind</span><span class="w" id="mwCws"> </span><span class="p" id="mwCww">(</span><span class="kt" id="mwCw0">Free</span><span class="w" id="mwCw4"> </span><span class="n" id="mwCw8">x</span><span class="p" id="mwCxA">)</span><span class="w" id="mwCxE"> </span><span class="n" id="mwCxI">f</span><span class="w" id="mwCxM"> </span><span class="ow" id="mwCxQ">=</span><span class="w" id="mwCxU"> </span><span class="kt" id="mwCxY">Free</span><span class="w" id="mwCxc"> </span><span class="p" id="mwCxg">(</span><span class="n" id="mwCxk">fmap</span><span class="w" id="mwCxo"> </span><span class="p" id="mwCxs">(</span><span class="nf" id="mwCxw">\</span><span class="n" id="mwCx0">y</span><span class="w" id="mwCx4"> </span><span class="ow" id="mwCx8">-></span><span class="w" id="mwCyA"> </span><span class="n" id="mwCyE">bind</span><span class="w" id="mwCyI"> </span><span class="n" id="mwCyM">y</span><span class="w" id="mwCyQ"> </span><span class="n" id="mwCyU">f</span><span class="p" id="mwCyY">)</span><span class="w" id="mwCyc"> </span><span class="n" id="mwCyg">x</span><span class="p" id="mwCyk">)</span>

Free monads, however, are not restricted to a linked-list like in this example, and can be built around other structures like trees.

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 iteratees 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 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 bind-centric monad definition, a comonad consists of:

• A type constructor W that marks the higher-order type W T
• The dual of unit, called counit here, extracts the underlying value from the comonad:

counit(wa) : W T → T

• A reversal of bind (also represented with =>>) that extends a chain of reducing functions:

(wa =>> f) : (W U, W U → T) → W T<sup about="#mwt421" class="mw-ref reference" id="cite_ref-53" rel="dc:references" typeof="mw:Transclusion mw:Extension/ref" data-mw='{"name":"ref","attrs":{"group":"lower-alpha"},"body":{"id":"mw-reference-text-cite_note-53"},"parts":[{"template":{"target":{"wt":"efn","href":"./Template:Efn"},"params":{"1":{"wt":"In Haskell, {{mvar|extend}} is actually defined with the inputs swapped, but as currying is not used in this article, it is defined here as the exact dual of {{mvar|bind}}."}},"i":0}}]}'><a href="./Monad_(functional_programming)#cite_note-53" data-mw-group="lower-alpha" id="mwC00"><span class="mw-reflink-text" id="mwC04"><span class="cite-bracket" id="mwC08">[</span>s<span class="cite-bracket" id="mwC1A">]</span></span></a></sup>

extend and counit must also satisfy duals of the monad laws:

counit ∘ <b id="mwC1U">(</b> (wa =>> f) → wb <b id="mwC1Y">)</b> ↔ f(wa) → b wa =>> counit ↔ wa wa <b id="mwC1c">(</b> (=>> f(wx = wa)) → wb (=>> g(wy = wb)) → wc <b id="mwC1g">)</b> ↔ <b id="mwC1k">(</b> wa (=>> f(wx = wa)) → wb <b id="mwC1o">)</b> (=>> g(wy = wb)) → wc

Analogous to monads, comonads can also be derived from functors using a dual of join:

• 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 extend are reversed, however, a comonad does not reverse functions it acts on, and consequently, comonads are still functors with map, not cofunctors. The alternate definition with duplicate, counit, and map 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. The Product comonad is only 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 streams and attach filters to the incoming signals with extend. While not as popular as monads, researchers have found comonads particularly useful for stream processing and modeling dataflow programming.

Due to their strict definitions, however, one cannot simply move objects back and forth between monads and comonads. As an even higher abstraction, arrows can subsume both structures, but finding more granular ways to combine monadic and comonadic code is an active area of research.