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
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)$
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.
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
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 functionf a -> f b
. - Parentheses emphasizes this is a mapping between morphisms(Haskell functions).
- Takes a function
- Application view
(a -> b) -> f a -> f b
- Take both a function
a -> b
and a valuef a
, returningf b
. - Parentheses removed due to currying (all Haskell functions are curried).
- Take both a function
While both are valid, the second form is more general and idiomatic in Haskell.
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 overNothing
should still remainNothing
.Just a
has a value with typea
. Applyingfmap
toJust a
should produceJust (f b)
(as seen infmap
’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 :)