Hostname: page-component-76fb5796d-25wd4 Total loading time: 0 Render date: 2024-04-25T11:53:49.917Z Has data issue: false hasContentIssue false

Monads of coalgebras: rational terms and term graphs

Published online by Cambridge University Press:  27 May 2005

NEIL GHANI
Affiliation:
Department of Mathematics and Computer Science, University of Leicester
CHRISTOPH LÜTH
Affiliation:
FB 3 – Mathematik und Informatik, Universität Bremen
FEDERICO DE MARCHI
Affiliation:
Department of Mathematics and Computer Science, University of Leicester

Abstract

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 that 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 term graph implementation of functional programming languages.

Type
Paper
Copyright
2005 Cambridge University Press

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)