Contents

Programming with Categories: Functor

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.

Warning

This section assumes you know what a category is. If you haven’t heard of it before, think of a category as a collection of objects and the relationships between them.

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 relationships1.

  • 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)$

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.

Info

The endo in endofunctor comes from Greek, meaning within.

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
Tip

The function signature fmap :: (a -> b) -> f a -> f b has two interpretations:

  • Morphism mapping view: (a -> b) -> (f a -> f b)
    • Takes a function a -> b and returns a lifted function f a -> f b.
    • Parentheses emphasizes this is a mapping between morphisms(Haskell functions).
  • Application view (a -> b) -> f a -> f b
    • Take both a function a -> b and a value f a, returning f b.
    • Parentheses removed due to currying (all Haskell functions are curried).

While both are valid, the second form is more general and idiomatic in Haskell.

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.

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 :)