Editing Monad (functional programming) (section)

=== 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" />