A category consists of three parts:
- A collection of objects.
- A collection of morphisms, each of which map one object to another.
- A composition operator 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.
All sets and standard functions form a category. Functions need not to be surjective, since morphisms have no mapping semantics.
All groups and homomorphisms between groups form a category. A group has specific algebaric structure, which morphisms should preserve.
Three laws that a category should obey:
- Composition should be associative.
- Composition operation should be enclosed 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.
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 trivial functor from Grp to Set, which maps groups to their underlying sets, and group morphisms to functions with same behavior but defined on sets instead of groups.
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 expect derived 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’ should be done automatically if possible, since it is only concerned with the structure of types instead of specific functions.
Haskell language itself forms a category, with all types being objects, and functions being morphisms. Such category is called Hask.
class Functor m where
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