> Free monads permit unlimited introspection and transformation of the structure of your program; Free monads allow minimal specification of each semantic layer, since performance can be optimized via analysis and transformation.
That is not true and this overselling of the Free monad is hurting the concept.
The Free monad is nothing more than the flatMap/bind operation, specified as a data-structure, much like how a binary-search tree describes binary search. And this means an imposed ordering of operations and loss of information due to computations being suspended by means of functions.
You see, if the statement I'm disagreeing with would be true, then you'd be able to build something like .NET LINQ on top of Free. But you can't.
Maybe this is a bit trite, but isn't the ordering given in Free simply the order of the code? At what stage does loss of information happen.
Yeah, the free monad structures involve lots of lambdas. It's not so much that information is "lost", more that you cannot see beyond the next lambda abstraction.
From a DSL perspective, it's like you can only inspect the program so far as to know the next statement in the "do" block. To see what the next statement will be, you need to actually evaluate the current one.
Instead of free monads, if you want very analyzable structures, look at free applicative functors.
"Applicative functors are a generalisation of monads. Both allow the expression of effectful computations into an otherwise pure language, like Haskell. Applicative functors are to be preferred to monads when the structure of a computation is fixed a priori. That makes it possible to perform certain kinds of static analysis on applicative values. We define a notion of free applicative functor, prove that it satisfies the appropriate laws, and that the construction is left adjoint to a suitable forgetful functor. We show how free applicative functors can be used to implement embedded DSLs which can be statically analysed."
The problem is that applicative functors aren't powerful enough to allow computations that depend on previous results. I suspect what we want is something like free ArrowChoice, but I'm not aware of any work in that direction.
https://byorgey.wordpress.com/2012/01/05/parsing-context-sen...
But yeah.
ApplicativeDo might be useful. You would be able to see the static applicative structure as far as the next monadic bind, which lets you do interesting types of optimization, e.g. Haxl.