Theory and applications of inverting functions as folds

This paper is devoted to the proof, applications, and generalisation of a theorem, due to Bird and de Moor, that gave conditions under which a total function can be expressed as a relational fold. The theorem is illustrated with three problems, all dealing with constructing trees with various proper...

Full description

Saved in:
Bibliographic Details
Published in:Science of computer programming 2004-05, Vol.51 (1), p.87-116
Main Authors: Mu, Shin-Cheng, Bird, Richard
Format: Article
Language:English
Subjects:
Fold
Program derivation
Program inversion
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:This paper is devoted to the proof, applications, and generalisation of a theorem, due to Bird and de Moor, that gave conditions under which a total function can be expressed as a relational fold. The theorem is illustrated with three problems, all dealing with constructing trees with various properties. It is then generalised to give conditions under which the inverse of a partial function can be expressed as a relational hylomorphism. Its proof makes use of Doornbos and Backhouse's theory on well-foundedness and reductivity. Possible applications of the generalised theorem is discussed.
ISSN:0167-6423
1872-7964
DOI:10.1016/j.scico.2003.09.003