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)
Swierstra, Wouter. 2008. ‘Data Types à La Carte’. Journal of Functional Programming 18 (04). https://doi.org/10.1017/S0956796808006758.
@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}
}