Category Theory
A category has three components:
 A collection of objects.
 A collection of morphisms, each of which map one object to another.
 A notion of composition of these morphisms, i.e. morphisms can be composed. If
f: A > B
andg: B > C
are morphisms,f.g
generates a new morphismA > C
.
Note that a morphism has no specific semantics of mapping, but simply links two objects together. Morphisms are also called Arrows.
Examples
Set Category: Set
All sets and standard functions form a category. Functions need not to be surjective, since morphisms have no mapping semantics.
Group Category: Grp
All groups and homomorphisms between groups form a category. A group has specific algebaric structure, which morphisms should preserve.
Laws
Three laws needed to be followed for a category:
 Composition should be associative.
 Composition operation should be closed in the category, i.e. if
f: A > B
andg: B > C
, there must be ah: A > C
satisfyingh = f . g
.  For each object
A
, there should exist an identity morphismid(A): A > A
s.t. for everyf: A > B
,f = id(A) . f = f . id(B)
.
Note that:
 There may exist serveral morphisms between
A
andB
.  An identity has type
A > A
, but a morphism with such type needs not to be an identity.
Functors in Category Theory
A functor maps a category to another category. It should contains two mappings for objects and for morphisms, with composition operation and category laws preserved.
There’s a natural functor from Grp to Set, which maps groups to their underlying sets and group morphisms to the function which behave the same but are defined on sets instead of groups.
Paramateric Types in Haskell
It’s common to create new types that hold values of other types. List[a]
type constructor creates types that holds sequential values of same type; Maybe[a]
creates types that hold operation states (failure, or success with returned values).
Usually we want generated types to inherit functions from types being wrapped. For example, List[Int]
should have elementwise addition as Int
does, and Maybe[Int]
should have similar operations with no burden of rewrapping and unwrapping. Such ‘inheritance’ is only concerned with the structure of types, instead of specific functions, so should be done automatically if possible.
Hask Category
Haskell language itself forms a category, with all types being objects, and functions being morphisms. Such category is called Hask.
Hask Functors


A parameteric type implementing class Functor
is a category functor mapping Hask to one of its subcategory, where types m a
are the object collection. The type constructor m
maps objects, and specific fmap
defined on m
maps corresponding functions.
It’s worth noted that (a > b) > m a > m b
can also read as (a > b) > (m a > m b)
, as >
is rightassociative. This may provide a clearer view of fmap
, which takes a regular function in Hask and returns the corresponding function in subcategory.
Examples:
fmap (+) :: List[Int] > List[Int]
generates elementwise addition in List[Int]
.
fmap (+) :: Maybe Int > Maybe Int
generates such function:

