AplicativeDo solves this a little bit through using Applicative until the results are necessary for the next instruction, then opting for Monad instances
Right, but at that point you're no longer Free. (Unless you declare the inefficient implementation and the efficient implementation to be equivalent, but if you do that then every refactor risks destroying your performance).