Abstract
We develop a calculus for lazy functional programming based on recursion operators associated with data type definitions. For these operators we derive various algebraic laws that are useful in deriving and manipulating programs. We shall show that all example functions in Bird and Wadler's “Introduction to Functional Programming” can be expressed using these operators.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Roland Backhouse, Jaap van der Woude, Ed Voermans, and Grant Malcolm. A relational theory of types. Technical Report ??, TUE, 1991.
Rudolf Berghammer. On the use of composition in transformational programming. Technical Report TUM-18512, TU München, 1985.
R. Bird. An introduction to the theory of lists. In M. Broy, editor, Logic of Programming and Calculi of Discrete Design, pages 3–42. Springer Verlag, 1987. Also Technical Monograph PRG-56, Oxford University, October 1986.
Richard Bird. Constructive functional programming. In M. Broy, editor, Marktoberdorf International Summer school on Constructive Methods in Computer Science, NATO Advanced Science Institute Series. Springer Verlag, 1989.
Richard Bird and Phil Wadler. Introduction to Functional Programming. Prentice-Hall, 1988.
R. Bos and C. Hemerik. An introduction to the category-theoretic solution of recursive domain equations. Technical Report TRCSN 88/15, Eindhoven University of Technology, October 1988.
Manfred Broy. Transformation parallel ablaufender Programme. PhD thesis, TU München, München, 1980.
A. de Bruin and E.P. de Vink. Retractions in comparing Prolog semantics. In Computer Science in the Netherlands 1989, pages 71–90. SION, 1989.
Peter de Bruin. Naturalness of polymorphism. Technical Report CS 8916, RUG, 1989.
Maarten Fokkinga. Tupling and mutumorphisms. The Squiggolist, 1(4), 1989.
Maarten Fokkinga, Johan Jeuring, Lambert Meertens, and Erik Meijer. Translating attribute grammars into catamorphisms. The Squiggolist, 2(1), 1991.
Maarten Fokkinga and Erik Meijer. Program calculation properties of continuous algebras. Technical Report 91-4, CWI, 1991.
C. Gunter, P. Mosses, and D. Scott. Semantic domains and denotational semantics. In Marktoberdorf International Summer school on Logic, Algebra and Computation, 1989. to appear in: Handbook of Theoretical Computer Science, North Holland.
Tasuya Hagino. Codatatypes in ML. Journal of Symbolic Computation, 8:629–650, 1989.
J. Arsac and Y Kodratoff. Some techniques for recursion removal. ACM Toplas, 4(2):295–322, 1982.
D.J. Lehmann and M.B. Smyth. Algebraic specification of data types: a synthetic approach. Math. Systems Theory, 14:97–139, 1981.
Grant Malcolm. Algebraic Types and Program Transformation. PhD thesis, University of Groningen, The Netherlands, 1990.
Lambert Meertens. Algorithmics — towards programming as a mathematical activity. In Proceedings of the CWI symposium on Mathematics and Computer Science, pages 289–334. North-Holland, 1986.
Lambert Meertens. Paramorphisms. To appear in Formal Aspects of Computing, 1990.
John-Jules Ch. Meyer. Programming calculi based on fixed point transformations: semantics and applications. PhD thesis, Vrije Universiteit, Amsterdam, 1985.
Ross Paterson. Reasoning about Functional Programs. PhD thesis, University of Queensland, Brisbane, 1988.
John C. Reynolds. Types abstraction and parametric polymorphism. In Information Processing '83. North Holland, 1983.
David A. Schmidt. Denotational Semantics. Allyn and Bacon, 1986.
M.B. Smyth and G.D. Plotkin. The category-theoretic solution of recursive domain equations. SIAM Journal on Computing, 11(4):761–785, November 1982.
Joseph E. Stoy. Denotational Semantics, The Scott-Strachey Approach to Programming Language Theory. The MIT press, 1977.
Nico Verwer. Homomorphisms, factorisation and promotion. The Squiggolist, 1(3), 1990. Also technical report RUU-CS-90-5, Utrecht University, 1990.
Phil Wadler. Views: A way for pattern matching to cohabit with data abstraction. Technical Report 34, Programming Methodology Group, University of Göteborg and Chalmers University of Technology, March 1987.
Philip Wadler. Theorems for free ! In Proc. 1989 ACM Conference on Lisp and Functional Programming, pages 347–359, 1989.
Philip Wadler. Comprehending monads. In Proc. 1990 ACM Conference on Lisp and Functional Programming, 1990.
M. Wand. Fixed point constructions in order enriched categories. Theoretical Computer Science, 8, 1979.
Hans Zierer. Programmierung mit funktionsobjecten: Konstruktive erzeugung semantische bereiche und anwendung auf die partielle auswertung. Technical Report TUM-18803, TU München, 1988.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1991 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Meijer, E., Fokkinga, M., Paterson, R. (1991). Functional programming with bananas, lenses, envelopes and barbed wire. In: Hughes, J. (eds) Functional Programming Languages and Computer Architecture. FPCA 1991. Lecture Notes in Computer Science, vol 523. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3540543961_7
Download citation
DOI: https://doi.org/10.1007/3540543961_7
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-54396-1
Online ISBN: 978-3-540-47599-6
eBook Packages: Springer Book Archive