Book Review: Basic Category Theory for Computer Scientists (MIRI course list)
I’m reviewing the books on the MIRI course list. After finishing Cognitive Science I picked up Basic Category Theory for Computer Scientists, by Benjamin C. Pierce.
Basic Category Theory for Computer Scientists
This book is tiny, clocking in at around 80 pages. Don’t be fooled, it packs a punch.
A word of warning: when the title says “for Computer Scientists”, it is not abusing the term. I went in expecting Category Theory for Computer Programmers and a tone like “Welcome, Java Programmer, to the crazy world of math!”. What I got was a lean, no-bullshit introduction to category that assumes mathematical competence.
“Computer Scientist” and “Programmer” get mixed up in common parlance, so casual programmers are cautioned that this book targets the former group. Category Theory for Computer Scientists assumes you’re familiar with proof-writing, set theory, functional programming, and denotational semantics.
In return, Category Theory wastes none of your time. I found this refreshing, but unexpected.
I’ll give a brief overview of the contents of the book before discussing them.
Chapter Summaries
1. Basic Constructions
Introduces Categories.
Introduces monomorphisms (f∘g = f∘h → g=h) and epimorphisms (g∘f = h∘f → g=h), then uses these to introduce categorical duals (similar constructs with the direction of the arrows swapped).
Introduces isomorphisms and the concept of equality up to isomorphism.
Introduces initial and terminal objects (objects with exactly one arrow from/to each object).
Introduces binary products and coproducts. Generalizes to arbitrary products.
Introduces equalizers and coequalizers.
Introduces pullbacks, briefly mentions pushforwards.
Generalizes equalizers, products, and pullbacks to terminal cones (which are limits).
Introduces exponentiation.
Mentions Cartesian Closed Categories (categories with products, exponents, and a terminal object).
2. Functors, Natural Transformations, and Adjoints
Introduces Functors (arrows between categories).
Introduces F-Algebras (an extreme generalization of algebra).
Introduces Natural Transformations (structure-preserving mappings between functors).
Introduces Adjoints (functors related in way that generalizes efficiency/optimality).
3. Applications
Discusses four applications of category theory:
-
Closed Cartesian Categories are in correspondence with lambda calculi.
-
Category theory can help make implicit conversion & generic operators more consistent in programming languages.
-
Category theory is linked to type theory, domain theory, and algebraic semantics (all useful in programming semantics).
-
Category theory revolutionized how programming languages construct underlying denotations.
4. Further Reading
A list of textbooks, introductory articles, reference books, and research articles that the author recommends for further learning.
Discussion
The first two chapters of this book are the important parts. The third chapter points out ways that category theory has been applied to computer science, which I found interesting but not relevant to my goal (of learning category theory). The fourth chapter provides a list of resources, which will be handy to have around.
A textbook review is somewhat ungrounded if you don’t know the reviewer’s background: Category Theory was not a complete mystery to me when I picked up this book. I gained some little familiarity with the subject osmotically when learning Type Theory and messing around in Haskell. However, Category Theory always looked like abstract nonsense and I’d never studied it explicitly.
Given that background, this book served me very well.
Most of my utility was derived from doing the exercises in the book. My goal was to build a mental implementation of category theory, and reading math without doing it works about as well as writing code without running it.
The first five exercises alone corrected a handful of misconceptions I had about category theory, and were sufficient to take theorems from “opaque abstract nonsense” to “vaguely intuitive”.
(In my case, the fact that “the diagram commutes” means “all paths from one vertex to another compose to the same arrow” made a lot of things click. I expect such clicking points to vary wildly between people, so I won’t mention more.)
It is likely that any other category theory textbook could have given similar results by providing exercises. The selling point of this book is the narrative: if you don’t like narratives, this is the book for you.
In fact, this book is sometimes too terse. Take, for example, this suggestion after the introduction of adjoint functors:
The reader who has persevered this far is urged to consult a standard textbook for more details on alternative treatments of adjoints.
Or this, right when things were getting interesting:
A longer discussion of representability is beyond the scope of this introduction, but it is often named as one of the two or three key concepts of category theory.
That said, the book is titled Basic Category Theory, so I can’t complain.
Should I read it?
It really depends on your goals.
This book does not motivate the math: It assumes you want to know category theory, and teaches you without embellishment. If you are wondering what this whole category theory thing is and why it matters then you should probably find a friendlier introduction.
However, if:
You’re familiar with the basic idea of category theory
You want to learn the basics
You are comfortable with functional programming and/or set theory
You’re motivated and don’t need much guidance
then you should strongly consider reading the first two chapters of this book (and perhaps chapter 3 section 4).
If you’re looking for a really deep understanding of category theory, you should probably look elsewhere; this book doesn’t step beyond the basics.
All that assumes you want to learn category theory, which probably isn’t true of the general audience. A more pertinent question is perhaps:
Should I learn category theory?
It depends on your goals. I think it was worth learning, but I’m the sort of person who delights in clean abstractions.
If nothing else, category theory is a lesson in how far abstractions can be pushed. F-Algebras, for instance, are one of the most abstract ideas I’ve ever encountered. Category-theoretic products (or, more generally, cones) are astonishingly powerful given their generality. I was quite surprised by how far you can strip down exponentiation.
That said, category theory won’t help the average person act more rationally.
If you’re into math, programming, or physics then category theory will likely help you out. Otherwise, I wouldn’t recommend starting here.
If you happen to be a programmer considering diving off the deep end, I strongly recommend familiarizing yourself with pure functional programming languages first. (Haskell is a good place to start.) My familiarity with type theory and my use of functors made category theory easier to approach. (And besides, pure functional programming is lots of fun.)
Final Notes
I’m somewhat surprised that the MIRI course list Category Theory textbook doesn’t discuss Representation Theory.
Otherwise, this book is precisely what I expected from the MIRI course list: very good at shutting up and giving you the data. I came away pleased.
- The mechanics of my recent productivity by (9 Jan 2014 2:30 UTC; 200 points)
- Mental Context for Model Theory by (30 Oct 2013 6:35 UTC; 112 points)
- Book Review: Naïve Set Theory (MIRI course list) by (30 Sep 2013 16:09 UTC; 52 points)
- 's comment on What are you working on? October 2013 by (1 Oct 2013 22:31 UTC; 18 points)
- 's comment on Open Thread, October 13 − 19, 2013 by (15 Oct 2013 1:37 UTC; 2 points)
Mathematics StackExchange on learning category theory:
Yes, it’s not as if the textbooks will give you any examples.
Well, yeah, any run-of-the-mill category theory textbook will of course load you down with examples. That doesn’t mean they’ll give you the background instruction necessary to understand those examples. It’s all very well being told that the classic example of a non-concretizable category is the category of topological spaces and homotopy classes of continuous maps between them—if you’ve never taken a topology course, you won’t have any idea what that means, and the book isn’t going to include a beginner’s topology textbook as a footnote.
An example isn’t being told something like that, it’s being shown something like that, with diagrams. A beginner’s topology course is not required, the diagrams are.
I’m probably at the mathematically naive level that the linked post warns against, and after looking at many of the examples with diagrams in the various category theory textbooks, I still have basically no idea what CT brings to the table or how I should use it. It unifies formal proofs, topological computations and quantum mechanical systems? Great! Except I don’t know how to grind proofs, derive topology or compute quantum mechanics by hand, so I have little idea what that means in practice.
A lot of people seem to describe learning Haskell monads as a similar experience. Most of the examples are basically incomprehensible until you just work with the raw formalism from sufficiently many angles that you start to build the necessary headspace to work it into something useful. Maybe studying advanced topology and abstract algebra will get you familiar with working with sufficiently similar formal structures that you can actually get significant bits of category theory by analogy from something as short as a textbook example
Sarcasm is nearly always inadvisable!
This comment makes a fair point that people might be missing at first glace. It’s true, as IainM said, that many of the examples will be of the form “Remember that concept from Abstract Algebra of a free group generated by a set? Remember also the concept of the underlying set of elements in a group? Turns out that those concepts are an example of an adjoint pair of functors.” If you don’t have any recollection of the motivating concepts to draw upon, those examples won’t be of much help to you.
However, any category theory text will give you some example without assuming any prior familiarity. For example, preorders and posets, groups (defined as single-object categories in which all morphisms are invertible) and groupoids, plus the constructions that can be built out of given categories, such as comma categories, functor categories, and products of categories.
That said, if you don’t have some prior familiarity with Set Theory and the set-theoretical definition of functions, you will have a rough time. Most authors I’ve seen want to be able to invoke Set as an example of a category without having to explain to you what a set is or what functions between sets are. (Though, Goldblatt is an exception. He tries to teach the reader set theory before moving on to the category theory.)
This seems like exactly the sort of thing I’d expect to be in a good category theory textbook. If I flip open, say, a physics textbook, I don’t see unmotivated derivation of laws, I see “here’s what a pendulum, a buoy in rough waters, and a mass on a spring have in common,” for example.
Part of the point of learning from a textbook, instead of the original papers, is so you can get that motivation and learn those concepts in a natural way. That’s what a good textbook means, I’d say.
Thanks for writing this review. Category theory keeps coming up slightly in my courses but I’ve never gotten a chance to really tackle it head-on so reviews like this are helpful.
I’ve had the book by David Spivak “Category Theory for Scientists” sitting around for a while that looks promising for a perhaps broader scope of people here.
John Baez (who sometimes comments here) and Mike Stay also have a delightful paper “Physics, Topology, Logic and Computation: A Rosetta Stone”. It’s not an introduction to category theory but it does not really expect much background. Yet it still manages to bring some really impressively diverse fields together in interesting ways. Unfortunately it’s not quite deep enough to really do much with these connections other than give their general form. It’s very readable and has such a breadth of subjects in it that it’s pretty likely you’ll find some of it interesting and it serves to give a pretty strong motivation for why category theory is worth learning.
Ha, small world. I actually ran into A Rosetta Stone a little while back when I was doing haskell & physics in my free time; I’ve skimmed it before. I’ll have to go back and read it more closely now that I know the basics of Category Theory a little better.
Thanks for the tips!
Category Theory for Scientists is available as Open Courseware from MIT http://ocw.mit.edu/courses/mathematics/18-s996-category-theory-for-scientists-spring-2013/index.htm
The student examples of how to use Olog are worth reading, in addition to the lecture pdfs.
Neat! Great tip.
Thanks for writing this review, it has convinced me to pick up a copy of the book and work through it.
A book I would recommend in a related field is “Conceptual Mathematics: A First Introduction to Categories” http://www.amazon.co.uk/Conceptual-Mathematics-First-Introduction-Categories/dp/052171916X
It starts out assuming mathematical knowledge but nothing specific and progresses rapidly. I found it hugely interesting as a piece of general reading (I didn’t have a direct purpose for reading the book other than fun).
What counts as nonspecific mathematical knowledge?
I found it difficult to follow (especially in later chapters) not because I lacked any particular knowledge, but because I am not used to the sort of mathematical analysis that was being done.
It didn’t assume a particular knowledge but it gets very complicated in a short number of pages and I think people who are not comfortable in some area of mathematics would struggle.
Do you know why this book is on the MIRI course list? What is the connection to Friendly AI?
From the course list.
What parts of physics would category theory help with? I have not come across any yet.
Here’s a relevant article. If you’re looking for something more technical, check this paper out.
Have you read Pierce’s Types and Programming Languages? If so, would you say it provides sufficient foundation for this book?
I’m not sure it works as a prerequisite. I’ve read most of it, but don’t feel like it got me any closer at all to figuring out category theory.
Since category theory was invented to unify abstract algebra and topology, maybe textbooks in those would work instead?
I kind of worry about how much the whole category theory talk on programmer forums is the blind leading the blind. Mathematical maturity is difficult to communicate, and I don’t have a clear idea just how far along the ladder of mastery levels you need to be before you can make category theory start paying rent.
I read it a few years ago and didn’t enjoy it at all except for an early section describing some interesting categories. I’m a great programmer and familiar with functional programming but not much Haskell. I worked examples, followed proofs, and generally understood the material.
I view as cargo-cult any recommendations to read this book for someone who wants to program (AI or otherwise).