Bananas in space

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Bananas in space: extending fold and unfold to exponential types

Full text

Pdf (986 KB)

Source

Functional Programming Languages and Computer Architecture archive
Proceedings of the seventh international conference on Functional programming languages and computer architecture table of contents

La Jolla, California, United States

Pages: 324 - 333

Year of Publication: 1995

ISBN:0-89791-719-7

Authors

Erik Meijer	University of Utrecht, The Netherlands
Graham Hutton	University of Utrecht, The Netherlands

Sponsors

IFIP WG 2.8 : IFIP WG 2.8
SIGPLAN: ACM Special Interest Group on Programming Languages
SIGARCH: ACM Special Interest Group on Computer Architecture

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 2, Downloads (12 Months): 39, Citation Count: 20

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/224164.224225 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Samson Abramsky, The lazy lambda calculus, Research topics in functional programming, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
	2	Lennart Augustsson. The Haskell B. compiler. Chalmers University of Technology, 1994.
	3	Roland Backhouse, Ed Voermans, and Jaap van der Woude. A relational theory of datatypes. In preparation, 1994.
	4	Henk Barendregt. The Lambda Calculus - it's Syntax and Semantzcs. North-Holland, 1984. Revised edition.
	5	H Bekic , C B. Jones, Programming languages and their definition, Springer-Verlag New York, Inc., New York, NY, 1984
	6	Richard Bird. Constructive functional programming. In Proc. Marktoberdorf International Summer School on Constructive Methods 2n Computer Science. Springer- Verlag, 1989.
	7	Richard Bird , Oege de Moor, Algebra of programming, Prentice-Hall, Inc., Upper Saddle River, NJ, 1997
	8	Richard Bird , Philip Wadler, An introduction to functional programming, Prentice Hall International (UK) Ltd., Hertfordshire, UK, 1988
	9	Gert Florijn. Modelling office processes with functional parsers. University of Utrecht, The Netherlands, 1994.
	10	Maarten Fokkinga. Law and Order ~n Algor~thm~cs. PhD thesis, University of Twente, March 1992.
	11	Peter Freyd. Algebraically complete categories. In A. Carboni et al, editor, Proc. 1990 Como Category Theory Conference, volume 1488 of Lecture Notes 2n Math, pages 95-104. Springer-Verlag, Berlin, 1990.
	12	Peter Freyd. Recursive types reduced to inductive types. In Proc. LICS 90. IEEE Computer Society Press, 1990.
	13	Jeremy Gibbons, Algebras for tree algorithms, 1991
	14	T. Hagino. Category Theoretic Approach to Data Types PhD thesis, University of Edinburgh, 1987.
	15	Graham Hutton. Higher-order functions for parsing. Journal of Functional Programming, 2(3):323-343, July 1992.
	16	Mark Jones. Gofer 2.28 release notes. February 1993.
	17	Mark P. Jones, A system of constructor classes: overloading and implicit higher-order polymorphism, Proceedings of the conference on Functional programming languages and computer architecture, p.52-61, June 09-11, 1993, Copenhagen, Denmark [doi>10.1145/165180.165190]
	18	Mark Jones Personal communication, May 1994.
	19	Mark Jones and Erik Meijer. Gofer goes bananas. In preparation, 1994.
	20	G. Malcolm, Data structures and program transformation, Science of Computer Programming, v.14 n.2-3, p.255-279, Oct. 1990 [doi>10.1016/0167-6423(90)90023-7]
	21	Ernest G. Manes , Michael A. Arbib, Algebraic approaches to program semantics, Springer-Verlag New York, Inc., New York, NY, 1986
	22	Lambert Meertens. Algorithmics: Towards programming as a mathematicM activity. In Proc. CWI Symposium, Centre for Mathematics and Computer Science, Amsterdam, November 1983.
	23	Lambert Meertens. Paramorphisms. Formal Aspects of Computing, 4(5):413-425, 1992.
	24	Erik Meijer. Calculating Compilers. PhD thesis, Nijmegen University, February 1992.
	25	Erik Meijer. More advice on proving a compiler correct: Improve a correct compiler. Submitted for Publication, September 1994.
	26	Erik Meijer. Type classes for better free theorems. In preparation, 1994.
	27	Erik Meijer , Maarten Fokkinga , Ross Paterson, Functional programming with bananas, lenses, envelopes and barbed wire, Proceedings of the 5th ACM conference on Functional programming languages and computer architecture, p.124-144, June 1991, Cambridge, Massachusetts, United States
	28	Ross Paterson. Control structures from types. Submitted for publication, 1994.
	29	Andrew M. Pitts. Relational properties of recursively defined domains. In Proc. LiCS 93. IEEE Computer Society Press, 1993.
	30	John C. Reynolds, On the Relation between Direct and Continuation Semantics, Proceedings of the 2nd Colloquium on Automata, Languages and Programming, p.141-156, July 29-August 02, 1974
	31	John C. Reynolds. Types, abstraction and parametric polymorphism. Informat,on Processing, 83:513-523, 1983.
	32	David A. Schmidt, Denotational semantics: a methodology for language development, William C. Brown Publishers, Dubuque, IA, 1986
	33	Tim Sheard and Leonidas Fegaras. A folci for all seasons. In Proc. FPCA 93. Springer, 1993.
	34	Mike B. Smyth and Gordon D. Plotkin. The category theoretic solution of recursive domain equations. SiAM Journal of Computing, pages 761-783, 1982.
	35	Doaitse Swierstra and Oege de Moor. Virtual data structures. Technical Report RUU-CS-92-16, Utrecht University, The Netherlands, 1992.
	36	Philip Wadler, Theorems for free!, Proceedings of the fourth international conference on Functional programming languages and computer architecture, p.347-359, September 11-13, 1989, Imperial College, London, United Kingdom [doi>10.1145/99370.99404]
	37	Philip Wadler, Deforestation: transforming programs to eliminate trees, Theoretical Computer Science, v.73 n.2, p.231-248, June 22, 1990

