Generalised folds for nested datatypes
- 1 September 1999
- journal article
- Published by Association for Computing Machinery (ACM) in Formal Aspects of Computing
- Vol. 11 (2), 200-222
- https://doi.org/10.1007/s001650050047
Abstract
: Nested datatypes generalise regular datatypes in much the same way that context-free languages generalise regular ones. Although the categorical semantics of nested types turns out to be similar to the regular case, the fold functions are more limited because they can only describe natural transformations. Practical considerations therefore dictate the introduction of a generalised fold function in which this limitation can be overcome. In the paper we show how to construct generalised folds systematically for each nested datatype, and show that they possess a uniqueness property analogous to that of ordinary folds. As a consequence, generalised folds satisfy fusion properties similar to those developed for regular datatypes. Such properties form the core of an effective calculational theory of inductive datatypes.Keywords
This publication has 9 references indexed in Scilit:
- de Bruijn notation as a nested datatypeJournal of Functional Programming, 1999
- Purely Functional Data StructuresPublished by Cambridge University Press (CUP) ,1998
- Nested datatypesLecture Notes in Computer Science, 1998
- A generalization of the trie data structureMathematical Structures in Computer Science, 1995
- Designing arithmetic circuits by refinement in RubyLecture Notes in Computer Science, 1993
- Data structures and program transformationScience of Computer Programming, 1990
- Algebraic Approaches to Program SemanticsPublished by Springer Science and Business Media LLC ,1986
- The typechecking of programs with implicit type structureLecture Notes in Computer Science, 1984
- SubequalizersCanadian Mathematical Bulletin, 1970