Book contents
- Frontmatter
- Contents
- Preface
- 1 Introduction
- 2 Categorical Preliminaries
- 3 Partiality
- 4 Order-Enriched Categories of Partial Maps
- 5 Data Types
- 6 Recursive Types
- 7 Recursive Types in Cpo-Categories
- 8 FPC
- 9 Computational Soundness and Adequacy
- 10 Summary and Further Research
- A Lemma 8.4.4
- B Theorem 8.6.6
- C Lemma 9.1.3
- D Propositions D.0.1 and D.0.2
- Bibliography
- Index
- Symbol Index
5 - Data Types
Published online by Cambridge University Press: 23 November 2009
- Frontmatter
- Contents
- Preface
- 1 Introduction
- 2 Categorical Preliminaries
- 3 Partiality
- 4 Order-Enriched Categories of Partial Maps
- 5 Data Types
- 6 Recursive Types
- 7 Recursive Types in Cpo-Categories
- 8 FPC
- 9 Computational Soundness and Adequacy
- 10 Summary and Further Research
- A Lemma 8.4.4
- B Theorem 8.6.6
- C Lemma 9.1.3
- D Propositions D.0.1 and D.0.2
- Bibliography
- Index
- Symbol Index
Summary
In this chapter we study the categorical constructions for interpreting data types. We start by observing that the notion of pairing in a category of partial maps (with a minimum of structure) cannot be the categorical product. The appropriate interpretation for product types (partial products) is the categorical product in the category of total maps endowed with a pairing operation on partial maps extending the pairing of total maps. Once the notion of product is established, partial exponentials are defined as usual, and some properties of Poset-partial-exponentials are presented. Next colimits are studied. The situation is completely different from that of limits. For example, an object is initial in the category of total maps if and only if it is so in the category of partial maps. A characterisation of certain colimits (including coproducts) in a category of partial maps, due to Gordon Plotkin, is given. We further relate colimits in the category of total maps and colimits in the category of partial maps by means of the lifting functor. Finally, we provide conditions on a Cpo-category of partial maps under which ω-chains of embeddings have colimits. This is done in the presence of the lifting functor, and for arbitrary categories of partial maps.
Partial Binary Products
The data type for pairing in pΚ cannot be the categorical product because, under reasonable assumptions, this would lead to inconsistency.
- Type
- Chapter
- Information
- Axiomatic Domain Theory in Categories of Partial Maps , pp. 77 - 105Publisher: Cambridge University PressPrint publication year: 1996