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 -> Band
g: B -> Care morphisms,
f.ggenerates a new morphism
A -> C.
Note that a morphism has no specific semantics of mapping, but simply links two objects together. Morphisms are also called Arrows.
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.
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 -> Band
g: B -> C, there must be a
h: A -> Csatisfying
h = f . g.
- For each object
A, there should exist an identity morphism
id(A): A -> As.t. for every
f: A -> B,
f = id(A) . f = f . id(B).
- There may exist serveral morphisms between
- 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 element-wise addition as
Int does, and
Maybe[Int] should have similar operations with no burden of re-wrapping and unwrapping. Such 'inheritance' is only concerned with the structure of types, instead of specific functions, so should be done automatically if possible.
Haskell language itself forms a category, with all types being objects, and functions being morphisms. Such category is called Hask.
class Functor m where fmap :: (a -> b) -> m a -> m b
A parameteric type implementing class
Functor is a category functor mapping Hask to one of its sub-category, 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 right-associative. This may provide a clearer view of
fmap, which takes a regular function in Hask and returns the corresponding function in sub-category.
fmap (+) :: List[Int] -> List[Int] generates element-wise addition in
fmap (+) :: Maybe Int -> Maybe Int generates such function:
maybePlus :: Maybe Int -> Maybe Int maybePlus _ Nothing = Nothing maybePlus Nothing _ = Nothing maybePlut (Just x) (Just y) = Maybe (x + y)