Book Review: Basic Category Theory for Computer Scientists (MIRI course list)

post by So8res · 2013-09-19T03:06:02.195Z · LW · GW · Legacy · 23 comments

Contents

  Basic Category Theory for Computer Scientists
    Chapter Summaries
    1. Basic Constructions
    2. Functors, Natural Transformations, and Adjoints
    3. Applications
    4. Further Reading
    Discussion
    Should I read it?
    Should I learn category theory?
    Final Notes
None
23 comments

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
2. Functors, Natural Transformations, and Adjoints
3. Applications
4. Further Reading

---

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:

1. Closed Cartesian Categories are in correspondence with lambda calculi.

2. Category theory can help make implicit conversion & generic operators more consistent in programming languages.

3. Category theory is linked to type theory, domain theory, and algebraic semantics (all useful in programming semantics).

4. 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:

1. You're familiar with the basic idea of category theory
2. You want to learn the basics
3. You are comfortable with functional programming and/or set theory
4. 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.

23 comments

Comments sorted by top scores.