Asymptotic Improvement of Computations over Free Monads Export

@inproceedings{Voi08d, 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.}, author = {Voigtl\"{a}nder, Janis}, booktitle = {Mathematics of Program Construction, Proceedings}, citeulike-article-id = {3048724}, citeulike-linkout-0 = {http://portal.acm.org/citation.cfm?id=1428237.1428257}, citeulike-linkout-1 = {http://dx.doi.org/10.1007/978-3-540-70594-9_20}, citeulike-linkout-2 = {http://wwwtcs.inf.tu-dresden.de/~voigt/mpc08.pdf}, doi = {10.1007/978-3-540-70594-9_20}, editor = {Paulin-Mohring, Christine and Audebaud, Philippe}, journal = {Mathematics of Program Construction}, keywords = {continuations, deforestation, functional-programming, generic-programming, haskell, monads, optimization, polymorphism, program-transformation, rank-2, type-classes, types}, month = {July}, pages = {388--403}, posted-at = {2008-07-28 10:23:57}, priority = {0}, publisher = {Springer-Verlag}, series = {LNCS}, title = {Asymptotic Improvement of Computations over Free Monads}, url = {http://dx.doi.org/10.1007/978-3-540-70594-9_20}, volume = {5133}, year = {2008} }

TY - CONF ID - Voi08d L3 - citeulike-article-id:3048724 N2 - 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. JF - Mathematics of Program Construction SE - LNCS EP - 403 TI - Asymptotic Improvement of Computations over Free Monads PB - Springer-Verlag VL - 5133 T2 - Mathematics of Program Construction, Proceedings SP - 388 KW - continuations KW - deforestation KW - functional-programming KW - generic-programming KW - haskell KW - monads KW - optimization KW - polymorphism KW - program-transformation KW - rank-2 KW - type-classes KW - types AU - Voigtländer, Janis A2 - Paulin-Mohring, Christine A2 - Audebaud, Philippe PY - 2008/07// UR - http://dx.doi.org/10.1007/978-3-540-70594-9_20 ER -