Theory and applications of inverting functions as folds.

S-C. Mu and R. S. Bird. In Science of Computer Programming Vol. 51 Special Issue for Mathematics of Program Construction 2002, pp. 87-116, 2003.
[PDF][GZipped Postscript]

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.

This entry was posted in Journal and tagged , , . Bookmark the permalink. Post a comment or leave a trackback: Trackback URL.

One Trackback

  1. By 先寬度標記 on June 21, 2009 at 10:53 am

    [...] 後來我在一篇談反函數的論文中用此題當作例子,焦點則是把這個演算法導出來。利用的性質是「先寬度標記是先寬度訪問的反函數再加上一個 zip」。此是後話不表。 [...]

Post a Comment

Your email is never published nor shared. Required fields are marked *

*
*

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>