liveBook · Manning

Category of types

As explained in Fabulous Adventures in Data Structures and Algorithms

The category of types is a category whose objects are types and whose morphisms express assignment compatibility.

The category of types turns ordinary assignment rules into a mathematical structure. Its objects are types, and a morphism from X to Y exists when an expression of type X can be assigned to a variable of type Y. section 7.2

With Object, Animal, Giraffe, and Tiger, assignment compatibility forms a partial order: Giraffe and Tiger both lead to Animal and Object, but neither leads to the other. Identity morphisms are normally omitted from the diagram. section 7.2

Covariance as preserved assignment

An IE<Giraffe> cannot initially be assigned to IE<Animal>. Because IE<T> uses T only as output, declaring interface IE<out T> makes the assignment valid. The generic construction then preserves the relevant assignment-compatibility morphisms. section 7.2

This perspective explains the terminology: covariant and contravariant generic interfaces behave like functors that preserve assignment morphisms, either in the same direction or in reverse. The treatment reaches the connection to posetal categories and semilattices, but only sketches the wider relationship to programming-language analysis. section 7.4

How Fabulous Adventures in Data Structures and Algorithms covers it

How deep it goes
Builds a four-type category and applies it to IE<T>, then sketches functors and semilattices without deeper formal development.
Examples
Uses Object, Animal, Giraffe, Tiger, and IE<T> assignments to demonstrate partial ordering and covariance.
What it assumes
Assumes familiarity with types, inheritance, generic interfaces, and assignment; defines morphisms through assignment compatibility.
What you can do after
Evaluate generic assignments using morphisms and recognize why output-only interfaces can be declared covariant.
How it connects
Connects assignment compatibility with covariance, contravariance, functors, posetal categories, and semilattices.

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Fabulous Adventures in Data Structures and Algorithms. The section links point to the parts of the book it draws on.