# Functoriality Chapter 8 --- ### Functoriality - Functors are morphisms in Cat -- intuitions about functions apply to functors -- functor can have 2 arguments too: bifunctor --- ### Bifunctor - Maps objects from category C and D to E: -- Cartesian product`C⨯D` to `E`  ---- ### Bifunctor Has to map morphisms as well Pair of morphisms is a single morphism in `C⨯D` - can be composed: ```= (f, g) ∘ (f', g') = (f ∘ f', g ∘ g') ``` - and has identity: ```= (id, id) ``` So a cartesian product of categrories is a category ---- ### Bifunctor Can be considered functor in each argument - this is not enough to prove joint functoriality -- when this fails the category is premonoidal ---- ### Bifunctor Haskell bifunctor typeclass ```haskell= class Bifunctor f where bimap :: (a -> c) -> (b -> d) -> f a b -> f c d bimap g h = first g . second h first :: (a -> c) -> f a b -> f c b first g = bimap g id second :: (b -> d) -> f a b -> f a d second = bimap id ``` Example implementation ```haskell= instance Bifunctor (,) where bimap f g (x, y) = (f x, g y) ``` ---- ### Bifunctor `bimap` maps 2 functions at once  ---- ### Bifunctor `first` only maps the first function; `second` only the second   ---- ### Bifunctor `first ∘ second` should return the same thing as `second ∘ first`  --- ### Product and coproduct bifunctors categorical product - If product exists for any pair of objects, the mapping is bifunctorial ```haskell= instance Bifunctor (,) where bimap f g (x, y) = (f x, g y) ``` ---- ### Product and coproduct bifunctors By duality, a coproduct is also a bifunctor ```haskell= instance Bifunctor Either where bimap f _ (Left x) = Left (f x) bimap _ g (Right y) = Right (g y) ``` --- ### Functorial ADTs - ADTs are created from sums and products -- which are functorial -- and functors compose - If we can show the building blocks of ADTs are functorial we know the ADTs are functorial too ---- ### Functorial ADTs What are these building blocks? - Items that have no dependency on the type parameter -- like `Nothing` in `Maybe` or `Nil` in `List` -- These are the equivalent to `Const` functor - Items that encapsulate the type parameter -- like `Just` in `Maybe` -- These are equivalent to `Identity` ---- ### Functorial ADTs Definition of Identity ```haskell= data Identity a = Identity a ``` ```haskell= instance Functor Identity where fmap f (Identity x) = Identity (f x) ``` ---- ### Functorial ADTs Everything else is constructed from these two primitives using products and sums: ```haskell= data Maybe a = Nothing | Just a ``` is a sum of 2 types: - `Nothing` can be represented as `Const () a`, partially applied - `Just` is a different name for `Identity` ---- ### Functorial ADTs - `Maybe` is a composition of `Either` with two functors ```haskell= type Maybe a = Either (Const () a) (Identity a) ``` - Composition of functors is a functor - to show this is true for bifunctor we need to see how this composition works on morphisms ---- ### Functorial ADTs Define the combination of bifunctor with functors as arguments ```haskell= newtype BiComp bf fu gu a b = BiComp (bf (fu a) (gu b)) ``` - `BiComp` is bifunctor in `a` and `b` if -- `bf` is a bifunctor -- `fu` and `gu` are functors ---- ### Functorial ADTs There must be a `bimap` for this combination: ```haskell instance (Bifunctor bf, Functor fu, Functor gu) => Bifunctor (BiComp bf fu gu) where bimap f1 f2 (BiComp x) = BiComp ((bimap (fmap f1) (fmap f2)) x) ``` ---- ### Functorial ADTs Used with `Either`, `Const` and `Identity`: ```haskell= BiComp (Either (Const ()) (Identity b)) ``` bimapping this with `f` and `g` will return ```haskell= BiComp (Either (Const ()) (Identity(g b))) ``` ---- ### Functorial ADTs We didn’t have to prove that Maybe was a functor - this fact follows from the fact it was constructed out of functorial primitives --- ### Writer functor ```haskell= type Writer a = (a, String) ``` - Just a simple product type -- we don’t even have to implement `fmap` for it ---- ### Writer functor Being a category it needs - Composition ```haskell= (>=>) :: (a -> Writer b) -> (b -> Writer c) -> (a -> Writer c) m1 >=> m2 = \x -> let (y, s1) = m1 x (z, s2) = m2 y in (z, s1 ++ s2) ``` - Identity ```haskell= return :: a -> Writer a return x = (x, "") ``` ---- ### Writer functor Identity and composition can be used to define `fmap` ```haskell= fmap f = id >=> (\x -> return (f x)) ``` ---- ### Writer functor - As long as `>=>` operator and `return` are defined you can define `fmap` as well - When there is an implementation of `fmap` for a type constructor which preserves identity `fmap` is unique --- ## Covariant and contravariant functors