Functors
Definitions
Let \(\mathbf{C}\) and \(\mathbf{D}\) be 2 categories. A mapping \(F: \mathbf{C} \Rightarrow \mathbf{D}\) between the categories is called functor if it preserves the internal structure (see Functor):
\(\forall a_C \in \mathrm{ob}(\mathbf{C}), \exists a_D \in \mathrm{ob}(\mathbf{D})\) such that \(a_D = F( a_C )\)
\(\forall f_C \in \mathrm{hom}(\mathbf{C}), \exists f_D \in \mathrm{hom}(\mathbf{D})\) such that \(\operatorname{dom}f_D = F (\operatorname{dom}f_C), \operatorname{cod}f_D = F (\operatorname{cod}f_C)\). We shall use the following notation later: \(f_D = F(f_C)\).
\(\forall f_C, g_C\) the following equation holds: \[F\left(f_C \circ g_C\right) = F\left(f_C\right) \circ F\left(g_C\right) = f_D \circ g_D.\]
\(\forall x \in \mathrm{ob}(\mathbf{C}): F(\mathbf{1}_{x \to x}) = \mathbf{1}_{F(x) \to F(x)}\).
When we say that a functor preserves internal structure we assume that the functor is not just mapping between Objects but also between Morphisms.
Thus a functor is something that allows us to map one category into another. The initial category can be considered as a pattern thus the mapping is some kind of search for the pattern inside another category.
Programming languages can be considered as a good platform for the functor examples. The functor can be defined in Haskell as follows. 1
class Functor f where
fmap :: (a -> b) -> f a -> f bIn Scala it can be defined in the same way.
trait Functor[F[_]] {
def fmap[A, B](f: A => B): F[A] => F[B]
}In C++ the definition differs.
In C++ templates can be considered as type constructors
in Haskell and therefore can convert one type to another. For instance
the list of strings can be obtained with the following construction:
using StringList = std::list<std::string>;
StringList a = {"1", "2", "3"};i.e. we have Objects mapping out of the box. Therefore we need to define fmap operation for Morphisms mapping to complete the Functor definition. It can be declared as follows:
template < template< class ...> class F, class A, class B>
F<B> fmap(std::function<B(A)>, F<A>);The template specialization for the std::list can be written as follows.
// file: functor.h
template <class A, class B>
std::list<B> fmap(std::function<B(A)> f, std::list<A> a) {
std::list<B> res;
std::transform(a.begin(), a.end(), back_inserter(res), f);
return res;
}The simple usage example is the following.
StringList a = {"1", "2", "3"};
std::function<int(std::string)> f = [](std::string s) {
return 2 * atoi(s.c_str());
};
auto res = fmap<>(f, a);Let \(\mathbf{C}\) be a Category. The Functor \(E: \mathbf{C} \Rightarrow \mathbf{C}\) i.e. the functor from a category to the same category is called endofunctor.
Let \(\mathbf{C}\) is a Category. The Functor \(\mathbf{1}_{\mathbf{C} \Rightarrow \mathbf{C}}: \mathbf{C} \Rightarrow \mathbf{C}\) is called identity functor if for every object \(a \in \mathrm{ob}(\mathbf{C})\) \[\mathbf{1}_{\mathbf{C} \Rightarrow \mathbf{C}}(a) = a\] and for every Morphism \(f \in \mathrm{hom}(\mathbf{C})\) \[\mathbf{1}_{\mathbf{C} \Rightarrow \mathbf{C}}(f) = f\]
First of all notice that Identity functor is an Endofunctor.
There is difference between identity functor and Identity morphism because the first one has deal with both Objects and Morphisms while the second one with the objects only.
If we have 3 categories \(\mathbf{C}, \mathbf{D}, \mathbf{E}\) and 2 functors between them: \(F: \mathbf{C} \Rightarrow \mathbf{D}\) and \(G: \mathbf{D} \Rightarrow \mathbf{E}\) then we can construct a new functor \(H: \mathbf{C} \Rightarrow \mathbf{E}\) that is called functor composition and denoted as \(H = G \circ F\). The functor is defined for Objects as follows: \[H(a) = G(F(a))\] and for Morphisms as follows: \[H(f) = G(F(f)).\]
Cat category
The Functor composition is associative by definition. Therefore Identity functor with the associative composition allow us to define a category where other categories are considered as objects and functors as morphisms:
The category of small categories (see Small category) denoted as \(\mathbf{Cat}\) is the Category where objects are small categories and morphisms are Functors between them.
We can construct an extension of Cartesian product as follows
If we have 2 categories \(\mathbf{C}\) and \(\mathbf{D}\) then we can construct a new category \(\mathbf{C} \times \mathbf{D}\) with the following components:
Objects are the pairs \((c,d)\) where \(c \in \mathrm{ob}(\mathbf{C})\) and \(d \in \mathrm{ob}(\mathbf{D})\)
Morphisms are the pair \((f,g)\) where \(f \in \mathrm{hom}(\mathbf{C})\) and \(g \in \mathrm{hom}(\mathbf{D})\)
Composition is defined as follows \((f_1, g_1) \circ (f_2, g_2) = (f_1 \circ f_2, g_1 \circ g_2)\)
Identity is defined objectwise as follows: \(\mathbf{1}_{(c,d) \to (c,d)} = \left(\mathbf{1}_{c \to c}, \mathbf{1}_{d \to d}\right)\)
Let consider a trivial functor \(\Delta_c\) from Category \(\mathbf{A}\) to category \(\mathbf{C}\) such that \(\forall a \in \mathrm{ob}(\mathbf{A}): \Delta_c a = c\) -fixed object in \(\mathbf{C}\) and \(\forall f \in \mathrm{hom}(\mathbf{A}): \Delta_c f = \mathbf{1}_{c \to c}\). The trivial functor is called constant functor.
Empty category is the Initial object in \(\mathbf{Cat}\) category ((https://math.stackexchange.com/users/301130/user84563), n.d.).
Trivial category is the Terminal object in \(\mathbf{Cat}\) category.
The good example can be found in \(\mathbf{Hask}\) category.
data Const c a = Const c
fmap :: (a -> b) -> Const c a -> Const c b
fmap f (Const c a) = Const cContravariant functor
Ordinary functor preserves the direction of morphisms and often called as Covariant functor. The functor that reverses the direction of morphisms is called as Contravariant functor.
If we have categories \(\mathbf{C}\) and \(\mathbf{D}\) then the ordinary Functor \(\mathbf{C} \Rightarrow \mathbf{D}\) is called covariant functor.
If we have categories \(\mathbf{C}\) and \(\mathbf{D}\) then the Functor \(\mathbf{C^{op}} \Rightarrow \mathbf{D}\) is called contravariant functor.
Function mapping inside a functor is made via fmap (see Functor) but sometimes the function that has to be mapped is a -> b but the result mapping has an inverse order: f b -> f a. In the case the contravariant functor can help
class Contravariant f where
contramap :: (a -> b) -> f b -> f aThe contravariant functor should follow the following laws
contramap id = id
contramap f . contramap g = contramap (g . f)Consider the following task. We have a predicate for Int type that returns True if the number is greater than 10 otherwise it returns False:
newtype Predicate a = Predicate { runPredicate :: a -> Bool}
intgt10 :: Predicate Int
intgt10 = Predicate ( \i -> i > 10 )Now we want to create a predicate that accepts a string and verify it length greater than 10 or not. I.e. we want to have something of the following type:
strgt10 :: Predicate StringIn the case the Contravariant functor helps.
instance Contravariant Predicate where
contramap f (Predicate p) = Predicate ( p . f )
strgt10 :: Predicate [Char]
strgt10 = contramap length intgt10Bifunctors
Bifunctor is a Functor whose Domain is a Category Product. I.e. if \(\mathbf{C_1}, \mathbf{C_2}, \mathbf{D}\) are 3 categories then the Functor \(F: \mathbf{C_1} \times \mathbf{C_2} \Rightarrow \mathbf{D}\) is called bifunctor.
Lets \(A,B,C\) and \(D\) are sets and \(f: A \to C, g: B \to D\) are two Functions. Then the Cartesian product with Product of morphisms form a Bifunctor \(\times\).
In \(\mathbf{Hask}\) the Either type constructor has 2 arguments, and both arguments can be mapped independently.
data Either a b = Left a | Right b
class Bifunctor p where
bimap :: (a -> c) -> (b -> d) -> p a b -> p c d
instance Bifunctor Either where
bimap f _ (Left a) = Left (f a)
bimap _ g (Right b) = Right (g b)Thus the first function changes the Left value and the second function changes the Right value.
If we have categories \(\mathbf{C}\) and \(\mathbf{D}\) then the Bifunctor \[\mathbf{C^{op}} \times \mathbf{D} \Rightarrow \mathbf{Set}\] is called profunctor. It is contravariant by the first argument and covariant by the second one.
In \(\mathbf{Hask}\) we can think about a profunctor as a type constructor with 2 arguments. The first argument is contravariant and the second one is covariant.
class Profunctor p where
dimap :: (a' -> a) -> (b -> b') -> p a b -> p a' b'
instance Profunctor (->) where
dimap f g h = g . h . fThe function arrow is the simplest example. If \(h: a \to b\), then dimap converts it into \(a' \to b'\) by composing it with \(f: a' \to a\) and \(g: b \to b'\).