A categorical model for data structures
Meyer, Susan Conry
Jump, J. Robert
Master of Science
In this thesis we consider the problem of modeling data structures. A model based on category theory is proposed in which both the static and dynamic characteristics of data structures can be represented. Data structures are modeled by categories and their dynamic characteristics by functors between these categories. Hierarchical data structures are considered, and examples are given of several common types of information structures and their description within this model. The categorical model for data structures is employed in studying those properties of data structures which are due to their structure alone. This is done by considering the functors between the representations of different data structures in order to study the relationships between them. An indication of when one data structure can be realized in another is given and the class of realizations of a data structure D in another data structure D is characterized. Finally, a sufficient condition is given for the realization of one class of data structures in another.