Haskell Language Category Theory Definition of a Category


Example

A category C consists of:

  • A collection of objects called Obj(C) ;
  • A collection (called Hom(C)) of morphisms between those objects. If a and b are in Obj(C), then a morphism f in Hom(C) is typically denoted f : a -> b, and the collection of all morphism between a and b is denoted hom(a,b) ;
  • A special morphism called the identity morphism - for every a : Obj(C) there exists a morphism id : a -> a ;
  • A composition operator (.), taking two morphisms f : a -> b, g : b -> c and producing a morphism a -> c

which obey the following laws:

For all f : a -> x, g : x -> b, then id . f = f and g . id = g
For all f : a -> b, g : b -> c and h : c -> d, then h . (g . f) = (h . g) . f

In other words, composition with the identity morphism (on either the left or right) does not change the other morphism, and composition is associative.

In Haskell, the Category is defined as a typeclass in Control.Category:

-- | A class for categories.
--   id and (.) must form a monoid.
class Category cat where
    -- | the identity morphism
    id :: cat a a

    -- | morphism composition
    (.) :: cat b c -> cat a b -> cat a c

In this case, cat :: k -> k -> * objectifies the morphism relation - there exists a morphism cat a b if and only if cat a b is inhabited (i.e. has a value). a, b and c are all in Obj(C). Obj(C) itself is represented by the kind k - for example, when k ~ *, as is typically the case, objects are types.

The canonical example of a Category in Haskell is the function category:

instance Category (->) where
  id = Prelude.id
  (.) = Prelude..

Another common example is the Category of Kleisli arrows for a Monad:

newtype Kleisli m a b = Kleisli (a -> m b)

class Monad m => Category (Kleisli m) where
  id = Kleisli return
  Kleisli f . Kleisli g = Kleisli (f >=> g)