Dipping a Toe into Category Theory

tl;dr – Abstract nonsense

Wikipedia says :

Category theory is used to formalize mathematics and its concepts as a collection of objects and arrows (also called morphisms). Category theory can be used to formalize concepts of other high-level abstractions such as set theory, ring theory, and group theory.
…an abstraction of mathematics itself that allows many intricate and subtle mathematical results in these fields to be stated, and proved, in a much simpler way than without the use of categories.

So it’s a node and arc graph kind of thing, formal and abstract, that can be used to find new approaches to existing problems. So far so good, and sounding like familiar territory. and seven years ago I ordered Basic Category Theory for Computer Scientists. Which almost immediately went onto the shelf. Reason being it begins with a load of arcane notation and terminology that immediately threw me – I Am Not A Mathematician.
But in the process of reshelving books a few weeks ago I stumbled on it again, and the frustration at not being able to grasp even the ‘basics’ rose again from my gullet. Search engine time.

Before long I’d found Category Theory for Scientists, a piece of MIT Open Courseware. Check this diagram:

Aha! To all intents and purposes a conceptual map, a graph very similar to those found around Semantic Web/Linked Data activies. A route into this stuff dannys might be able to grasp. Well so far, yes, but it’s an uphill struggle. The textbook runs to 268 pages and does introduce quite a lot of new-to-dannys notation and terminology: products, coproducts, limits, colimits, functors, monads, monoids, operads… (Ok, I have come across some of these in other mostly forgotten contexts, but their definitions with Category Theory aren’t necessarily the ‘familiar’ ones).

The diagram is an example of an Olog, a category whose objects are represented as boxes containing sentences and whose morphisms are represented as directed labeled arrows between boxes.

Ok, I’d better backtrack and provide a couple of (informal, no doubt naive) definitions.
Objects in Category Theory are a step more abstract than those coders (or humans) are used to dealing with, they are structures. For example, you can talk of a class of all objects having a set structure. That’s set in the sense of a collection of distinct objects, considered as an object in its own right. The category Set contains all those sets. The category Graph contains graphs, Olog (above) is another one, and so on.
Morphisms (or ‘arrows’) are pretty abstract too. While within Set (and the usual set theory), morphisms are just functions in the usual mathematical sense (a relation between a set of inputs and a set of permissible outputs with the property that each input is related to exactly one output), CT generalizes this to (more or less) any structure-preserving mapping. So a morphism in graph will be a mapping between one bunch of nodes and arcs and another bunch of nodes and arcs.
Categories are essentially structures containing objects and morphisms as above, with a couple of provisos : the morphisms can be composed (associatively) and there’s an identity arrow for each object.

Not abstract nonsense enough yet? Well how about the category of categories. That (with certain restrictions) has morphisms called functors, in effect mappings between categories.

Now I’m optimistic this latter bit is why Category Theory should be useful in Web knowledge representation, you can get (kind of) analogies across domains that are very different in detail but share some level of abstract structural similarity. In fact googling ‘semantic web category theory‘ yields a bunch of papers on semantic interop using this stuff. There’s also a fun-sounding technique called diagram chasing, a visual method of arguing with abstract morphisms, and one that might yield to relatively down-to-earth coding techniques.

[Note that Olog has a function requirement which messes up a direct mapping between semweb languages and Ologs, though I’m pretty sure a one-step-removed mapping should be straightforward.]

I’ve personally a long, long way to go before I grok this stuff properly, but I have got far enough to think it worth flagging up as of interest…

One final note. Forgot exactly where I read it, but the CT folks have a way around Russell’s Paradox. You work with a universe U, then if you run into the paradox you just create a bigger universe U’ that contains U.

PS. Category Theory has cropped up on the semweb mailing list, and it turns out that David Spivak, the author of the MIT material has done a paper on applying Category Theory to SPARQL queries.

PPS. Looking for some easy lectures on youtube, I stumbled on this, Faster JavaScript with Category Theory by John Bender. He introduces two categories: Html and Jqry (jQuery), figures out a functor between them, and shows how to get performance improvements (essentially by using composition to cut down the number of nested loops). He’s also got some JS libs on github, wield, that can be slotted in place of jQuery/DOM stuff where performance is needed.