| 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. |