Fusion!

[bfrk]

Nicolas Wu and Tom Schrijvers have explained how to completely fuse away the intermediate syntax trees, leading to extremely efficient code. Have you considered implementing that?

[edofic]

Did not know about the paper, so thanks for the link. I'll read it and then see what I can do.

[bfrk]

I found that the paper doesn't make much sense unless one already has at least a rudimentary understanding of fold/build fusion (a.k.a. shortcut fusion) in general. In case you have similar difficulties, I just found this nice and friendly introduction.

[bfrk]

BTW I just issued a pull request for the freemonad-benchmark demonstrating that state effect with a free monad is not necessarily 300 times slower than MTL.State (only twice ;-). The funny thing is that the TermMonad class from the paper was already in the project (as class MonadFree); it is used as the generic API for all the free monad implementations. It took me a while to actually attain the huge efficiency gains, though. The crucial trick is to type specialize the stateful computation, while still enforcing that it uses only the API given by TermMonad/MonadFree. In the freemonad-benchmark code, the MTL computation was specialized, but not any of the free monad implementations. You might be interested to take a look at the code in Fused.hs where I implementated the fused free monad a la Wu & Schrijvers. Getting the ideas in the paper to work in practice wasn't easy. I learned one important thing that was not pointed out explicitly (enough) in the paper: The fused free monad no longer contains nor even mentions the Free data type! In the end, the syntax tree (Free f a) completely disappears; the concrete monad in which the computation is expressed (and which is also used as intermediate data type between handlers) is now 'Codensity H' where H is the carrier functor, that is, the functor which describes the result of an effect after handling it.