Asymptotic Improvement of Computations over Free Monads

Author: J. Voigtländer
Published: In 9th International Conference on Mathematics of Program Construction (MPC'08, acceptance rate 18/41), Marseille, France, Proceedings, volume 5133 of LNCS, pages 388-403, Springer, July 2008.
DOI: 10.1007/978-3-540-70594-9_20
BibTeX: Voi08d.bib
Abstract: We present a low-effort program transformation to improve the efficiency of computations over free monads in Haskell. The development is calculational and carried out in a generic setting, thus applying to a variety of datatypes. An important aspect of our approach is the utilisation of type class mechanisms to make the transformation as transparent as possible, requiring no restructuring of code at all. There is also no extra support necessary from the compiler (apart from an up-to-date type checker). Despite this simplicity of use, our technique is able to achieve true asymptotic runtime improvements. We demonstrate this by examples for which the complexity is reduced from quadratic to linear.
Download: AsymptoticImprovementOfComputationsOverFreeMonads.pdf
Rights: Copyright held by Springer.
Slides: Slides of my talk at the conference are here.