Category theory for Haskell programmers

Here is some advice, gained through my own trial and error, on how to teach yourself basic category theory.  This advice will probably be useful only if you are like me, i.e. a computer scientist and Haskell programmer without a strong background in advanced math.

The development of category theory was motivated by problems in the mathematical field of abstract algebra, and most of the literature assumes that you come from this background. What little knowledge I have of groups, rings, fields, and so on was stretched and then quickly broken by the examples in mathematically-oriented textbooks (e.g. Mac Lane).  I decided I needed a different approach.

So, here is how I acquired the basics:

Step 1:  Read Brent Yorgey’s excellent Typeclassopedia. Besides being a great intermediate Haskell tutorial and guide to the standard libraries, it will make you understand why programmers should care about category theory.

Step 2: Work through Benjamin Pierce’s Basic Category Theory for Computer Scientists.  Although frequently criticized for its terseness, this book is one of the few resources available that anchors the abstract notions of category theory to concrete and accessible topics in computer science.

Step 3: Supplement Pierce with Eugenia Cheng’s excellent tutorial videos. I recommend reading a section in Pierce and then watching the relevant videos. This combo worked really well for me.

Step 4: It may help to have a look at the category-extras package on Hackage. For example, I found the source code for the Control.Functor.Adjunction module helpful in understanding adjunctions.  Simply reading the type annotations can provide intuition.

Pierce’s book ends with adjunctions which are, unfortunately, where monads begin. By this point, however, I was comfortable enough with the basic concepts to move on to an advanced textbook (namely Mac Lane, see below).

You may be tempted to start with Saunders Mac Lane’s Categories for the Working Mathematician.  This is pretty much the definitive text on category theory, but unless you have a firm grasp of abstract algebra you may find it tough going. Until I understood the basic ideas, I found it utterly impenetrable.

At the other end of the spectrum is Conceptual Mathematics: A First Introduction to Categories by F. William Lawvere. This book starts with very basic foundations and is easy to follow.  It does a good job of motivating category theory through examples (although not from computer science).  I found that it moved a bit too slowly.

If you know of any other good resources for mathematically-impaired computer scientists trying to learn category theory, please leave a comment below.

About these ads
This entry was posted in Haskell and tagged , . Bookmark the permalink.

19 Responses to Category theory for Haskell programmers

  1. Aaron Culich says:

    Category Theory for Computing Science by Michael Barr & Charles Wells. It is out of print but if you write to CRM Books at the Université de Montréal you can order a copy for CAN$45 + shipping/export fees (at least that is what was last quoted to me).

  2. solrize says:

    Haskell Wikibook is a good place to start:

    http://en.wikibooks.org/wiki/Haskell/Category_theory

  3. Cale Gibbard says:

    Awodey’s book “Category Theory” is my favourite introduction. It’s a lot lighter on prerequisites than MacLane’s book, developing some of the most important examples within the book itself. Some of the explanations are among the best that I’ve seen — in particular, I don’t think I really understood Yoneda’s lemma properly until reading Awodey’s treatment of it.

  4. nomen says:

    If, as you say, you acquired category theory what’s stopping you from spilling the beans on it, as opposed to providing random links?

  5. Matt R says:

    There is also Barr and Wells’ “Category Theory Lecture Notes” available online: http://folli.loria.fr/cds/1999/library/pdf/barrwells.pdf

    I’ll second the recommendation for the Catsters videos, but I confess that neither I nor my boss found Pierce’s book to be much of a help.

  6. Sjoerd Visscher says:

    If it helps to look at the category-extras package, it might also help to look at my data-category package, although probably less so, as the types are not as readable.

    http://hackage.haskell.org/package/data-category

    • Sean Leather said on November 24, 2010 at 2:37 am:

      > My category theory references.

      In briefly reviewing that list, I found one rather unusual informal article, entitled “When is one thing equal to some other thing?”, by Barry Mazur, dated June 12, 2007, which adopted a very conversational style in describing categories as “B.Y.O.S.T. [Bring Your Own Set Theory] parties” that balance mathematical objects with structure in replacing mathematical objects with “network[s] of relationships,” contrasting the concept of a category (due to Samuel Eilenberg and Saunders Mac Lane) with that of a formal system (due to David Hilbert), and providing a definition of a locally small category in terms of a “bare set theory.” The author uses categories to describe how equality is replaced by equivalence expressed as “canonical isomorphism” in the context of category theory.

  7. Geoff says:

    I completely forgot about the Haskell wikibook chapter on category theory, but I should have included it above. Maybe after the Typeclassopedia, but before Pierce?

    I also looked at Awoday’s book a while ago, but found it confusing at the time. I will give it another look, along with all the other great links. Thanks everyone!

  8. You may also be interested in my rather long blog entry describing a collection of publications that are suitable for learning Haskell through category theory; _viz._:

    Learning Haskell through Category Theory, and Adventuring in Category Land: Like Flatterland, Only About Categories « Monadically Speaking: Adventures in PLT Wonderland

    http://dekudekuplex.wordpress.com/2009/01/16/learning-haskell-through-category-theory-and-adventuring-in-category-land-like-flatterland-only-about-categories/

  9. Pingback: Category Theory for the Mathematically Impaired: An Outline of A Short Reading List for “Mathematically-impaired Computer Scientists Trying to Learn Category Theory” « Monadically Speaking: Adventures in PLT Wonderland

  10. jt says:

    This is a book to learn Category Theory using Standard ML.
    Not Haskell, but might interest some of you.

    http://www.cs.man.ac.uk/~david/categories/

  11. Benjamin L. Russell said on August 28, 2012 at 11:51 am:

    > David Dalrymple said on December 5, 2010 at 9:30 am:

    Sorry, I have posted an erroneous date and time for the citation. The citation should have been written as follows:

    > David Dalrymple said on August 27, 2012 at 3:32 pm:

    I would edit my comment; however, this blog does not allow editing of one’s comments. Hence, I have posted a correction. Apologies.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s