Functor #

The notion of functor comes from a branch of mathematics called category theory.

For programmers, a functor can be viewed as a generic type that implements a certain function (called fmap in Haskell), while respecting certain constraints.

In Haskell #

Definition. Functor in Haskell is a type class.

A type t that belongs to this class must:

• be a generic type (with a single type variable), and
• implement the function

fmap :: (Functor t) => (a -> b) -> t a -> t b

Terminology. The function fmap lifts a function

$\qquad$ f :: a -> b

to a function

$\qquad$ fmap f :: t a -> t b

Example. The type “List” (noted [ ] in Haskell) is a functor.

So for this type, fmap lifts a function

$\qquad$ f :: a -> b

to a function

$\qquad$ fmap f :: [a] -> [b]

Constraints #

The mathematical definition of a functor requires that fmap satisfies two additional constraints, sometimes called the functor laws.

Constraint. fmap should preserve function composition, i.e.

$\qquad$ fmap (g . f) and (fmap g) . (fmap f) must be the same function.

Constraint. fmap must preserve the identity function , i.e.

$\qquad$ fmap id and id must be the same function.

(where the first id is over a, and the second over t a).

These two laws limit the possible implementations of fmap.

Example (continued). For the type “List”, the implementation of fmap coincides with map.

Indeed, this is the only way to implement fmap while respecting the two functor laws.
So for instance

fmap (+ 1) [1,2,3]

evaluates to [2,3,4], just like

map (+ 1) [1,2,3]

Usage #

Intuition. A functor can often be viewed as a “container” type.

Examples. “List”, “Set”, “Tree” and “Optional” are all functors.

Intuition. The functor laws often capture the “natural” (a.k.a. expected) way to lift a function to a container type.

Example. Consider the function

ord :: Char -> Int

that maps a character to its Unicode point.

We can lift it to a function fmap ord.
Then:

• If cs is a list of characters, then fmap ord cs is the list of their Unicode points,
• If cs is a set of characters, then fmap ord cs is the set of their Unicode points,
• If c is an optional character, then fmap ord c is its optional Unicode point,
• etc.

To go further.

Benefit. One can write generic code that uses fmap, regardless of its implementation for a specific functor (for an illustration, we refer to Programming in Haskell).

Other applications. Functors are used for automatic program verification.

Limitation. In general, the Haskell compiler cannot check whether an implementation of fmap satisfies the functor laws.

Maybe as a functor #

Reminder. Maybe is the option type of Haskell.

It is declared as:

data Maybe a = Nothing | Just a

Implementation. The type Maybe is a functor. Therefore it implements fmap.

So in this case, fmap lifts a function

$\qquad$ f :: a -> b

to a function

$\qquad$ fmap f :: Maybe a -> Maybe b

This function maps

• Nothing to Nothing, and
• Just x to Just (f x).

Or in other words:

fmap :: (a -> b) -> Maybe a -> Maybe b
fmap _ Nothing   = Nothing
fmap f (Just x)  = Just (f x)

Examples. We can use fmap to lift the function (+ 1).

fmap (+ 1) Nothing    -- evaluates to `Nothing`

$\qquad$

fmap (+ 1) (Just 3)     -- evaluates to `Just 4`

Usage #

For the functor Maybe, fmap lets us propagate some “null values” (i.e. Nothing) without boilerplate code.

Example. Consider a function

maybeHead :: [Int] -> Maybe Int

that maps a list to its head (if present).

For instance:

• maybeHead [] evaluates to Nothing
• maybeHead [2,3,4] evaluates to Just 2

Now let us assume that we want to:

• apply the function (^ 2) to the output of maybeHead if present, and
• propagate the “null value” (a.k.a. Nothing) otherwise.

No need to check explicitly whether maybeHead outputs Nothing. Instead, we can use fmap.
For instance (assuming that we import >>> from the module Control.Category):

maybeHeadSquared :: [Int] -> Maybe Int
maybeHeadSquared = maybeHead >>> fmap (^ 2)   -- compose `maybeHead` with `fmap (^ 2)`

Then

maybeHeadSquared [3,4,5]

evaluates to Just 9, whereas

maybeHeadSquared []

evaluates to Nothing.

[3,4,5,6] & filter (> 6)
          & maybeHead
          & fmap (+ 1)

[3,4,5,6] & filter even
          & maybeHead
          & fmap (+ 1)
          & fmap (< 5)

[[3,7],[4,5]] & map (filter even)
              & map (maybeHead)
              & map (fmap (+ 1))