# Haskell 笔记：Category Theory and Functor

## Category Theory

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 -> 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 that a category should obey:

- Composition should be associative.
- Composition operation should be enclosed 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 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.

## 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 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.**

## 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)

Author:hsfzxjy.Link:.License:CC BY-NC-ND 4.0.

All rights reserved by the author.

Commercial use of this post in any form isNOTpermitted.

Non-commercial use of this post should be attributed with this block of text.

## OOPS!

A comment box should be right here...But it was gone due to network issues :-(If you want to leave comments, make sure you have access to disqus.com.