Catherine Hope
Compact fusion
Hope, Catherine; Hutton, Graham
Abstract
There are many advantages to writing functional programs in a compositional style, such as clarity and modularity. However, the intermediate data structures produced may mean that the resulting program is inefficient in terms of space. These may be removed using deforestation techniques, but whether the space performance is actually improved depends upon the structures being consumed in the same order that they are produced. In this paper we explore this problem for the case when the intermediate structure is a list, and present a solution. We then formalise the space behaviour of our solution by means of program transformation techniques and the use of abstract machines.
Citation
Hope, C., & Hutton, G. (2006). Compact fusion.
Conference Name | Workshop on Mathematically Structured Functional Programming |
---|---|
Publication Date | Jul 1, 2006 |
Deposit Date | Mar 18, 2015 |
Publicly Available Date | Mar 18, 2015 |
Peer Reviewed | Peer Reviewed |
Keywords | hylomorphism, space, fold, abstract machine |
Public URL | https://nottingham-repository.worktribe.com/output/1018333 |
Publisher URL | http://ewic.bcs.org/content/ConWebDoc/5350 |
Files
compact.pdf
(119 Kb)
PDF
Copyright Statement
Copyright information regarding this work can be found at the following address: http://creativecommons.org/licenses/by/4.0
You might also like
Calculating correct compilers
(2015)
Journal Article
Cutting out continuations
(2016)
Presentation / Conference Contribution
Towards a theory of reach
(2016)
Journal Article
Failing faster: overlapping patterns for property-based testing
(2017)
Presentation / Conference Contribution
Contractive Functions on Infinite Data Structures
(2016)
Presentation / Conference Contribution
Downloadable Citations
About Repository@Nottingham
Administrator e-mail: discovery-access-systems@nottingham.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search