How can two very different programming problems share a useful structure? Category theory looks past what things are and studies the relationships between them. Its practical appeal is composition: solve smaller problems, then connect their solutions. section 7.0 section 7.1
A category contains objects and morphisms—arrows from one object to another. Here, “object” does not mean an object in the object-oriented programming sense. Morphisms are reflexive and transitive: each object has an arrow to itself, and arrows from A to B and B to C imply one from A to C. section 7.1 section 7.4
Figure 7.1 A small category with three objects, represented by the nodes, and six morphisms, represented by the arrows
The nodes and arrows make the distinction visible: objects are the things being related; morphisms are the relationships. section 7.1
Mappings between categories introduce a second question: what happens to the arrows?
- A covariant functor maps objects to objects while preserving morphisms and their direction. section 7.4
- A contravariant functor preserves the relationships but reverses their direction. A functor whose source and destination are the same category is an endofunctor. section 7.4
Types as objects
Take types as objects and assignment compatibility as an arrow: X→Y means an expression of type X may be assigned to a variable of type Y. This makes covariance and contravariance of generic interfaces questions about whether a type-to-type mapping preserves or reverses those arrows. Posetal categories and semilattices provide further ways to examine such type relationships. section 7.4
