Haskell 笔记：Category Theory and Functor

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 and g: B -> C are morphisms, f.g generates 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.

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 and g: B -> C, there must be a h: A -> C satisfying h = f . g.
• For each object A, there should exist an identity morphism id(A): A -> A s.t. for every f: A -> B, f = id(A) . f = f . id(B).

Note that:

• There may exist serveral morphisms between A and B.
• 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.

Hask Category

Haskell language itself forms a category, with all types being objects, and functions being morphisms. Such category is called Hask.

Hask Functors

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.

Examples:

fmap (+) :: List[Int] -> List[Int] generates element-wise addition in List[Int].

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)