On “on”

One of the things I like about languages like Haskell and ML is how you can often figure out what a function does just by looking at its type. For example, I recently came across the on function (defined in Data.Function), which I had not encountered before. The example defines a function groupOn like so:

groupOn :: Eq b =>; (a ->; b) ->; [a] ->; [[a]]
groupOn f = groupBy ((==) `on` f)

and then shows how it can be used

groupOn isDigit "46a12b159c"

which yields

["46","a","12","b","159","c"]

So hmm, this on function seems pretty useful, but what does it do? To figure it out, just look at its type:

on :: (b ->; b ->; c) ->; (a ->; b) ->; a ->; a ->; c

That looks very similar to the type for function composition!

(.) :: (b ->; c) ->; (a ->; b) ->; a ->; c

From the types, it looks like on might work just like function composition, except that the first argument is a binary (rather than unary) function. It turns out that this is exactly what on does. Its definition is:

f `on` g = \x y ->; f (g x) (g y)

This simple function turns out to quite handy, especially if you favor a point-free style. Apparently the most common use for on is in conjuction with the various "By" functions in Data.List, where it is used to build predicates. For example:

sortBy (compare `on` fst) [(5,'a'),(1,'b'),(3,'c')] == [(1,'b'),(3,'c'),(5,'a')]

Useful stuff!

monad-supply 0.3 released

I’ve uploaded a new version of monad-supply to Hackage and Github. There are two new functions. The first, exhausted, checks whether the supply is empty. The second, peek, will return the next element without removing it from the supply. Enjoy!

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.

Hello world!

Ok, let’s try blogging.  I have not had much luck with blogs in the past, but I am going to try to keep this one updated with things that I am working on, papers I am reading, anything related to CS that interests me.