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. Ifaandbare inObj(C), then a morphismfinHom(C)is typically denotedf : a -> b, and the collection of all morphism betweenaandbis denotedhom(a,b); - A special morphism called the identity morphism - for every
a : Obj(C)there exists a morphismid : a -> a; - A composition operator (
.), taking two morphismsf : a -> b,g : b -> cand producing a morphisma -> 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)
