Editing Monad (functional programming) (section)

== 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]].

=== Verifying the monad laws ===
Returning to the <code>Maybe</code> 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 <code>Maybe</code> 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:''' <!--@ col 8 --> ma >>= eta(x)          <!--@ col 32      --> ⇔  ma
 
        <!--@ col 8    --> '''if''' ma '''is''' (Just a) '''then'''
            <!--@ col 12      --> eta(a)             <!--@ col 32      --> ⇔ Just a
        <!--@ col 8    --> '''else'''                    <!--@ col 36-->    '''or'''
            <!--@ col 12      --> Nothing            <!--@ col 32      --> ⇔ Nothing
        <!--@ col 8    --> '''end if'''

 '''Law 3:''' <!--@ col 8 --> '''('''ma >>= f(x)''')''' >>= g(y)           <!--@ col 52          -->            ⇔  ma >>= '''('''f(x) >>= g(y)''')'''
 
        <!--@ col 8       --> '''if''' (ma >>= f(x)) '''is''' (Just b) '''then'''  <!--@ col 52 -->             '''if''' ma '''is''' (Just a) '''then'''
            <!--@ col 12         --> g(ma >>= f(x))                          <!--@ col 56                   -->      (f(x) >>= g(y)) a
        <!--@ col 8       --> '''else'''                                   <!--@ col 52             -->         '''else'''
            <!--@ col 12         --> Nothing                                   <!--@ col 56                   -->      Nothing
        <!--@ col 8       --> '''end if'''                                 <!--@ col 52             -->         '''end if'''
 
                <!--@ col 16            --> ⇔  '''if''' ma '''is''' (Just a) '''and''' f(a) '''is''' (Just b) '''then'''      
                    <!--@ col 20               -->    (g ∘ f) a
                <!--@ col 16            -->    '''else if''' ma '''is''' (Just a) '''and''' f(a) '''is Nothing then'''
                    <!--@ col 20               -->    Nothing
                <!--@ col 16            -->    '''else'''
                    <!--@ col 20               -->    Nothing
                <!--@ col 16            -->    '''end if'''

=== Derivation from functors <span id="map"></span><span id="join"></span> ===
Though rarer in computer science, one can use category theory directly, which defines a monad as a [[functor]] with two additional [[natural transformation]]s.{{efn|name= kleisli|1= These natural transformations are usually denoted as morphisms η, μ. That is:  η, μ denote ''unit'', and ''join'' respectively. }}
So to begin, a structure requires a [[higher-order function]] (or "functional") named '''[[map (higher-order function)|map]]''' to qualify as a functor:
{{block indent|<code>map : (a → b) → (ma → mb)</code>}}
This is not always a major issue, however, especially when a monad is derived from a pre-existing functor, whereupon the monad inherits {{mvar|map}} automatically. (For historical reasons, this <code>map</code> is instead called <code>fmap</code> in Haskell.)

A monad's first transformation is actually the same {{mvar|unit}} from the Kleisli triple, but following the hierarchy of structures closely, it turns out {{mvar|unit}} characterizes an [[applicative functor]], an intermediate structure between a monad and a basic functor. In the applicative context, {{mvar|unit}} is sometimes referred to as '''pure''' but is still the same function. What does differ in this construction is the law {{mvar|unit}} must satisfy; as {{mvar|bind}} is not defined, the constraint is given in terms of {{mvar|map}} instead:
{{block indent|<code>(unit ∘ φ) x ↔ ((map φ) ∘ unit) x ↔ x</code><ref name="Applicative">{{cite web | title = Applicative functor | url = https://wiki.haskell.org/Applicative_functor | date = 7 May 2018 | website = HaskellWiki | publisher = Haskell.org | archive-url = https://web.archive.org/web/20181030090822/https://wiki.haskell.org/Applicative_functor | archive-date = 30 October 2018 | url-status = live | access-date = 20 November 2018}}</ref>}}

{{anchor|muIsJoin}}
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 {{mvar|μ}}), which "flattens" nested applications of the monad:
{{block indent|<code>join(mma) : M (M T) → M T</code>}}

As the characteristic function, {{mvar|join}} must also satisfy three variations on the monad laws:

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

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:
{{block indent|1=<code>(map φ) ma  ↔ ma >>= (unit ∘ φ)</code>}}
{{block indent|1=<code>join(mma)   ↔ mma >>= id</code>}}
{{block indent|1=<code>ma >>= f ↔ (join ∘ (map f)) ma</code><ref name="MonadContainers">{{cite web | last = Gibbard | first = Cale | title = Monads as containers | url = https://wiki.haskell.org/Monads_as_containers | date = 30 December 2011 | website = HaskellWiki | publisher = Haskell.org | archive-url = https://web.archive.org/web/20171214235146/https://wiki.haskell.org/Monads_as_containers | archive-date = 14 December 2017 | url-status = live | access-date = 20 November 2018}}</ref>}}

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

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

The '''List monad''' naturally demonstrates how deriving a monad from a simpler functor can come in handy.
In many languages, a list structure comes pre-defined along with some basic features, so a <code>List</code> type constructor and {{mvar|[[append]]}} operator (represented with <code>++</code> for infix notation) are assumed as already given here.

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 {{mvar|bind}} and converting lists to a full monad.
The difficulty with this approach is that {{mvar|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 {{mvar|map}}, is straightforward:
 (map φ) xlist  =  [ φ(x1), φ(x2), ..., φ(xn) ]

Now, these two procedures already promote <code>List</code> to an applicative functor.
To fully qualify as a monad, only a correct notion of {{mvar|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.
{{mvar|bind}} can now also be derived with just a formula, then used to feed <code>List</code> values through a pipeline of monadic functions:
[[File:Multivalued functions with List monad.svg|thumb|upright=1.4|right|The <code>List</code> monad can greatly simplify the use of multivalued functions, such as complex roots.<ref name="MultivalueEx">{{cite web | last = Piponi | first = Dan | title = You Could Have Invented Monads! (And Maybe You Already Have.) | url = http://blog.sigfpe.com/2006/08/you-could-have-invented-monads-and.html | date = 7 August 2006 | website = A Neighborhood of Infinity | archiveurl = https://web.archive.org/web/20181024193429/http://blog.sigfpe.com/2006/08/you-could-have-invented-monads-and.html | archivedate = 24 October 2018 | url-status = live | accessdate = 16 October 2018}}</ref>]]
 (xlist >>= f)  =  join ∘ (map f) xlist

One application for this monadic list is representing [[nondeterministic algorithm|nondeterministic computation]].
<code>List</code> can hold results for all execution paths in an algorithm, then condense itself at each step to "forget" which paths led to which results (a sometimes important distinction from deterministic, exhaustive algorithms).{{citation needed|date=March 2021}}
Another benefit is that checks can be embedded in the monad; specific paths can be pruned transparently at their first point of failure, with no need to rewrite functions in the pipeline.<ref name="MonadContainers" />

A second situation where <code>List</code> shines is composing [[multivalued function]]s.
For instance, the {{mvar|n}}th [[Nth root#Complex roots|complex root]] of a number should yield {{mvar|n}} distinct complex numbers, but if another {{mvar|m}}th root is then taken of those results, the final {{mvar|m•n}} values should be identical to the output of the {{mvar|m•n}}th root.
<code>List</code> completely automates this issue away, condensing the results from each step into a flat, mathematically correct list.<ref name="MultivalueEx" />