Continuous Functions on Final Coalgebras

Abstract

In a previous paper we gave a representation of, and simultaneously a way of programming with, continuous functions on streams, whether discrete-valued functions, or functions between streams. We also defined a combinator on the representations of such continuous functions that reflects composition. Streams are one of the simplest examples of non-trivial final coalgebras. Here we extend our previous results to cover the case of final coalgebras for a broader class of functors than that giving rise to streams. Among the functors we can deal with are those that arise from countable signatures of finite-place untyped operators. These have many applications. The topology we put on the final coalgebra for such a functor is that induced by taking for basic neighbourhoods the set of infinite objects which share a common 'prefix', a la Baire space. The datatype of prefixes is defined together with the set of 'growth points' in a prefix, simultaneously. This we call beheading. To program and reason about representations of continuous functions requires a language whose type system incorporates the dependent function and pair types, inductive definitions at types Set, I → Set and (Σ I : Set) SetI, coinductive definitions at types Set and I → Set, as well as universal arrows for such definitions. Show more