| Theory and Applications of Inverting Functions as Folds (2007) | |||||||||||||||
Abstract | |||||||||||||||
| 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. The proof makes use of Doornbos and Backhouse's theory on well-foundedness and reductivity. Possible applications of the generalised theorem is then discussed. 1 | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||