Monads of Coalgebras: Rational Terms and Term Graphs
Neil Ghani1, Christoph Lüth2, Federico de Marchi1
1Department of Mathematics and Computer Science, University of Leicester
2FB3 - Mathematik und Informatik, Universität Bremen

Whilst the relationship between initial algebras and monads is This paper introduces guarded and strongly guarded monads as a unified model of a variety of different term algebras covering fundamental examples such as initial algebras, final coalgebras, rational terms and term graphs. We develop a general method for obtaining finitary guarded monads which allows us to define and prove properties of the rational and term graph monads. Furthermore, our treatment of rational equations extends the traditional approach to allow right-hand sides of equations to be infinite terms, term graphs or other such coalgebraic structures. As an application, we use these generalised rational equations to sketch part of the correctness of the the term graph implementation of functional programming languages.


Christoph Lüth, 02.05.2002