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
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
We won't see what happens when a category is large for the moment.
Example : combining
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.
SafeTail :: [a] → Maybe [a]It returns a list
Nothingif the list is empty (
Nothingis like an exception code).
SafeTail  = Nothing SafeTail (x:xs) = Just xs
xis the head of the list, of type
xsis the tail of the list, of type
We have applied two functors, one on top of an other. We have composed the
Maybefunctor after the
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
mis :: Maybe[Int] sq :: Int → Int
fmapgoes under the functor and applies. Here under
List, so to apply
sqwe must use
fmapto this list.
fmap(fmap sq) misThis goes to two layers of containership.
Could be written
(fmap.fmap) sq mis
BifunctorsMost 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 categoriesA product of two types is a pair
(a, b). Could be rewritten as a type constructor acting on
(,) a bIf we fix
a, is it a functor in
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 Dare 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 Dis 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 bas 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 categoriesWe 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
Cartesian categoriesA 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
f a = a'and
f b = b'.
We can also construct a product for
b'. To show that it's a bifunctor we must show that we can lift
gto something that goes from
In Haskell it was easy, we just applied
band 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
b'; there are two projections from
f o pand
g o q.
Here the real product of
(a', b')and the fake candidate is
From the universal construction we know that there is a unique arrow from
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.