# Categories a computer scientist should know about

I am a computer scientist with a CS degree from the 80's. I am learning category theory by myself. I am looking for advice about learning category theory. E.g. it is quite helpful in learning category theory to have examples from a familiar topic like logic or programming languages.

### What I know

I have read the answers to this question and the paper Physics, Topology, Logic and Computation: A Rosetta Stone which builds up concepts with parallels between category theory, logic, and theory of computation.

I know about the following categories:

• categories
• monoidal categories
• braided monoidal categories
• closed monoidal categories
• symmetric monoidal categories
• closed braided monoidal categories
• compact monoidal categories
• cartesian categories
• closed symmetric monoidal categories
• compact braided monoidal categories
• cartesian closed categories
• compact symmetric monoidal categories

### Questions

1. Are there any other major categories that a computer scientist should know about?

2. Were there any that have fallen out of favor? If yes, why? Have they been replaced with other categories?

3. When thinking about categories should I focus on the arrows first before the objects?

• For what purrpose are you learning category theory? Is it for logic and semantics, or something else? – David Boshton Jul 1 '14 at 15:25
• Obviously a good question to my open ended question. I presently tinker with theorem provers of the HOL variety and functional programming, so logic, languages, BDD, term rewriting, lambda calculus and unification are everyday concepts for me. I am also trying to learn more about SMT solvers. – Guy Coder Jul 1 '14 at 15:33
• You could try something completely different to get some feel for the other 90% of category theory. For instance, you could have a look at the basic setup of algebraic topology. That would give you some perspective. – Andrej Bauer Jul 2 '14 at 15:30
• I dunno. There are CS students our there who learnt algebraic topology from a computational point of view in one semester. Look up things like "persistent homology". – Andrej Bauer Jul 2 '14 at 15:44
• @Kaveh I don't think there's any such thing as a "category that all computer scientists should know about". I don't think any of my current work (algorithms and complexity) or previous work (finite model theory) required or would even have benefited from any knowledge of category theory. I can't even think of a conference talk I've seen in those areas that has used category theory. – David Richerby Jul 9 '14 at 6:44

## 3 Answers

Note that most of the categories you considered are 'abstract', i.e., they require structure or properties of an abstract category. As computer scientists we should also be familiar several concrete categories which turn out to be useful:

## Concrete categories

• Set
• Set$_{\mathcal P}$ (objects are sets, morphisms are relations)
• Rel (objects are relations, morphisms are functions preserving these relations)
• Pred (objects are predicates (= subsets) morphisms are functions preserving these relations.
• Posets
• $\omega$-CPOs
• Nominal sets
• Lawvere theories

## Abstract categories

• Functor categories
• Presheaf categories, in particular, monoid actions, which are equivalent to finite automata iianm
• Locally presentable categories
• Monads
• Enriched categories (in particular, O-categories)
• Kleisli and Eilenberg-Moore categories
• Embedding-projection categories
• Profunctors

Also, sometimes properties don't commute on the nose, and the structure under consideration is of higher-dimensional (i.e., 2-categorical).

As to your question 3: you can define a category without mentioning objects at all (though it's conceptually clearer if we do mention the objects).

If $F$ is an endofunctor in a category $C$, then the category of $F$-algebras is pretty important in the study of datatypes. In particular, initial objects in this category correspond closely to finite datastructures. See this page on Wikipedia for more details, including examples of how the types of natural numbers, cons-lists and binary trees arise in this way.

Also, a monad is just a monoid in the category of endofunctors :-) Highly tongue-in-cheek, but the category of endofunctors is important nevertheless, if you want a better theoretical understanding of (Haskell's) monads.

This is not a complete answer (as I'd be surprised if any answer will complete given the disparate nature of your research), but when I was going to do a PhD in re-representation of mathematical issues one of the constructs that was suggested was Sober Spaces. They underlie schemes, which connect algebraic topology, number theory and commutative algebra. This may help with the theorem prover side of things.

• Thanks. Yes trying to identify how to get unstuck in self-learning CT is hard as I don't know enough CT to explain my problem. One "ahh" moment came when watching this video by Mike Stay. Also working through Category Theory for Computing Science and doing the exercises is most beneficial. – Guy Coder Jul 8 '14 at 11:04
• Is it really right to say that sober spaces "underlie" schemes? Most introductions to schemes and books that talk about schemes that I've seen don't even mention sober spaces (or perhaps they do, but only in passing). I would think it's more that sober spaces generalize schemes, but I'm not so familiar with this part of topology... – Joshua Grochow Jul 8 '14 at 12:41