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.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Moggi, E.: Notions of computation and monads. Information and Computation 93(1), 55–92 (1991)
Peyton Jones, S., Wadler, P.: Imperative functional programming. In: Principles of Programming Languages, Proceedings, pp. 71–84. ACM Press, New York (1993)
Launchbury, J., Peyton Jones, S.: State in Haskell. Lisp and Symbolic Computation 8(4), 293–341 (1995)
Wadler, P.: The essence of functional programming. In: Principles of Programming Languages, Proceedings, pp. 1–14. ACM Press, New York (1992) (invited talk)
Liang, S., Hudak, P., Jones, M.: Monad transformers and modular interpreters. In: Principles of Programming Languages, Proceedings, pp. 333–343. ACM Press, New York (1995)
Hughes, R.: A novel representation of lists and its application to the function “reverse”. Information Processing Letters 22(3), 141–144 (1986)
Jones, M.: Functional programming with overloading and higher-order polymorphism. In: Jeuring, J., Meijer, E. (eds.) AFP 1995. LNCS, vol. 925, pp. 97–136. Springer, Heidelberg (1995)
Sheard, T., Pasalic, E.: Two-level types and parameterized modules. Journal of Functional Programming 14(5), 547–587 (2004)
Reynolds, J.: Types, abstraction and parametric polymorphism. In: Information Processing, Proceedings, pp. 513–523. Elsevier, Amsterdam (1983)
Wadler, P.: Theorems for free! In: Functional Programming Languages and Computer Architecture, Proceedings, pp. 347–359. ACM Press, New York (1989)
Swierstra, W., Altenkirch, T.: Beauty in the beast — A functional semantics for the awkward squad. In: Haskell Workshop, Proceedings, pp. 25–36. ACM Press, New York (2007)
Claessen, K., Hughes, R.: QuickCheck: A lightweight tool for random testing of Haskell programs. In: International Conference on Functional Programming, Proceedings, pp. 268–279. ACM Press, New York (2000)
Swierstra, W.: Data types à la carte. Journal of Functional Programming (to appear)
Swierstra, W., Altenkirch, T.: Dependent types for distributed arrays. In: Trends in Functional Programming, Draft Proceedings (2008)
Ghani, N., Johann, P., Uustalu, T., Vene, V.: Monadic augment and generalised short cut fusion. In: International Conference on Functional Programming, Proceedings, pp. 294–305. ACM Press, New York (2005)
Ghani, N., Johann, P.: Monadic augment and generalised short cut fusion. Journal of Functional Programming 17(6), 731–776 (2007)
Gill, A.: Cheap Deforestation for Non-strict Functional Languages. PhD thesis, University of Glasgow (1996)
Johann, P.: A generalization of short-cut fusion and its correctness proof. Higher-Order and Symbolic Computation 15(4), 273–300 (2002)
Chitil, O.: Type-Inference Based Deforestation of Functional Programs. PhD thesis, RWTH Aachen (2000)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Voigtländer, J. (2008). Asymptotic Improvement of Computations over Free Monads. In: Audebaud, P., Paulin-Mohring, C. (eds) Mathematics of Program Construction. MPC 2008. Lecture Notes in Computer Science, vol 5133. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-70594-9_20
Download citation
DOI: https://doi.org/10.1007/978-3-540-70594-9_20
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-70593-2
Online ISBN: 978-3-540-70594-9
eBook Packages: Computer ScienceComputer Science (R0)