Monads Part 1 (Functors)

Journey Overview

Time and time again, the uncultured programmer stumbles upon the wild world of category theory.
Every time, his mind ravages itself to comprehend what lies before his eyes. Each acknowledgment of the words “functor” and “monad” brings out fresh sharp pangs into the frontal lobe. As days drag into years, the programmer sinks into despair and swallowed by his own ignorance. Another one bites the dust.

Upon careful consideration, let’s not follow in those footsteps. Instead, we will reach our own enlightenment by building up our own theory and understanding on the connections between category theory and functional programming starting from Categories and Functors.

Category Theory Introduction

A category is defined very minimally: there exists objects and arrows.
Objects are what they sound like, just things to be acted upon.
Arrows connect the objects in a category.
If objects \(a\) and \(b\) exist in a category, then there may be no arrows, one arrows, or many arrows between them.

The laws in a category and also described minimally.
1.) For every object \(a\) in a category, there must exist some arrow labelled \(id_a\) which represents the identity arrow for that object.
2.) Arrows can be composed associatively to generate new arrows.
i.e. if \(f\) is an arrow from object \(a\) to \(b\) and \(g\) is an arrow from objects \(b\) to \(c\), then there must be an an arrow \(f\circ g\) from \(a\) to \(c\).
The identity arrow defined earlier interacts with other arrows in the obvious way: \(id \circ f = f\) and \(g\circ id = g\)

Based on these definitions, it may seem like objects are sets and arrows are just functions on those sets.
For categories that we are already familiar with, this is the case, but for generic categories, the objects may not be sets. It may very well be that the objects we are analyzing are sets, but we do not know that. In the world of category theory, we can only define things with objects, arrows, and the behaviors of these primitives.

A Functor is some mapping between categories that maintains the structure of the categories.
If \(F\) is a functor from category \(X\) to category \(Y\), then \(F\) maps objects of \(X\) to objects of \(Y\).
\(F\) also maps arrows to arrows, but must respect the laws of categories.
i.e. \(F(id_a) = id_{F(a)}\) and \(F(f\circ g) = F(f)\circ F(g)\)
Functors can be thought of as category homomorphisms.

So far so good, but what is the point of all this?
It turns out that numerous reoccurring ideas across mathematics can be codified using the language of category theory. The ideas are so general, we have resorted to talking about objects with no properties and arrows that mimic, but are not quite functions.

Programming with Functors

When we discuss category theory in the context of functional programming, we typically refer to a specific category at first: \(\mathcal{H}\) or \(Hask\), which is the category of the types in a (functional) programming language’s type system. (Haskell is the preferred language for these discussions, so we will use that, but the ideas are easily transferable.)
The arrows here are just normal deterministic functions that we’re all familiar with and arrow composition is just function composition.
i.e. Int and String are objects in this category and the length function is a specific arrow from object String to object Int. It should also be easy to confirm that the identity arrow exists for each object and that arrows compose as they should.

Now let’s take a look at how a programming functor is defined:

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

The functor f is actually a type constructor, which upon taking a certain type a, returns a new type f a. The functor also has a accompanying function fmap that converts a function of type a -> b to a function of type f a -> f b. Not specified in the definition, the programming functor should also satisfy the functor laws:
1.) fmap id = id
2.) fmap (f . g) = fmap f . fmap g

Thinking back to our mathematical definition of a functor, the similarities gradually become apparent. Our functor f converts an object like Int to f Int and converts a function like length to some function of type f String -> f Int via the fmap function. These mappings correspond with the mapping on objects and arrows that a normal categorial functor would do.
The programming functor laws also correspond with the rules that guide categorical functors.
Unlike mathematical functors, however, the categories that the programming functors maps from and to are fixed: \(\mathcal{H}\).

Functions as Functors

Some common examples of existing functors are Maybe a and [a], but let us consider another example of a programming functors.

instance Functor ((->) a) where
    fmap g h = g . h

Thinking back on our discussion earlier, a programming functor is a type constructor that takes a single type. If b if some arbitrary type, then f b = (->) a b = a -> b, which is just the type of some function that takes input of type a and returns an output of type b.
i.e. (->) a is a type constructor for functions that take something of type a as input.

Suppose that we have two types: b and c as well as a specific function of type b -> c between them. Our programming functor should be able to map all three of them somehow.
Mapping the types is easy: f b becomes a -> b and f c becomes a -> c.

Applying fmap to the function of type b -> c should result in some function of type (a -> b) -> (a -> c).
Given a function of type b -> c, how do we construct a function of type (a -> b) -> (a -> c)?

After some thought, it should be apparent that applying the function b -> c after a -> b with input a should result in something of type c. This explains the line fmap g h = g . h.
g is our function of type b -> c and h is some function of type a -> b. By composing the two, we obtain our desired function of type a -> c.