Thu 23 Jun 2011

## Free Monads for Less (Part 1 of 3): Codensity

Posted by Edward Kmett under Algorithms , Category Theory , Data Structures , Haskell , Kan Extensions , Monads[9] Comments

A couple of years back Janis Voigtländer wrote a nice paper on how one can use the codensity monad to improve the asymptotic complexity of algorithms using the free monads. He didn't use the name Codensity in the paper, but this is essentially the meaning of his type `C`

.

I just returned from running a workshop on domain-specific languages at McMaster University with the more than able assistance of Wren Ng Thornton. Among the many topics covered, I spent a lot of time talking about how to use free monads to build up term languages for various DSLs with simple evaluators, and then made them efficient by using `Codensity`

.

This has been shown to be a sufficient tool for this task, but is it necessary?