7.1: Functoriality, bifunctors | Categories Bartosz Milewski Youtube notes

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 ? Product as functor

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. Product of categories

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'. Bifunctor product

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.