Free monads

A free monad is a monad that is free.

Unrolling the facetiousness, given an endofunctor, its associated free monad is the 'least' data type that is based on that endofunctor, and also supports the monad operations.

In many functional programming languages the free monad can be given as an algebraic data type. In Haskell, suppose we are given a type constructor f :: * -> *. Moreover, suppose that f is a functor. Then, the free monad is given by the declaration

data Free f a = Pure a | Bind (f (Free f a))

This is clearly a monad, as the monadic operations can be interpreted syntactically:

instance (Functor f) => Monad (Free f a) where
  return :: a -> Free f a
  return x = Return x
  
  (>>=) :: Free f a -> (a -> Free f b) -> Free f b
  (Return x) >>= f = f x
  (Bind k)   >>= f = Bind (fmap (>>= f) k)

References

• Free monads play an important role in the 'data types à la carte' style, which is a popular solution to the expression problem first described by Wouter Swierstra in

@article{swierstra_data_2008,
	title = {Data types \'{a} la carte},
	volume = {18},
	doi = {10.1017/S0956796808006758},
	number = {04},
	journal = {Journal of Functional Programming},
	author = {Swierstra, Wouter},
	year = {2008}
}

• There are far too many blog posts about free monads online. You are welcome to search for some of them.