---
title: Functor, applicative, and monad
published: August 31, 2019
summary:
Functor, applicative, and monad are useful abstractions. They're also not
so hard to understand!
---
Functor, applicative, and monad are related concepts that frequently arise in
functional programming. These three ideas give a name to common patterns across
different operations defined on different data types, so recognizing their
occurrences are important. However, these entities are shrouded in mystery,
being associated with "category theory," and in particular, monads have been
elevated to a divine status around the misconception that they are about
"laziness" or "state." Although functors, applicatives, and monads do originate
from category theory, their manifestations in functional programming are far
removed from their origins and you don't need to understand category theory to
use them effectively in your programs.
Functor, applicative, and monad are abstract concepts agnostic of any specific
programming language. However, we use programming languages to precisely
communicate ideas, and therefore I use OCaml in this tutorial, with some
occurrences of Haskell. I occasionally mention the category theory behind an
idea, without making it the focus of the explanation or assuming prior
knowledge. My intention is for anyone familiar with the basics of typed
functional programming to be able to follow along.
## Functor
You've probably mapped over lists in your code before. Given some function
`f : 'a -> 'b`{.ocaml}, you can run that function on every element of some list
`l : 'a list`{.ocaml} to produce a new list, `map f l : 'b list`{.ocaml}, that
contains the results of `f`{.ocaml} applied to each element of `l`{.ocaml}.
It turns out that every generic type `t`{.ocaml} has a corresponding map
function `map : ('a -> 'b) -> 'a t -> 'b t`{.ocaml}. The type `t`{.ocaml}
together with the map function is called a functor. The definition of functor
interprets `t`{.ocaml} as a "function" from types to types that transforms the
original type `'a`{.ocaml} into a type `'a t`{.ocaml} with some additional
meaning. The `map`{.ocaml} operation associates every function
`f : 'a -> 'b`{.ocaml} with a corresponding function
`map f : 'a t -> 'b t`{.ocaml}.
Functor comes with the following *laws*, or contracts that implementations
should satisfy:
- `id` = `map id`{.ocaml}, where `id x = x`{.ocaml} (identity function).
- `compose (map g) (map f)`{.ocaml} = `map (compose g f)`{.ocaml}, where
`compose g f x = g (f x)`{.ocaml} (function composition).
These laws come from category theory, where a functor is a map from category to
category, and therefore must preserve the "category structure." Without learning
category theory, an intuitive way of understanding these laws is that
`map f x`{.ocaml} transforms the contents of `x`{.ocaml} according to
`f`{.ocaml}, but doesn't change the "shape" of `x`{.ocaml}.
In Haskell's standard library, the map operation is called `fmap`{.haskell}.
OCaml's binding operators make functor usage more convenient. You can define an
operator `(let+)`{.ocaml} and use it like a let-binding. The code
`let+ x = a in y`{.ocaml} is desugared into `(let+) a (fun x -> y)`{.ocaml}.
Conventionally, `(let+)`{.ocaml} has type `'a t -> ('a -> 'b) -> 'b t`{.ocaml},
making it `map`{.ocaml} with its arguments reversed.
Other than the list type, another example of a functor is the option type.
`'a option`{.ocaml} represents the possible absence of `'a`: it can either be
`Some of 'a`{.ocaml} or `None`{.ocaml}. The option type is like a type-safe
alternative to nullability: the possible absence is expressed in the type and
you must pattern match on option values to retrieve the `'a` inside, forcing you
to consider the `None`{.ocaml} case.
Sometimes, when pattern matching, you handle the `Some`{.ocaml} case by
transforming the value inside and returning `Some`{.ocaml}, and you handle the
`None`{.ocaml} case by returning `None`{.ocaml}:
```ocaml
match opt with
| Some x -> Some (x + 1)
| None -> None
```
In this situation, pattern matching can get verbose. For option types, the
`map`{.ocaml} function abstracts away the pattern match:
```ocaml
let map f = function
| Some x -> Some (f x)
| None -> None
map (fun x -> x + 1) opt
```
The benefit of recognizing that the list type, the option type, and others
all give rise to a functor is that you can write generic code that only relies
on the functor laws, yet has desirable meaning for each functor instance. This
benefit increases with applicatives and monads, which have additional operations
and laws.
## Applicative
According to currying, `'a -> 'b -> 'c`{.ocaml} is interchangeable with
`'a * 'b -> 'c`{.ocaml}. (The fancy math word for this interchangeability is
"isomorphism.")
However, given that `f : 'a -> 'b -> 'c`{.ocaml},
`map f : 'a t -> ('b -> 'c) t`{.ocaml}, but what if you actually wanted
`'a t -> 'b t -> 'c t`{.ocaml}? Certain functors, called applicative functors,
have additional structure about preserving the currying relationship.
In Haskell's standard library, the applicative is defined with an operator
`(<*>) :: Applicative f => f (a -> b) -> f a -> f b`{.haskell}, where
`f`{.haskell} refers to the functor type. With this operator, you can turn the
`('b -> 'c) t`{.ocaml} in the above example into a `'b t -> 'c t`{.ocaml}.
OCaml provides "and-operator" syntactic sugar intended for applicatives, and
this syntactic sugar suggests an alternate definition. You can define an
operator `(and+)`{.ocaml} and use it like an and-binding next to a let-binding
operator. The code `let+ x = a and+ y = b in c`{.ocaml} desugars into
`(let+) ((and+) a b) (fun (x, y) -> c)`{.ocaml}. If `(let+)`{.ocaml} is
`map`{.ocaml} with its arguments reversed, then it would have type
`('a * 'b) t -> (('a * 'b) -> 'c) -> 'c t`{.ocaml} in this context, as the
lambda in the desugaring takes a pair as an input. Therefore, `(and+)`{.ocaml}
must have type `'a t -> 'b t -> ('a * 'b) t`{.ocaml} for it to define an
applicative. So, applicatives are about "preserving" the product.
Given:
- `map : ('a -> 'b) -> 'a t -> 'b t`{.ocaml}
- `(and+) : 'a t -> 'b t -> ('a * 'b) t`{.ocaml}
- `f : ('a * 'b) -> 'c`
You can derive:
- `f : ('a * 'b) -> 'c`{.ocaml}
- `map f : ('a * 'b) t -> 'c t`{.ocaml}
- `(fun (x, y) -> map f ((and+) x y)) : ('a t * 'b t) -> 'c t`{.ocaml}
Because of the currying relationship,
- `('a * 'b) -> 'c`{.ocaml} is isomorphic to `'a -> 'b -> 'c`{.ocaml}
- `('a t * 'b t) -> 'c t`{.ocaml} is isomorphic to
`'a t -> 'b t -> 'c t`{.ocaml}
So, the currying relationship is preserved.
Essentially, applicatives are about "mapping over" functions of multiple
parameters.
The product type `'a * 'b`{.ocaml}, as its name implies, is similar to
multiplication. The identity element of multiplication is 1, meaning that
1 * a = a * 1 = 1. Similarily, the product type has an identity, the
`unit`{.ocaml} type. `unit`{.ocaml} only has one inhabitant, `()`{.ocaml}, and
therefore `unit * 'a`{.ocaml}, `'a * unit`{.ocaml}, and `'a`{.ocaml} are all
interchangeable.
The *monoid* generalizes the idea of an associative binary operation with an
identity element. Technically, an applicative is a "lax monoidal functor,"
meaning that it must preserve the identity element. In addition to the
`(<*>)`{.haskell} operator, applicative requires a function
`pure :: Applicative f => a -> f a`{.haskell}. `(pure f) <*> x`{.haskell} should
equal `fmap f x`{.haskell}. Equivalently, according to the definition using the
`(and+)`{.ocaml} operator, an applicative must define some value
`one : unit t`{.ocaml}.
## Monad
The monad is more powerful than the functor and the applicative because it lets
later computations depend on the results of earlier computations. A monad
defines an operation called "monadic bind," or
`(>>=) : 'a t -> ('a -> 'b t) -> 'b t`{.ocaml}. Notice that unlike
`map : ('a -> 'b) -> 'a t -> 'b t`{.ocaml}, `(>>=)`{.ocaml} takes a function
whose output type is a result of the functor. While `map`{.ocaml} doesn't change
the "shape", only the contents, monadic bind lets the passed function change a
monadic value's shape. With monadic bind, the shape of the result is, quite
literally, *a function of* the contents.
Consider the option functor example from before. The `map`{.ocaml} function
abstracted away the pattern match. However, the `Some`{.ocaml} case always
returned a `Some`{.ocaml}. What if whether it returned a `Some`{.ocaml} or a
`None`{.ocaml} depended on the value inside the `Some`{.ocaml}?
```ocaml
match str_opt with
| Some str -> int_of_string_opt str
| None -> None
```
You can't use a functor here:
`map int_of_string_opt str_opt : int option option`{.ocaml}, rather than the
desired `int option`{.ocaml}. However, you can use the monadic bind operation
defined on the option type:
```ocaml
let (>>=) opt f =
match opt with
| Some a -> f a
| None -> None
str_opt >>= int_of_string_opt
```
Even if `opt`{.ocaml} is the `Some`{.ocaml} case, `opt >>= f`{.ocaml} can result
in `None`{.ocaml}. In other words, `f`{.ocaml} can change the "shape" of the
option.
Notice the nested `option`{.ocaml}s in `int option option`{.ocaml}. In general,
if `f : 'a -> 'b t`{.ocaml} and `x : 'a`{.ocaml}, then
`map f x : 'b t t`{.ocaml}. Instead of bind, a monad can be defined in terms of
`join : 'a t t -> 'a t`{.ocaml}. The essence of a monad is the ability to
*flatten* values. Indeed, another name for monadic bind is flatmap, which is
just a map followed by a flatten! A way of understanding `join`{.ocaml} is that
when the nested monadic value is flattened, its "shape" is changed.
Of course, since you can flatten and flatmap over lists, the list type admits a
monad instance.
In addition to monadic bind, monads must also support an operation
`return : 'a -> 'a t`{.ocaml}, but `return`{.ocaml} is identical to
applicative's `pure`{.ocaml}.
Monadic functions can be composed with
`(<=<) : ('b -> 'c t) -> ('a -> 'b t) -> 'a -> 'c t`{.ocaml}. This operation is
known as Kleisli composition. A monad must satisfy these laws:
- `(h <=< g) <=< f`{.ocaml} = `h <=< (g <=< f)`{.ocaml} (Associativity)
- `return <=< f`{.ocaml} = `f <=< return`{.ocaml} = `f`{.ocaml} (Identity)
Notice that these laws are similar to the properties of function composition and
identity:
- `compose (compose h g) f`{.ocaml} = `compose h (compose g f)`{.ocaml}
(Associativity)
- `compose id f`{.ocaml} = `compose f id`{.ocaml} = `f`{.ocaml} (Identity)
The category-theoretic explanation is that every monad gives rise to a "Kleisli
category." Intuitively, this just means that `(<=<)`{.ocaml} is similar to
`compose`{.ocaml} and `return` is similar to `id`{.ocaml}.
Why do people care about monads so much? When a monadic value is flattened, some
kind of computation can happen, and therefore people use monads to achieve
"effects." In my opinion, the word "effects" is misleading because it implies
that monads are special, while in reality these "effects" are just the different
behaviors that different monad instances have. Realize that these behaviors are
all implemented in normal code.
Examples of monads and their effects:
- The `'a list`{.ocaml} monad's effect is nondeterminism. The list contains what
you can think of as "alternate timelines" or "parallel universes."
- The `'a option`{.ocaml} monad's effect is failure. If the result is
`None`{.ocaml}, the computation has "failed."
- The `('e, 'a) result`{.ocaml} monad can throw "exceptions" of type
`'e`{.ocaml}. It works like the `option`{.ocaml} monad, but instead of
`None`{.ocaml}, it has an error message, `Error of 'e`{.ocaml}.
- The state monad `('s, 'a) state`{.ocaml}, which wraps
`'s -> ('a * 's)`{.ocaml} for some "state type" `'s`{.ocaml}, models the
effect of updating the state.
Haskell's IO monad is the state monad where the state is the "real world." The
motivation of using a monad for IO is as follows: Haskell is non-strict, so
reasoning about the execution of side effects is difficult. Therefore, Haskell
became pure and then adopted monadic IO as a way of doing IO purely.
**However, contrary to
popular myth, monads themselves aren't about state or laziness!!**
Haskell provides do-notation as syntactic sugar for monadic bind.
```haskell
do x <- m1
m2
```
roughly translates to `m1 >>= \x -> do m2`{.haskell}, and
```haskell
do m1
m2
```
roughly translates to `m1 >>= \_ -> do m2`{.haskell}.
In addition to functor's map, OCaml's binding operators can be used for monadic
bind. Conventionally, `( let* ) : 'a t -> ('a -> 'b t) -> 'b t`{.ocaml}, making
it a synonym of monadic bind.
The following code is an example of the option monad in action. It reads two
strings that may not exist, parses them into integers, and calculates their sum:
```ocaml
let read_setting (s : string) : string option =
...
read_setting "x" >>= fun x ->
int_of_string_opt x >>= fun x ->
read_setting "y" >>= fun y ->
int_of_string_opt y >>= fun y ->
return (x + y)
```
Here is the equivalent code using `( let* )`{.ocaml}:
```ocaml
let read_setting (s : string) : string option =
...
let* x = read_setting "x" in
let* x = int_of_string_opt x in
let* y = read_setting "y" in
let* y = int_of_string_opt y in
return (x + y)
```
If either `read_setting`{.ocaml} or `int_of_string_opt`{.ocaml} returns
`None`{.ocaml}, the entire expression evaluates to `None`{.ocaml}. See how
concise the code is!
Here is a more "clever" version that makes use of Kleisli composition to chain
together `read_setting`{.ocaml} and `int_of_string_opt`{.ocaml} into a single
function, `read_int_setting`{.ocaml}, that reads the setting and parses it into
an integer:
```ocaml
let read_setting (s : string) : string option =
...
let read_int_setting : string -> int option =
int_of_string_opt <=< read_setting
let* x = read_int_setting "x" in
let* y = read_int_setting "y" in
return (x + y)
```
## Conclusion
A functor is some type `'a t`{.ocaml} with some operation `map`{.ocaml} that
can convert any function `f : 'a -> 'b`{.ocaml} into a function
`map f : 'a t -> 'b t`{.ocaml}. An applicative is a functor that preserves the
*product* by providing a value `one : unit t`{.ocaml} and a way to convert from
`'a t * 'b t`{.ocaml} to `('a * 'b) t`{.ocaml}. With applicatives, you can "map"
each parameter of a multi-parameter function, allowing you to convert from
`'a -> 'b -> 'c`{.ocaml} to `'a t -> 'b t -> 'c t`{.ocaml}. A monad is a functor
that provides an operation `join : 'a t t -> 'a t`{.ocaml}. Equivalently, a
monad generalizes the `flatmap`{.ocaml} operation. Monads are more powerful than
plain functors and applicatives because a monadic value's "shape" can depend on
the results of a computation.
---
1.