So I started reading about Free Monads in Haskell inspired from the Functional Pearl - Data types a la carte (http://www.cs.ru.nl/~W.Swierstra/Publications/DataTypesALaCarte.pdf) by Wouter Swierstra. And possibly after a long time really finding myself into an information overload with a topic in functional programming.

There are quite a few references on Free Monads out there on the Web ..

a. Why free monads matter (http://www.haskellforall.com/2012/06/you-could-have-invented-free-monads.html)

b. What makes the free monad free? (http://www.typesandotherdistractions.com/2010/12/what-makes-free-monad-free.html)

c. Free Monads In Haskell (http://blog.omega-prime.co.uk/?p=34)

and a series by +Edward Kmett on the Comonad.Reader starting with http://comonad.com/reader/2011/free-monads-for-less/.

However I am still struggling to understand what it formally means to be a Free Monad - what's the freedom out there. Well, Swierstra's paper mentions that "In general, a structure is called free when it is left-adjoint to a forgetful functor." .. well what ?

This leads into understanding what it means by a Forgetful Functor and people really have struggled to formalize the definition of a forgetful functor in a way that makes sense to someone not an expert in Category Theory. Someone asking for a formal definition on mathoverflow gets an answer "They are like pornography: you know them when you see them" (http://mathoverflow.net/questions/19405/definition-of-forgetful-functor).

Looks like quite a long way to go for me to understand what's free in a free monad :(

There are quite a few references on Free Monads out there on the Web ..

a. Why free monads matter (http://www.haskellforall.com/2012/06/you-could-have-invented-free-monads.html)

b. What makes the free monad free? (http://www.typesandotherdistractions.com/2010/12/what-makes-free-monad-free.html)

c. Free Monads In Haskell (http://blog.omega-prime.co.uk/?p=34)

and a series by +Edward Kmett on the Comonad.Reader starting with http://comonad.com/reader/2011/free-monads-for-less/.

However I am still struggling to understand what it formally means to be a Free Monad - what's the freedom out there. Well, Swierstra's paper mentions that "In general, a structure is called free when it is left-adjoint to a forgetful functor." .. well what ?

This leads into understanding what it means by a Forgetful Functor and people really have struggled to formalize the definition of a forgetful functor in a way that makes sense to someone not an expert in Category Theory. Someone asking for a formal definition on mathoverflow gets an answer "They are like pornography: you know them when you see them" (http://mathoverflow.net/questions/19405/definition-of-forgetful-functor).

Looks like quite a long way to go for me to understand what's free in a free monad :(

- Great overview.

One thing you may not know is about the dual of free monads: cofree comonads (you can't make these things up :)

http://comonad.com/reader/2008/the-cofree-comonad-and-the-expression-problem/

http://hackage.haskell.org/packages/archive/category-extras/0.2/doc/html/Control-Comonad-Cofree.html

Both free monads and cofree comonads come from free algebras and cofree coalgebras.Jun 29, 2012 - Hi Daniel - I read about the duals as well. What I am seeking for is a clear explanation in simple terms regarding what is
**free**in a free monad. Is there any pointer that explains free structures without the rigor of category theory ? I don't need a formal definition. But say, why Maybe is a free monad while List is not ..Jun 29, 2012 - Edward Kmett+14A free foo happens to be the simplest thing that satisfies all of the 'foo' laws. That is to say it satisfies exactly the laws necessary to be a foo and nothing extra.

A forgetful functor is one that forgets part of the structure as it goes from one category to another.

For example:

Take a monoid, which is defined by some carrier set T, a binary function to mash a pair of elements together :: T → T → T, and a unit :: T, such that you have an associative law, and the f(unit,x) = x = f(x,unit).

You can make a functor U from the category of monoids (where arrows are monoid homomorphisms, that is, they ensure they map unit -> unit on the other monoid, and that you can compose before or after mapping to the other monoid without changing meaning) to the category of sets (where arrows are just function arrows) that 'forgets' about the operation and unit, and just gives you the carrier set.

Then, you can define a functor F from the category of sets back to the category of monoids that is left adjoint to this functor. That functor is the functor that maps a set a to the monoid [a], where unit = [], and mappend = (++).

So to review our example so far

U : Mon → Set -- is our forgetful functor

U (a,mappend,mempty) = a

F : Set → Mon -- is our free functor

F a = [a]

Then to show F is free, need to demonstrate that it is left adjoint to U, a forgetful functor, that is, we need to show that

F a → b is isomorphic to a → U b

now, remember the target of F is in the category Mon of monoids, where arrows are monoid homomorphisms, so we need a to show that a monoid homomorphism from [a] → b can be described precisely by a function from a → b.

In Haskell, we call the side of this that lives in Set (er, Hask, the category of Haskell types that we pretend is Set), just "foldMap", which when specialized from Data.Foldable to Lists has type :: Monoid m => (a → m) → [a] → m.

There are consequences that follow from this being an adjunction. Notably that if you forget then build up with free, then forget again, its just like you forgot once, and we can use this to build up the monadic join. since UFUF ~ U(FUF) ~ UF, and we can pass in the identity monoid homomorphism from [a] to [a] through the isomorphism that defines our adjunction,get that a list isomorphism from [a] → [a] is a function of type a -> [a], and this is just return for lists.

You can compose all of this more directly by describing a list in these terms with:

newtype List a = List (forall b. Monoid b => (a -> b) -> b)

How does this relate to the notion of a free monad as it is usually used? Knowing that something is a free monad, Free f, tells you that giving a monad homomorphism from Free f -> m, is the same thing as giving a natural transformation (a functor homomorphism) from f to m.

In contrast, a cofree functor is simply /right adjoint/ to a forgetful functor, and by symmetry, knowing something is a cofree comonad is the same as knowing that giving a comonad homomorphism from w -> Cofree f is the same thing as giving a natural transformation from w -> f.Jun 29, 2012 - +Debasish Ghosh Actually I've no idea. When I started learning algebra I got the habit to ignore the usual meaning of any words so I never even thought about the meaning of free in free monad.Jun 29, 2012
- Thanks +Edward Kmett for the clear explanation. Now I feel more confident to approach your article on Comonad.Reader.Jun 30, 2012