From Category Theory for Programmers - Series 1

Category Theory 6.1 - Functors

• Functor is a mapping from one category to another
• Discrete category
• Has no morphisms except those required (id)
• Has no structure
• Can take a set and represent it as a discrete category
• A functor mapping objects between two categories also should preserve morphisms between objects into the new category (otherwise it isn't a functor)
• A functor defines a mapping of hom-sets between categories
• A functor preserves composition
• For a→b→c given by 𝑓,𝑔, and a→c by 𝑔 ∘ 𝑓, then a functor F maps
• 𝑓 to F𝑓
• 𝑔 to F𝑔
• 𝑔 ∘ 𝑓 to F(𝑔 ∘ 𝑓) which must equal F𝑔 ∘ F𝑓 (otherwise it isn't a functor)
• Functor doesn't have to be injective or surjective, but it must preserve structure
• Things connected in starting category are also connected in mapped category
• "Faithful" functor is injective on all hom-sets (but not necessarily objects)
• "Full" functor is surjective on all hom-sets (but not necessarily objects)
• Fully faithful functor is an isomorphism
• A functor that collapses all objects into a single object
• All morphisms collapse to id
• Called ∆c where c is the object collapsed into
• Functor doesn't have to map to a different category. If it maps back into the same category, it's an "endofunctor"
• What does this have to do with programming?
• In Haskell, endofunctors are just called functors because there's really only one category
• A functor has to be a mapping of types (generic, template, etc)
• But also has to map functions
• How to define on mapping of functions
• (Haskell)
• data Maybe a = Nothing | Just a
• fmap f
• fmap f is a function that takes 'a' to 'b' that produces a 'Maybe a' to a 'Maybe b'
• fmap :: (a→b) → (Maybe a → Maybe b)
• fmap f Nothing = Nothing
• fmap f (Just x) = Just (f x)
• id x = x

• Need to know if the functor preserves identity
• fmap id = id
• Need to know if structure is preserved, that is
• fmap (𝑔 ∘ 𝑓) = fmap 𝑔 ∘ fmap 𝑓
• In Haskell, every function definition is an equation (left side = right side)
• Basically, inlining
• Only works with pure functions (Haskell vs c++)
• Testing out preservation:
• fmap id Nothing = Nothing ...
• fmap id Nothing = Nothing = id Nothing
• fmap id (Just x) = ...
• fmap id (Just x) = Just (id x) = Just x
• id (Just x) = Just x
• Types obtained by endofunctors are obtained by "lifting"
• Can't just write one formula for fmap that works for all functions
• Haskell has "typeclass" similar to Interface

class Eq a where 
    (==) :: a -> a -> Bool

• 'a' is a member
• Takes two 'a's, produces a Bool
• This is ad hoc polymorphism, parameterized by a type
• In class, same mechanism works for types and type structures

class Functor f where 
    fmap :: (a -> b) -> (f a -> f b)

• So f can work on types, a type constructor
• Most intuitive example of a functor is a list
• data List a = Nil | Cons a (List a)
• Type constructor
• Takes an arbitrary type and creates a list of types

instance Functor List where 
    fmap f Nil = Nil
    fmap f (cons h t) = Cons (f h) (fmap f t)

• Says List is an instance of Functor
• h,t are "head", "tail"
• Definition of 'map'

type Reader r a = r -> a
fmap :: (a -> b) -> (r -> a) -> (r -> b)
fmap f g = 𝑓 ∘ 𝑔 = (∘) f g

• Functor takes type a and maps (r -> a)
• Currying (aka partial application)
• endofunctors might be considered containers
• List contains a bunch of elements
• Sometimes run into problems with this comparison though ...
• Data types and functions are sort of inter related ...
• Infinite list, evaluates, returns a value
• What really matters is that it can be applied onto something