Programming with Categories: Functor

Intro

What’s a functor? You might use it daily without realizing it. For example, calling map on a collection means you’re using a functor.

This post explains functors from two perspectives: category theory and programming. By this end, you will have a deeper understanding of the concept.

Functor in category theory

flowchart
    subgraph C
        a
        b
    end
    subgraph D
        fa(F a)
        fb(F b)
    end
    a --> |F| fa(F a)
    b --> |F| fb(F b)
    a --> |f| b
    fa --> |F f| fb

In category, theory, a functor $F:\mathcal C\rightarrow\mathcal D$ refers to the mapping between categories $\mathcal C$ and $\mathcal D$ that preserves their structure. Specifically, $F$ maps objects and morphisms from $\mathcal C$ to $\mathcal D$ while maintaining composition and identity relationships¹.

• Object mapping: Each object $a$ in category $\mathcal C$ is mapped to $F\ a$ in category $\mathcal D$
• Morphism mapping: Each morphism $f:a\rightarrow b$ in category $\mathcal C$ is mapped to $F\ f:F\ a\rightarrow F\ b$ in category $\mathcal D$

Besides that, a functor should be subject to the functor laws:

• Identity preservation: $F\ id_a=id_{F\ a}$
• Composition preservation: $F(f\circ g)=(F\ f)\circ(F\ g)$

Functor in programming

Haskell’s design incorporates concepts from category theory. We will demonstrate this using Haskell code examples.

From a category theory perspective, all Haskell types form a category $\mathcal C$ where

• Object: Haskell types
• Morphism: Haskell functions

From a programmer’s perspective, we programmers focus on writing Haskell functions and converting between Haskell types. Therefore, we are particularly interested in the specific category $F:\mathcal C\rightarrow\mathcal C$, called endofunctor.

To represent a functor where

• Objects are Haskell types.
• Morphisms are Haskell functions.

We implement it using:

• Object mapping: A type constructor with type variables.
• Morphism mapping: A type class.

For example, the Maybe type constructor can create types like Maybe Int.

As for the mapping between morphisms, they can be represented by the following Functor type class.

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

Example. Maybe Functor

The Maybe type is a classic functor. We could easily creat a Maybe a type by providing a type a. The interesting question is: how should we implement fmap for the Maybe functor?

fmap :: (a -> b) -> Maybe a -> Maybe b

There exist two data constructors: Nothing and Just.

• Nothing represents the absence of a value, mapping any function over Nothing should still remain Nothing.
• Just a has a value with type a. Applying fmap to Just a should produce Just (f b) (as seen in fmap’s type signature).

The detailed code is shown below.

instance Functor Maybe where
  fmap _ Nothing = Nothing
  fmap f (Just x) = Just (f x)

Finally, we should also verify that our implementation satisfies the functor laws.

The first law states that $F\ {id_a}=id_{F\ a}$, which translates to fmap id = id in Haskell.

fmap id Nothing = Nothing
                = id Nothing
-- fmap _ Nothing = Nothing

fmap id (Just x) = Just (id x)
                 = Just x
                 = id (Just x)
-- fmap f (Just x) = Just (f x)

The second law states that $F(f\circ g)=(F\ f)\circ(F\ g)$:

fmap (f . g) Nothing = Nothing
                     = fmap f Nothing
                     = fmap f (fmap g Nothing)
                     
fmap (f . g) (Just x) = Just ((f . g) x)
                      = Just (f (g x))
                      = fmap f (Just  (g x))
                      = fmap f (fmap g (Just x))
                      = (fmap f . fmap g) (Just x)

Thus, we’ve verified that our implementation is correct.

What’s the benefit of functor?

A functor establishes a mapping between categories of Haskell types. It maps not only types themselves but also preserves the mapping of functions between them. Thus, we can write functions for one type and use functors to lift them to work with other types. In this sense, a functor acts as an adapter.

The List type ([]) is another classic functor. Its fmap function is implemented as follows:

instance Functor [] where
  fmap _ [] = []
  fmap f (x : xs) = f x : fmap f xs

Let’s assume that you’ve already implemented a function foo for the Int type:

foo :: Int -> Int
foo x = (x * 2) + 1

Now suppose you want to apply the foo function to every element in an [Int] list. You don’t need to write a new function - just use fmap

fmap foo [1, 2, 3]
-- [3, 5, 7]

This example might seem trivial, but it demonstrates the core concept :)