Abstract
In functional programming one usually writes programs as the composition of simpler functions. Consequently, the result of a function might be generated only to be consumed immediately by another function. This potential source of inefficiency can often be eliminated using a technique called shortcut fusion, which fuses both functions involved in a composition to yield a monolithic one. In this article we investigate how to apply shortcut fusion to applicative computations. Applicative functors provide a model of computational effects which generalise monads, but they favour an applicative programming style. To the best of our knowledge, this is the first time shortcut fusion is considered in an applicative setting.
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
Abramsky, S., Jung, A.: Domain Theory. In: Abramsky, S., Gabbay, D., Maibaum, T.S.E. (eds.) Handbook of Logic in Computer Science, vol. 3, pp. 1–168. Oxford University Press (1994)
Backhouse, R., Jansson, P., Jeuring, J., Meertens, L.: Generic Programming — An Introduction. In: Swierstra, S.D., Oliveira, J.N. (eds.) AFP 1998. LNCS, vol. 1608, pp. 28–115. Springer, Heidelberg (1999)
Bird, R., de Moor, O.: Algebra of programming. Prentice-Hall, Inc., Upper Saddle River (1997)
Bird, R.S.: Introduction to Functional Programming Using Haskell. Prentice-Hall (1998)
Fernandes, J.P., Pardo, A., Saraiva, J.: A shortcut fusion rule for circular program calculation. In: Keller, G. (ed.) Haskell, pp. 95–106. ACM (2007)
Ghani, N., Johann, P.: Monadic augment and generalised short cut fusion. Journal of Functional Programming 17(6), 731–776 (2007)
Ghani, N., Johann, P.: Short cut fusion of recursive programs with computational effects. In: Achten, P., Koopman, P., Morazán, M. (eds.) Trends in Functional Programming. Trends in Functional Programming, Intellect, vol. 9, pp. 113–128 (2009) ISBN 978-1-84150-277-9
Ghani, N., Uustalu, T., Vene, V.: Build, Augment and Destroy, Universally. In: Chin, W.-N. (ed.) APLAS 2004. LNCS, vol. 3302, pp. 327–347. Springer, Heidelberg (2004)
Gibbons, J.: Datatype-Generic Programming. In: Backhouse, R., Gibbons, J., Hinze, R., Jeuring, J. (eds.) SSDGP 2006. LNCS, vol. 4719, pp. 1–71. Springer, Heidelberg (2007)
Gibbons, J., Oliveira, B.C.d.S.: The essence of the iterator pattern. Journal of Functional Programming 19(3-4), 377–402 (2009)
Gill, A., Launchbury, J., Peyton Jones, S.: A short cut to deforestation. In: FPCA 1993: Proceedings of the Conference on Functional Programming Languages and Computer Architecture, pp. 223–232. ACM Press, New York (1993)
Hughes, J.: Why functional programming matters. Comput. J. 32(2), 98–107 (1989)
Johann, P., Ghani, N.: Monadic fold, monadic build, monadic short cut fusion. In: Proceedings of the 10th Symposium on Trends in Functional Programming (TFP 2009), pp. 9–23 (2009)
Manzino, C., Pardo, A.: Shortcut fusion of monadic programs. Journal of Universal Computer Science 14(21), 3431–3446 (2008)
Martínez, M., Pardo, A.: A shortcut fusion approach to accumulations. In: Simpósio Brasileiro de Linguagens de Programacao, SBLP 2009 (2009)
McBride, C., Paterson, R.: Applicative programming with effects. Journal of Functional Programming 18(01), 1–13 (2008)
Meertens, L.: Functor pulling. In: Backhouse, R., Sheard, T. (eds.) Proc. Workshop on Generic Programming (1998)
Meijer, E., Fokkinga, M.M., Paterson, R.: Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire. In: Hughes, J. (ed.) FPCA 1991. LNCS, vol. 523, pp. 124–144. Springer, Heidelberg (1991)
Pardo, A., Fernandes, J.P., Saraiva, J.: Shortcut fusion rules for the derivation of circular and higher-order monadic programs. In: Puebla, G., Vidal, G. (eds.) PEPM, pp. 81–90. ACM (2009)
Takano, A., Meijer, E.: Shortcut deforestation in calculational form. In: Proc. Conference on Functional Programming Languages and Computer Architecture, pp. 306–313. ACM Press (1995)
Wadler, P.: Theorems for Free! In: Proceedings of the 4th ACM Conference on Functional Programming Languages and Computer Architecture, FPCA 1989, pp. 347–359. ACM Press, New York (1989)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Delbianco, G.A., Jaskelioff, M., Pardo, A. (2012). Applicative Shortcut Fusion. In: Peña, R., Page, R. (eds) Trends in Functional Programming. TFP 2011. Lecture Notes in Computer Science, vol 7193. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-32037-8_12
Download citation
DOI: https://doi.org/10.1007/978-3-642-32037-8_12
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-32036-1
Online ISBN: 978-3-642-32037-8
eBook Packages: Computer ScienceComputer Science (R0)