Article

Theory and practice of fusion

Authors:

Daniel W. H. JamesAuthors Info & Claims

IFL'10: Proceedings of the 22nd international conference on Implementation and application of functional languages

Pages 19 - 37

Published: 01 September 2010 Publication History

Abstract

There are a number of approaches for eliminating intermediate data structures in functional programs--this elimination is commonly known as fusion. Existing fusion strategies are built upon various, but related, recursion schemes, such as folds and unfolds. We use the concept of recursive coalgebras as a unifying theoretical and notational framework to explore the foundations of these fusion techniques. We first introduce the calculational properties of recursive coalgebras and demonstrate their use with proofs and derivations in a calculational style, then provide an overview of fusion techniques by bringing them together in this setting. We also showcase these developments with examples in Haskell.

References

[1]

Capretta, V.: General recursion via coinductive types. Logical Methods in Computer Science 1(2), 1-28 (2005).

[2]

Capretta, V., Uustalu, T., Vene, V.: Recursive coalgebras from comonads. Information and Computation 204(4), 437-468 (2006).

Digital Library

[3]

Chin, W.N.: Safe Fusion of Functional Expressions. In: LISP and functional programming, pp. 11-20 (1992).

Digital Library

[4]

Church, A.: The calculi of lambda-conversion. Annals of Mathematics Studies, vol. 6. Princeton University Press, Princeton (1941).

[5]

Coutts, D., Leshchinskiy, R., Stewart, D.: Stream Fusion: From Lists to Streams to Nothing At All. In: ICFP 2007, pp. 315-326 (2007).

Digital Library

[6]

Fegaras, L., Sheard, T., Zhou, T.: Improving Programs which Recurse over Multiple Inductive Structures. In: PEPM 1994 (June 1994).

[7]

Fokkinga, M.M., Meijer, E.: Program calculation properties of continuous algebras. Technical Report CS-R9104. CWI, Amsterdam (January 1991).

[8]

Freyd, P.J.: Remarks on algebraically compact categories. In: Fourman, M.P., Johnstone, P.T., Pitts, A.M. (eds.) Applications of Categories in Computer Science. LMS Lecture Note Series, vol. 177, pp. 95-106. Cambridge University Press, Cambridge (1992).

[9]

Gill, A., Launchbury, J., Peyton Jones, S.L.: A Short Cut to Deforestation. Functional programming languages and computer architecture, 223-232 (1993).

Digital Library

[10]

Hinze, R., Harper, T., James, D.W.H.: Theory and Practice of Fusion. Tech. Rep. CS-RR-11-01. Oxford University Computing Laboratory (2011).

[11]

Hu, Z., Iwasaki, H., Takeichi, M.: An Extension of The Acid Rain Theorem. Functional and Logic Programming, 91-105 (1996).

[12]

Johann, P., Ghani, N.: Initial algebra semantics is enough! In: Della Rocca, S.R. (ed.) TLCA 2007. LNCS, vol. 4583, pp. 207-222. Springer, Heidelberg (2007).

Digital Library

[13]

Lambek, J.: A fixpoint theorem for complete categories. Math. Zeitschr. 103, 151- 161 (1968).

[14]

Mac Lane, S.: Categories for the Working Mathematician, 2nd edn. Graduate Texts in Mathematics. Springer, Berlin (1998).

[15]

Meijer, E., Fokkinga, 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).

Digital Library

[16]

Reynolds, J.C.: Types, abstraction and parametric polymorphism. In: Mason, R.E.A. (ed.) Information Processing 1983, pp. 513-523. North-Holland, Amsterdam (1983).

[17]

Sheard, T., Fegaras, L.: A Fold for All Seasons. Functional programming languages and computer architecture, 233-242 (1993).

Digital Library

[18]

Svenningsson, J.: Shortcut fusion for Accumulating Parameters & Zip-like Functions. In: ICFP 2002, pp. 124-132 (2002).

Digital Library

[19]

Takano, A., Meijer, E.: Shortcut deforestation in calculational form. Functional programming languages and computer architecture, 306-313 (1995).

Digital Library

[20]

Voigtländer, J.: Proving correctness via free theorems: the case of the destroy/- build-rule. Partial Eval. and Semantics-Based Prog. Manip. 13-20 (2008).

Digital Library

[21]

Wadler, P.: Theorems for free! In: FPCA, pp. 347-359 (1989).

Digital Library

[22]

Wadler, P.: Deforestation: transforming programs to eliminate trees. Theoretical Computer Science 73(2), 231-248 (1990).

Digital Library

[23]

