Sat Nov 18 01:12:59 EST 2017

Free Monad

The free monad is all possible nestings derived from a functor.
I.e. the fixed point of a functor.

Compare to lists -- but I did not find this very clarifying.

  data List a   = Nil    | Cons a (List a)

The definition of a Free is similar:

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


Pure a
Roll $ f $ Pure a
Roll $ f $ Roll $ f Pure a

This contains all nested versions of the functor.  E.g. with a product
functor such as pair: f a = {a, a} and leaving out the tags Pure and
Roll, the actual structure is:


"Technically, it is only a tree if your base functor is a product
functor. When you have a sum functor as the base functor it more
closely resembles a stack machine."

The Free Monad (data structure) is to the Monad (class) like the List
(data structure) to the Monoid (class): It is the trivial
implementation, where you can decide afterwards how the content will
be combined.

-> That rings like the other explanation: instead of combing
   computations, it just keeps nesting.

-> Or: You want to use the machinery of a monad for composition, but
   want to determine later on what the meaning of the functions will
   be.  Then foldFree takes return and join.  This is an interpreter.

"Stacking instead of reduction."