# Free Monad A free monad is a technique of constructing a [[Monad]] from a [[Covariant Functor]]. A free monad is a sum type that can be defined as such ```fsharp type Free<Functor<'T>, 'T> = | Pure of 'T | Free of Functor<Free<Functor<'T>, 'T>> ``` `return` is simply `Pure`. A function that lifts `<Functor<T>` into `Free<Functor<T>, T>` can be defined as such: ```fsharp //Functor.map is the functor's map, with signature //map : (a -> b) -> Functor<a> -> Functor<b> //or specifically //map : (T -> Free<Functor<T>, T>) -> Functor<T> -> Functor<Free<Functor<T>, T>> let lift = Functor.map Free.Pure //Functor<T> -> Functor<Free<Functor<T>, T> >> Free //Free<Functor<T>, T> ``` Bind is implemented as ```fsharp //We take bind in this case to have signature //(A -> Free<Functor<B>, B>) -> Free<Functor<A>, A> -> Free<Functor<B>, B> let rec bind (f : 'A -> Free<Functor<'B>, 'B>) (x : Free<Functor<'A>, 'A>) = match x with | Pure (x : 'A) -> f x //Pure case. We already have a value to pass to f | Free (x : Functor<Free<Functor<'A>, 'A>>) -> let loop = bind f //Free<Functor<'A>, 'A> -> Free<Functor<'B>, 'B> //mapped : Functor<Free<Functor<'A>, 'A>> -> Functor<Free<Functor<'B>, 'B>> let mapped = Functor.map loop let next = mapped x //Functor<Free<Functor<'B>, 'B>> Free next ``` For an implementation of the free monad in FSharpPlus see [[FSharpPlus Free]]. The [[Trampoline]] is a free monad whose functor is a function that takes no parameters (`Func<T>`).