CITED BY 20

	Ralf Hinze, A new approach to generic functional programming, Proceedings of the 27th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.119-132, January 19-21, 2000, Boston, MA, USA
	Patrik Jansson , Johan Jeuring, PolyP—a polytypic programming language extension, Proceedings of the 24th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.470-482, January 15-17, 1997, Paris, France
	Carsten Schurmann , Joelle Despeyroux , Frank Pfenning, Primitive recursion for higher-order abstract syntax, Theoretical Computer Science, v.266 n.1-2, p.1-57, 09/06/2001
	Graham Hutton, Fold and unfold for program semantics, ACM SIGPLAN Notices, v.34 n.1, p.280-288, Jan. 1999
	Jonathan Sobel , Daniel P. Friedman, Recycling continuations, ACM SIGPLAN Notices, v.34 n.1, p.251-260, Jan. 1999
	Valery Trifonov , Bratin Saha , Zhong Shao, Fully reflexive intensional type analysis, ACM SIGPLAN Notices, v.35 n.9, p.82-93, Sept. 2000
	Geoffrey Washburn , Stephanie Weirich, Boxes go bananas: encoding higher-order abstract syntax with parametric polymorphism, ACM SIGPLAN Notices, v.38 n.9, p.249-262, September 2003
	Zhenjiang Hu , Hideya Iwasaki , Masato Takeichi , Akihiko Takano, Tupling calculation eliminates multiple data traversals, ACM SIGPLAN Notices, v.32 n.8, p.164-175, Aug. 1997
	Olaf Chitil, Typer inference builds a short cut to deforestation, ACM SIGPLAN Notices, v.34 n.9, p.249-260, Sept. 1999
	Leonidas Fegaras , Tim Sheard, Revisiting catamorphisms over datatypes with embedded functions (or, programs from outer space), Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.284-294, January 21-24, 1996, St. Petersburg Beach, Florida, United States
	Neil Ghani , Patricia Johann , Tarmo Uustalu , Varmo Vene, Monadic augment and generalised short cut fusion, ACM SIGPLAN Notices, v.40 n.9, September 2005
	Stephanie Weirich, RepLib: a library for derivable type classes, Proceedings of the 2006 ACM SIGPLAN workshop on Haskell, September 17-17, 2006, Portland, Oregon, USA
	Graham Hutton, A tutorial on the universality and expressiveness of fold, Journal of Functional Programming, v.9 n.4, p.355-372, July 1999
	C. B. Jay , G. Bellè , E. Moggi, Functorial ML, Journal of Functional Programming, v.8 n.6, p.573-619, November 1998
	Ralf Hinze, Perfect trees and bit-reversal permutations, Journal of Functional Programming, v.10 n.3, p.305-317, May 2000
	Erik Meijer, Confessions of a used programming language salesman, ACM SIGPLAN Notices, v.42 n.10, October 2007
	Geoffrey Washburn , Stephanie Weirich, Boxes go bananas: Encoding higher-order abstract syntax with parametric polymorphism*, Journal of Functional Programming, v.18 n.1, p.87-140, January 2008
	Bruno C.d.S. Oliveira , Meng Wang , Jeremy Gibbons, The visitor pattern as a reusable, generic, type-safe component, ACM SIGPLAN Notices, v.43 n.10, September 2008
	Paul Tarau, Isomorphisms, hylomorphisms and hereditarily finite data types in Haskell, Proceedings of the 2009 ACM symposium on Applied Computing, March 08-12, 2009, Honolulu, Hawaii
	Edwin Westbrook , Aaron Stump , Evan Austin, The calculus of nominal inductive constructions: an intensional approach to encoding name-bindings, Proceedings of the Fourth International Workshop on Logical Frameworks and Meta-Languages: Theory and Practice, August 02-02, 2009, Montreal, Quebec, Canada