From Category Theory for Programmers - Series 1

Category Theory 7.1 - Functoriality, bifunctors

• If a category is small (a set), it's actually a function
• Functor preserves structure on hom-sets
• Functor preserves composition and identity
• Functors can be composed for mappings between categories
• Functor can be morphism between categories, where categories are objects
• This is the category Cat
• For now, Cat is technically limited to small categories, dealing with large categories is more complicated and addressed later
• Composition of functors in Haskell

tail :: [a] -> [a]
-- | but tail doesn't check if the list is empty
safeTail :: [a] -> Maybe [a]
-- | definition for empty
safeTail  [ ] = Nothing
-- | with a list
safeTail (x * xs) = Just xs

• So maybe list is a composition of functors
• How to apply another function, square, on this composition?

-- | list of maybe ints
mis :: Maybe [int]
-- | square function
sq :: Int -> Int
-- | fmap is then
fmap (fmap sq) mis

• Composing functors in Haskell is composing fmaps
• Algebraic structures are automatically "functorial"
• Is a product a functor?
• A product is just a pair (a,b)
• Fixing one argument is easy to show it's a functor
• But is it a functor in two arguments?
• Define a functor that acts on two categories (for small categories)
• Then take two categories C,D
• And give cartesian product of objects
• Which also take cartesian pairs of morphisms
• And give cartesian pairs of compositions
• So then functors can be given from a product of categories to a different category
• C ⨯ D → E
• Called a bifunctor

class Bifunctor f where
-- | needs to lift two functions at the same time
-- | corresponds to fmap
bimap :: (a -> a`) -> (b -> b`) -> (f a b -> f a` b`)

• In a category, if a product is defined for every pair of objects, it is a cartesian category
• Additionally, C ⨯ C → C is a bifunctor
• The same is true for coproduct (i.e., also a bifunctor)
• Categories with a bifunctor are called monoidal categories (which also have a Unit)

(part 2 Category Theory 7.2 - Monoidal Categories, Functoriality of ADTs, Profunctors)

• Defining multiplication on objects in a category
• Must have Unit
• Category Unit is a terminal object
• If multiplication is defined, and there is a terminal object, this is a monoidal category
• Coproduct is the same, except with initial object
• Monoidal category has a tensor product ⊗ (product or coproduct) and unit, usually written as 1
• Const functor ∆_c takes any type 'a' and maps it into a single type 'c'

-- | map any type a to type c
data Const c a = Const c
instance Functor (Const c) where
    -- | fmap :: (a -> b) Const c a -> Const c b
    fmap f (Const c) = Const c
data Identity a = Identity a
    fmap f (Identity a) = Identity (f a)
 
-- | can be used to define any type constructor
data Maybe a = Nothing | Just a
    Either () (Identity a)
    -- | same as
    Either Const () a (Identity a)

• Functor that works in the opposite category

 
class Contravariant f where
    contramap :: (b -> a) -> (f a -> f b)

• Haskell arrow is a profunctor
• Profunctor
• C^op ⨯ C → C

class Profunctor p where
    dimap :: (a` -> a) -> (b -> b`) -> p a b -> p a` b`