# 7.1: Functoriality, bifunctors

## The category `Cat` Functor composition is easy to define. As functors are defined in terms of functions (in small categories), it just follows the rules of function composition.
As each functor preserves structure, the composition also preserves structure.
The composition of functors `F` and `G` is noted `G o F`.

The identity functor maps everything to itself. It is necessarily an endofunctor. It is an identity with respect to composition of functors.

Whatever we know about function composition applies to functor composition : associativity, identity...
So it is a category in which functors are morphisms and categories are objects.
Such a category is called `Cat`.
We won't see what happens when a category is large for the moment.

### Example : combining `Maybe` and `List`

This is useful, for example for function
`tail :: [a] → [a]`
which throws away the first element of a list.
It is not defined for empty list.
Let's define
`SafeTail :: [a] → Maybe [a]`
It returns a list `[a]` or `Nothing` if the list is empty (`Nothing` is like an exception code).
```SafeTail [] = Nothing
SafeTail (x:xs) = Just xs
```
`x` is the head of the list, of type `a`.
`xs` is the tail of the list, of type `[a]`.

We have applied two functors, one on top of an other. We have composed the `Maybe` functor after the `List` functor.
So `Maybe List`, a composition of two functors, is also a functor.

How to apply the function square to the contents of this `Maybe List` ? We could implement dealing with all the particular cases (`Nothing`), but we have already defined the functions `fmap`.
```mis :: Maybe[Int]
sq :: Int → Int
```
`fmap` goes under the functor and applies. Here under `Maybe` is a `List`, so to apply `sq` we must use `fmap` to this list.
`fmap(fmap sq) mis`
This goes to two layers of containership.
Could be written
`(fmap.fmap) sq mis`

## Bifunctors

Most type constructors in Haskell are functors. All the algebraic data structures are automatically functorial. Algebraic data structures are formed using products or sums, applied to unit or void or a type variable.

### Product of categories

A product of two types is a pair `(a, b)`. Could be rewritten as a type constructor acting on `a` and `b` :
`(,) a b`
If we fix `a`, is it a functor in `b` ? `fmap f(e, x) = (e, fx)`
By the same way we can show that it's also functorial in the first argument.

But is it functorial in both arguments at the same time, a functor that takes two types and produces a third type ?

We can do this by defining a product of two categories. Then a functor from a product to a category would be equivalent to a functor with two arguments. We do the same with functions : a function with two arguments is a function that takes a pair as argument.

The product of small categories is easy to define.
Objects in small categories form sets, we can define the product of two categories as a category containing the pairs ; a simple cartesian product of two sets. The product is noted `C x D`
Hom-sets also form sets, so the morphisms can also be paired. The morphisms of `C x D` are formed by cartesian product of two hom-sets.
Composition of morphisms can be easily defined : `(f', g') o (f, g) = (f' o f, g' o g)`
Associativity is obvious.
The identity can be defined as `id (a, b) = (id a, id b)`
`C x D` is therefore a category.

So it is possible to define a functor `C x D → E`.
It maps a pair of objects to an object and a paire of morphisms to a morphism.
Such a functor is called a bifunctor.

In Haskell we are in the category of types, so it's a functor `C x C → C`
In terms of types and functions, this is a mapping from two types to a type, and from a pair of functions to a function.
We are lifting two functions at the same time.
```class Bifunctor f where
bimap :: (a → a') → (b → b') → (f a b → f a' b')
```
The compiler sees that f is acting on two types and then knows that is has two types as arguments.

In particular, we can define the product
`(,) a b`
as a bifunctor. Fixing the first or the second argument can be done by using an identity as one of the functions `(a → a')` or `(b → b')`.

### Sums of categories

We can also use a bifunctor for the sum.
The canonical sum type of two types, `Either a b`, is a bifunctor. We can define the action of two functions on `Either a b`. It takes two types, a pair from a product, and produces a third type, `Either a b`. The first function will be applied to `a`, the second will be applied to `b`.

### Cartesian categories

A category where the product is defined for any pair of objects is called a cartesian category.
In a cartesian category, this product is a bifunctor of `C x C → C`.
The same is true for coproduct.

We are in a cartesian category, so the product is defined for any pair `(a, b)`.
Morphisms `f` and `g` such as `f a = a'` and `f b = b'`.
We can also construct a product for `a'` and `b'`. To show that it's a bifunctor we must show that we can lift `f` and `g` to something that goes from `(a, b)` to `(a', b')`.
In Haskell it was easy, we just applied `f` to `a` and `g` to `b` and had this mapping.
In the general case, the definition of a product is the universal construction, which says that if we have a candidate for the product, there is a unique morphism from this candidate and the actual product.
Let's think at `(a, b)` as a candidate for the product of `a'` and `b'` ; there are two projections from `(a, b)` to `a'` and `b'` : `f o p` and `g o q`.
Here the real product of `a'` and `b'` is `(a', b')` and the fake candidate is `(a, b)`.
From the universal construction we know that there is a unique arrow from `(a, b)` to `(a', b')`.
This gives us our lifting, we call it `f x g`.

The same kind of analysis works also for the coproduct in the opposite category.
A category where the coproduct is a bifunctor is called a cocartesian category.

Categories who have a bifunctor like this are called monoidal categories ; but to be monoidal, they also need to have a unit.