7 First abstract nonsense interlude: Category theory
Programming is presented as a stack of abstractions, from electrons and hardware up through bits, language features, and finally data structures and algorithms. The chapter argues that category theory offers an even more abstract way to think about these layers by focusing on relationships and composition. It frames this detour as both useful and enjoyable, especially because it connects directly to real language-design questions such as type compatibility.
A category is introduced as a collection of objects together with morphisms, or arrows, that obey identity and compositional rules. The text emphasizes that objects can be almost anything, including numbers, sets, people, or types, and that morphisms capture “can get from here to there” relationships. Functors are then described as structure-preserving mappings between categories: covariant functors keep arrow direction intact, while contravariant functors reverse it.
The chapter uses C# type variance to make these ideas concrete. Sequences like IEnumerable<T> behave covariantly because a sequence of giraffes can safely stand in for a sequence of animals, while input-heavy interfaces like comparers behave contravariantly because something that compares animals can also compare giraffes. By modeling assignment compatibility as morphisms in a category of types, the chapter shows how the language’s variance rules are instances of category-theoretic structure, and how generic type constructors act as covariant or contravariant endofunctors.
A small category with three objects, represented by the nodes, and six morphisms, represented by the arrows
A strangely familiar small category with four objects and 10 morphisms
The function F is represented as dashed arrows mapping from one category to another.
The category of four types with the assignment-compatibility morphism; the identity morphisms are omitted for clarity. Note that Giraffe and Tiger have morphisms to Animal but not to each other. A Giraffe can’t be assigned to a variable of type Tiger, and a Tiger can’t be assigned to a variable of type Giraffe, but both can be assigned to a variable of type Animal or Object.
Adding four constructed generic types to our category. Notice that the morphism structure of the interface types is similar to that of the original four types.
The mapping of a function from types to types, shown as dashed arrows
Part of another infinite category of types, this time with a contravariant interface
Summary
- Category theory is a modern mathematical discipline that studies relationships among arbitrary objects. It’s cheekily characterized as “generalized abstract nonsense.”
- A category is a collection of objects with reflexive, transitive morphisms. We can think of a morphism as of an arrow going from one object to another.
- A function that maps objects of one category to another while preserving morphisms is a covariant functor. A function that preserves morphisms but reverses their direction is a contravariant functor. If the two categories are the same, the functor is an endofunctor.
- The assignment-compatibility relation (“an expression of type
Xmay be assigned to a variable of typeY”) is a common morphism in a category in which types are objects. - Covariant and contravariant interfaces are called that because generic interfaces can be thought of as covariant or contravariant functors: functions from types to types that preserve assignment-compatibility morphisms.
- Posetal categories, which define a partial order on a set of objects, are common and particularly useful when the objects are types in a programming language. Semilattices are posets with the additional useful property that you can always find the most specific type that’s assignment-compatible with any two types.
- The relationship between category theory and the analysis of programming languages is deep; we’ve just scratched the surface here. We’ll go a little deeper in subsequent interludes.
FAQ
What is category theory in this chapter’s sense?
Category theory is presented as the study of relationships between “stuff,” rather than the stuff itself. In other words, it focuses on how objects relate to one another through morphisms and how those relationships can be preserved by functions such as functors.Why is category theory called “generalized abstract nonsense”?
Because it is extremely abstract: the actual objects in a category can be almost anything, and the theory studies only their relationships. Category theorists jokingly call it “generalized abstract nonsense” to emphasize that level of abstraction.What are the two main components of a category?
A category consists of a bunch of objects and a bunch of morphisms. The morphisms are arrows connecting objects and describe allowable relationships between them.What rules must morphisms in a category follow?
They must be reflexive and transitive. Every object has an identity morphism to itself, and if there is a morphism from A to B and from B to C, then there must also be a morphism from A to C.What is a morphism, in intuitive terms?
A morphism can be thought of as a “you can get from here to there” relationship between objects. It tells you how one object can be related to or transformed into another within the category.What is a functor?
A functor is a function between categories that maps objects to objects and preserves morphisms. It carries the structure of one category into another without breaking the relationships that matter.What is a covariant functor?
A covariant functor preserves the direction of morphisms. If there is an arrow from X to Y, then after applying the functor there is an arrow from F(X) to F(Y).What does contravariant mean in category theory?
Contravariant means the direction of morphisms is reversed. If X points to Y in the original category, then after applying a contravariant functor, F(Y) points to F(X).How do covariant and contravariant generic types relate to type systems?
The chapter explains that generic types can be understood as functors in the category of types. Covariant types, like a sequence interface, preserve assignment compatibility in the same direction, while contravariant types reverse it, which matches how some language type systems allow or disallow assignments.Why is IEnumerable<Giraffe> assignable to IEnumerable<Animal>, but IList<Giraffe> is not assignable to IList<Animal>?
IEnumerable<T> is covariant because it only produces values of T, so a sequence of giraffes can safely be treated as a sequence of animals. IList<T> is not covariant because it also accepts inserted values, and allowing a list of giraffes to be treated as a list of animals would let you insert the wrong kind of animal.
Fabulous Adventures in Data Structures and Algorithms ebook for free
