Church Encoding

[LSLeary]

I wrote a Church encoding of the higher-order free monad from A Framework for Higher-Order Effects & Handlers. Like Control.Monad.Free.Church, its >>= should be asymptotically faster than the vanilla.

Perhaps heftia can put this to good use?

[ymdfield]

Thanks for sharing the code!

In fact, the early version of heftia did implement Free h a based on a Church encoding¹. At the time, I also believed Church encoding would be faster, but in practice the current encoding using FTCQueue (by freer-simple) ended up being faster. Because of this, I’m not entirely convinced about the performance benefits of the Church encoding approach. The fact that Polysemy, which uses the same Church encoding for a higher order free monad, is not particularly fast either further supports this.

That said, I never made a fair comparison between the two. The architecture changed quite a bit in the meantime (for example, I dropped some of the heavier type class abstractions and increased INLINE usage) so it’s possible that trying Church encoding again now might indeed give better results. (Also, my memory of that time is vague)

I’ve been busy lately with other things and with effect experiments in a separate repository², so I don’t have time to rewrite the code and run benchmarks. For these reasons, unfortunately it will have to remain a low priority. If you are still strongly interested, I would welcome it if you could take on the benchmarking work.

Footnotes

1. https://github.com/sayo-hs/heftia/blob/v0.3.1/heftia/src/Control/Monad/Freer/Church.hs ↩

2. https://github.com/sayo-hs/eff-research ↩