Free Monad + Interpreter Pattern
May 31, 2015 ยท View on GitHub
It's like creating the front end and back end of a compiler inside Haskell without the need of Template Haskell!
Write your DSL AST as a Free Monad, and then interpret the monad any way you like.
The advantage is that you get to swap out your interpreter, and your main code remains pure.
A prerequisite to understanding this, is understanding how monads are monoids in the monoidal category of endofunctors:
- http://stackoverflow.com/a/3870310/582917
- http://blog.sigfpe.com/2008/11/from-monoids-to-monads.html
- http://www.fceia.unr.edu.ar/~mauro/pubs/Notions_of_Computation_as_Monoids.pdf
More to come (ideas are still floating in my head).
- https://wiki.haskell.org/Free_monad
- https://wiki.haskell.org/Free_structure
- http://en.wikipedia.org/wiki/Free_object#Free_functor
- http://en.wikipedia.org/wiki/Algebraic_structure
- http://ncatlab.org/nlab/show/forgetful+functor
- http://ncatlab.org/nlab/show/free+functor
- http://en.wikipedia.org/wiki/Adjoint_functors (F -| U)
- http://ncatlab.org/nlab/show/stuff%2C+structure%2C+property
- https://stackoverflow.com/questions/13352205/what-are-free-monads
- http://www.haskellforall.com/2012/06/you-could-have-invented-free-monads.html
- https://www.fpcomplete.com/user/dolio/many-roads-to-free-monads
- http://www.stephendiehl.com/posts/monads.html
Ideas:
- Free is left adjoint to Forgetful
- Free adds structure.
- Forgetful forgets structure.
- A free object is an object the minimum amount of laws/properties to make it a specific type of object.
- A list is a free monoid.
- Free objects are constructed from the Free functor.
- Left adjoint is considered a weak inverse.
- An adjunction is a pair of functors Free and Forgetful.
- Monoid -> Set is Forgetful, while Set -> Monoid is Free. The functor acts like a generator. The Free functor adds just enough properties to a set so that it becomes a monoid!
- A free monad, is a specific type of free object. It has been constructed from a Free functor. But from what? Well from some underlying object in some other category. For example an DSL AST!
- There's a universal property (construction?) when there's an adjunction. It's just a law that must be true.
- Algebraic structures are just some set(s) with some operations. Structure is then synonymous with operations.