Understanding Monad 2 - Category and Functor

Category and Higher Order Type

A category $C$ consists of two parts:

  • a class $ob(C)$ of objects

  • a class $hom(C)$ of morphisms between the objects

Each morphism map from a object to another object in $C$, for example, $f : a \rightarrow b$ maps from $a$ to $b$.

The composition of two morphisms $f : a \rightarrow b$ and $g : b \rightarrow c$ can be written as $g \circ f$, and the result of $g \circ f$ is another morphism $h : a \rightarrow c$.

From a programmatic view, we can simply regard a category as a higher order type (or say higher kinded type). For example, in Scala, List is a category, and is also a higher order type because it accepts other types as parameters. List[T] takes a proper type and produces another type such as List[Int] or List[String], so Int, String are objects as correspondence to $ob(List)$.

Functor

Like a function maps from a proper type to another proper type, a functor maps from a category to another category.

Assume $A$ and $B$ are two categories, and we have a functor $F$ which maps $A$ to $B$, which

  • maps every object $X$ in $A$ to $F(X)$ which belongs to $B$

  • for each morphism $f:X \rightarrow Y$ in $A$, $F$ maps it to a morphism $F(f):F(X)\rightarrow F(Y)$

  • for every object in $A$, $ F(id_{X}) = id_{F(X)} $

  • for morphism $f: X \rightarrow Y$ and $g: Y \rightarrow Z$ in $A$, $F(g \circ f) = F(g) \circ F(f) $

In Scala, we can express functor as a trait:

trait Functor[F[_]] {
    def fmap[A,B](fa: F[A], f: A => B): F[B]
}

f is a higher order type, which can take a proper type. fmap takes two arguments, it maps a container fa with proper type A to a containter with type B by using f to transform every value in fa with type A to type B.

Functor Category

Functor category is a kind of category where the objects are functors, and the morphisms are natural transformations (functor to functor). The objects in the functor category are functors, which maps a category to another category.

Natural Transformations

Natural transformation is a way to transform a functor to another functor, while respect the internal structure of categories.

Assume that $C$ and $D$ are categories, and $F$ and $G$ are functors between $C$ and $D$. A natural transformation $\eta$ from $F$ to $G$ has following properties:

  • for each object $X$ in $C$ has a morphism between $C$ and $D$: $ \eta_{X} : F(X) \rightarrow G(X) $. The morphism $\eta_{X}$ is called the component of $\eta$ at $X$.

  • for every morphism $f : X \rightarrow Y$ we have $ \eta_{Y} \circ F(f) = G(f) \circ \eta_{X} $