Wang, M., Gibbons, J., Matsuda, K., Hu, Z.: Gradual refinement: Blending pattern matching with data abstraction. In: Bolduc, C., Desharnais, J., Ktari, B. (eds.) MPC 2010. LNCS, vol. 6120, pp. 397-425. Springer, Heidelberg (2010).

Digital Library

Cited By

Jonnalagedda MStucki SHaller PMiller H(2015)Fold-based fusion as a library: a generative programming pearlProceedings of the 6th ACM SIGPLAN Symposium on Scala10.1145/2774975.2774981(41-50)Online publication date: 13-Jun-2015
https://dl.acm.org/doi/10.1145/2774975.2774981
Farmer AHoener zu Siederdissen CGill AChin WHage J(2014)The HERMIT in the streamProceedings of the ACM SIGPLAN 2014 Workshop on Partial Evaluation and Program Manipulation10.1145/2543728.2543736(97-108)Online publication date: 11-Jan-2014
https://dl.acm.org/doi/10.1145/2543728.2543736
Hinze RWu NCarette JWillcock J(2013)Histo- and dynamorphisms revisitedProceedings of the 9th ACM SIGPLAN workshop on Generic programming10.1145/2502488.2502496(1-12)Online publication date: 28-Sep-2013
https://dl.acm.org/doi/10.1145/2502488.2502496
Show More Cited By

Recommendations

Theorizing Practice and Practicing Theory

This paper describes the emerging field of practice theory as it is practiced in relation to organizational phenomena. We identify three approaches---empirical, theoretical, and philosophical---that relate to the what, the how, and the why of using a ...
Affordances for practice

This paper argues that Gibson's concept of affordance inserts a powerful conceptual lens for the study of sociomateriality as enacted in contemporary organizational practices. Our objective in this paper is to develop a comprehensive view of affordances ...
Novel Data Fusion Method Using Dempster-Shafer Theory
ICEICE '12: Proceedings of the 2012 Second International Conference on Electric Information and Control Engineering - Volume 03

In order to improve the robustness of the multi-sensor data fusion system, a novel data fusion algorithm is proposed based on Dempster-Shafer theory. Firstly the accuracy of the measured data are obtained according to relative distance between data, ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

IFL'10: Proceedings of the 22nd international conference on Implementation and application of functional languages

September 2010

217 pages

ISBN:9783642242755

Editors:
Jurriaan Hage
Utrecht University, Department of Information and Computing Sciences, Utrecht, The Netherlands
,
Marco T. Morazán
Seton Hall University, Department of Mathematics and Computer Science, South Orange, NJ

Sponsors

Utrecht University: Utrecht University
Microsoft Research: Microsoft Research
KNAW: Koninklijke Nederlandse Academie van Wetenschappen

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 01 September 2010

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 13 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Jonnalagedda MStucki SHaller PMiller H(2015)Fold-based fusion as a library: a generative programming pearlProceedings of the 6th ACM SIGPLAN Symposium on Scala10.1145/2774975.2774981(41-50)Online publication date: 13-Jun-2015
https://dl.acm.org/doi/10.1145/2774975.2774981
Farmer AHoener zu Siederdissen CGill AChin WHage J(2014)The HERMIT in the streamProceedings of the ACM SIGPLAN 2014 Workshop on Partial Evaluation and Program Manipulation10.1145/2543728.2543736(97-108)Online publication date: 11-Jan-2014
https://dl.acm.org/doi/10.1145/2543728.2543736
Hinze RWu NCarette JWillcock J(2013)Histo- and dynamorphisms revisitedProceedings of the 9th ACM SIGPLAN workshop on Generic programming10.1145/2502488.2502496(1-12)Online publication date: 28-Sep-2013
https://dl.acm.org/doi/10.1145/2502488.2502496
Hinze RJames DHarper TWu NMagalhães JLöh AGarcia R(2012)Sorting with bialgebras and distributive lawsProceedings of the 8th ACM SIGPLAN workshop on Generic programming10.1145/2364394.2364405(69-80)Online publication date: 12-Sep-2012
https://dl.acm.org/doi/10.1145/2364394.2364405
Harper T(2011)A library writer's guide to shortcut fusionACM SIGPLAN Notices10.1145/2096148.203468246:12(47-58)Online publication date: 22-Sep-2011
https://dl.acm.org/doi/10.1145/2096148.2034682
Harper TClaessen K(2011)A library writer's guide to shortcut fusionProceedings of the 4th ACM symposium on Haskell10.1145/2034675.2034682(47-58)Online publication date: 22-Sep-2011
https://dl.acm.org/doi/10.1145/2034675.2034682

View Options

View options

Media

Figures

Other

Tables

View Table of Contents