##

Monads of Coalgebras: Rational Terms and Term Graphs
Neil Ghani^{1}, Christoph Lüth^{2},
Federico de Marchi^{1}

^{1}Department of Mathematics and Computer Science,
University of Leicester

^{2}FB3 - 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