Editing Monad (functional programming) (section)

=== 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 <code>Just</code> and <code>Nothing</code> markers, the <code>Maybe</code> monad is in fact a free monad.
The <code>List</code> monad, on the other hand, is not a free monad since it brings extra, specific facts about lists (like {{mvar|append}}) into its definition.
One last example is an abstract free monad:
<syntaxhighlight lang="haskell">
data Free f a
  = Pure a
  | Free (f (Free f a))

unit :: a -> Free f a
unit x = Pure x

bind :: Functor f => Free f a -> (a -> Free f b) -> Free f b
bind (Pure x) f = f x
bind (Free x) f = Free (fmap (\y -> bind y f) x)
</syntaxhighlight>
Free monads, however, are ''not'' restricted to a linked-list like in this example, and can be built around other structures like [[tree (data structure)|tree]]s.

Using free monads intentionally may seem impractical at first, but their formal nature is particularly well-suited for syntactic problems.
A free monad can be used to track syntax and type while leaving semantics for later, and has found use in parsers and [[interpreter (computing)|interpreter]]s as a result.<ref name="Swierstra2008">{{cite journal |last=Swierstra |first=Wouter |year=2008 |title=Data types à la carte |url=https://www.cs.ru.nl/~W.Swierstra/Publications/DataTypesALaCarte.pdf |department=Functional Pearl |journal=Journal of Functional Programming |publisher=Cambridge University Press |volume=18 |issue=4 |pages=423–436 |citeseerx=10.1.1.101.4131 |doi=10.1017/s0956796808006758 |doi-broken-date=1 November 2024 |issn=1469-7653 |s2cid=21038598}}</ref>
Others have applied them to more dynamic, operational problems too, such as providing [[iteratee]]s within a language.<ref name="Kiselyov2012">{{cite conference |last=Kiselyov |first=Oleg |date=May 2012 |editor1-last=Schrijvers |editor1-first=Tom |editor2-last=Thiemann |editor2-first=Peter |title=Iteratees |url=http://okmij.org/ftp/Haskell/Iteratee/describe.pdf |conference=International Symposium on Functional and Logic Programming |series=Lecture Notes in Computer Science |location=Kobe, Japan |publisher=Springer-Verlag |volume=7294 |pages=166–181 |doi=10.1007/978-3-642-29822-6_15 |isbn=978-3-642-29822-6}}</ref>