## 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} $