Functors

Having two categories $C$ and $D$, can we take objects and morphisms from $C$ and map them to objects and morphisms in $D$? A functor is just that, a mapping between categories.

Functor laws

There are laws though, we can’t just map things at random.

Functors preserve composition

Let $f : a \to b$ and $g : b \to c$ two arrows in $C$.

$$F(g \circ f) = F(g) \circ F(f)$$

Functors preserve identity

$$F(id_a) = id_F$$

Functors in Haskell

When programming with Haskell, we’re working with only the category of all Haskell types, called Hask, so our functors look more like $F : Hask \to Hask$ – notice that the source and target categories are the same.

An object in Hask is just a type (e.g. Int, Bool, Char, and so on). Our functor $F$, when mapping Hask objects, will be a mapping between two types – $Type \to Type$. These mappings are just type constructors with arguments.

e.g. Maybe a : Type -> Type takes a type as an argument maps it to another type. Taking a concrete example, Maybe a maps the type Int : Type to Maybe Int : Type.

So we can see that mapping of objects is handled by type constructors with parameters. Our next stop is mapping morphisms, which in Hask are just functions.

What does it mean to map a function? Having a -> b, we want to map it to a function F a -> F b. This is encoded by the Functor type class:

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

Example of functors in Haskell

Let’s consider the object Int, and the arrow Int -> Char, both from Hask.

Maybe

data Maybe a = Nothing | Just a

Object Int maps to Maybe Int by the type constructor.

Arrow Int -> Char maps to Maybe Int -> Maybe Char by fmap

Reader

type Reader r a = r -> a

Notice how reader has two arguments. A functor always takes a single argument, so Reader is a functor only in its last argument.

Also note that Reader r a is the “same” as a function r -> a.

Object Int maps to Reader r Int, a function r -> Int.

Arrow Int -> Char maps to Reader r Int -> Reader r Char, a function (r -> Int) -> (r -> Char)

Const

data Const c a = Const c

This type is the same as just having a value c. Notice that a appears only at the type level.

Object Int maps to Const c Int, always the value c.

Arrow Int -> Char maps to Const c Int -> Const c Char, always a function c -> c.

So Const completely ignores a at the value level and maps everything to c.

Functor composition

Having two functors $F : B \to C$ and $G : A \to B$, we can compose them, gaining another functor $F \circ G : A \to C$.

In Haskell, this is defined by the Compose data type and its Functor instance.

Compose (f g : Type -> Type) (a : Type) = Compose (f (g a))

A function a -> b maps to Compose f g a -> Compose f g b, which is the same thing as f (g a) -> f (g b).

Functor composition is associative

Consider three functors $F : C \to D$, $G : B \to C$ and $H : A \to B$.

$$F \circ (G \circ H) = (F \circ G) \circ H$$

Functor composition preserves identity

$$F \circ Id = F$$