# Functor, applicative, and monad

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`

, you can run that function on every element of some list `l : 'a list`

to produce a new list, `map f l : 'b list`

, that contains the results of `f`

applied to each element of `l`

.

It turns out that many generic types `t`

have a corresponding map function `map : ('a -> 'b) -> 'a t -> 'b t`

. The type `t`

together with the map function is called a functor. The definition of functor interprets `t`

as a "function" from types to types that transforms the original type `'a`

into a type `'a t`

with some additional meaning. The `map`

operation associates every function `f : 'a -> 'b`

with a corresponding function `map f : 'a t -> 'b t`

.

Functor comes with the following *laws*, or contracts that implementations should satisfy:

`id`

=`map id`

, where`id x = x`

(identity function).`compose (map g) (map f)`

=`map (compose g f)`

, where`compose g f x = g (f x)`

(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`

transforms the contents of `x`

according to `f`

, but doesn't change the "shape" of `x`

.

In Haskell's standard library, the map operation is called `fmap`

.

OCaml's binding operators make functor usage more convenient. You can define an operator `(let+)`

and use it like a let-binding. The code `let+ x = a in y`

is desugared into `(let+) a (fun x -> y)`

. Conventionally, `(let+)`

has type `'a t -> ('a -> 'b) -> 'b t`

, making it `map`

with its arguments reversed.

Other than the list type, another example of a functor is the option type. `'a option`

represents the possible absence of `'a`

: it can either be `Some of 'a`

or `None`

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

case.

Sometimes, when pattern matching, you handle the `Some`

case by transforming the value inside and returning `Some`

, and you handle the `None`

case by returning `None`

:

In this situation, pattern matching can get verbose. For option types, the `map`

function abstracts away the pattern match:

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`

is interchangeable with `'a * 'b -> 'c`

. (The fancy math word for this interchangeability is "isomorphism.")

However, given that `f : 'a -> 'b -> 'c`

, `map f : 'a t -> ('b -> 'c) t`

, but what if you actually wanted `'a t -> 'b t -> 'c t`

? 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`

, where `f`

refers to the functor type. With this operator, you can turn the `('b -> 'c) t`

in the above example into a `'b t -> 'c t`

.

OCaml provides "and-operator" syntactic sugar intended for applicatives, and this syntactic sugar suggests an alternate definition. You can define an operator `(and+)`

and use it like an and-binding next to a let-binding operator. The code `let+ x = a and+ y = b in c`

desugars into `(let+) ((and+) a b) (fun (x, y) -> c)`

. If `(let+)`

is `map`

with its arguments reversed, then it would have type `('a * 'b) t -> (('a * 'b) -> 'c) -> 'c t`

in this context, as the lambda in the desugaring takes a pair as an input. Therefore, `(and+)`

must have type `'a t -> 'b t -> ('a * 'b) t`

for it to define an applicative. So, applicatives are about "preserving" the product.

Given:

`map : ('a -> 'b) -> 'a t -> 'b t`

`(and+) : 'a t -> 'b t -> ('a * 'b) t`

`f : ('a * 'b) -> 'c`

You can derive:

`f : ('a * 'b) -> 'c`

`map f : ('a * 'b) t -> 'c t`

`(fun (x, y) -> map f ((and+) x y)) : ('a t * 'b t) -> 'c t`

Because of the currying relationship,

`('a * 'b) -> 'c`

is isomorphic to`'a -> 'b -> 'c`

`('a t * 'b t) -> 'c t`

is isomorphic to`'a t -> 'b t -> 'c t`

So, the currying relationship is preserved.

Essentially, applicatives are about "mapping over" functions of multiple parameters.

The product type `'a * 'b`

, 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`

type. `unit`

only has one inhabitant, `()`

, and therefore `unit * 'a`

, `'a * unit`

, and `'a`

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 `(<*>)`

operator, applicative requires a function `pure :: Applicative f => a -> f a`

. `(pure f) <*> x`

should equal `fmap f x`

. Equivalently, according to the definition using the `(and+)`

operator, an applicative must define some value `one : unit t`

.

## 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`

. Notice that unlike `map : ('a -> 'b) -> 'a t -> 'b t`

, `(>>=)`

takes a function whose output type is a result of the functor. While `map`

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`

function abstracted away the pattern match. However, the `Some`

case always returned a `Some`

. What if whether it returned a `Some`

or a `None`

depended on the value inside the `Some`

?

You can't use a functor here: `map int_of_string_opt str_opt : int option option`

, rather than the desired `int option`

. However, you can use the monadic bind operation defined on the option type:

Even if `opt`

is the `Some`

case, `opt >>= f`

can result in `None`

. In other words, `f`

can change the "shape" of the option.

Notice the nested `option`

s in `int option option`

. In general, if `f : 'a -> 'b t`

and `x : 'a t`

, then `map f x : 'b t t`

. Instead of bind, a monad can be defined in terms of `join : 'a t t -> 'a t`

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

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`

, but `return`

is identical to applicative's `pure`

.

Monadic functions can be composed with `(<=<) : ('b -> 'c t) -> ('a -> 'b t) -> 'a -> 'c t`

. This operation is known as Kleisli composition. A monad must satisfy these laws:

`(h <=< g) <=< f`

=`h <=< (g <=< f)`

(Associativity)`return <=< f`

=`f <=< return`

=`f`

(Identity)

Notice that these laws are similar to the properties of function composition and identity:

`compose (compose h g) f`

=`compose h (compose g f)`

(Associativity)`compose id f`

=`compose f id`

=`f`

(Identity)

The category-theoretic explanation is that every monad has an associated "Kleisli category." Intuitively, this just means that `(<=<)`

is similar to `compose`

and `return`

is similar to `id`

.

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`

monad's effect is nondeterminism. The list contains what you can think of as "alternate timelines" or "parallel universes." - The
`'a option`

monad's effect is failure. If the result is`None`

, the computation has "failed." - The
`('e, 'a) result`

monad can throw "exceptions" of type`'e`

. It works like the`option`

monad, but instead of`None`

, it has an error message,`Error of 'e`

. - The state monad
`('s, 'a) state`

, which wraps`'s -> ('a * 's)`

for some "state type"`'s`

, 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. ^{[1]} **However, contrary to popular myth, monads themselves aren't about state or laziness!!**

Haskell provides do-notation as syntactic sugar for monadic bind.

roughly translates to `m1 >>= \x -> do m2`

, and

roughly translates to `m1 >>= \_ -> do m2`

.

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`

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

```
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* )`

:

```
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`

or `int_of_string_opt`

returns `None`

, the entire expression evaluates to `None`

. See how concise the code is!

Here is a more "clever" version that makes use of Kleisli composition to chain together `read_setting`

and `int_of_string_opt`

into a single function, `read_int_setting`

, that reads the setting and parses it into an integer:

```
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`

with some operation `map`

that can convert any function `f : 'a -> 'b`

into a function `map f : 'a t -> 'b t`

. An applicative is a functor that preserves the *product* by providing a value `one : unit t`

and a way to convert from `'a t * 'b t`

to `('a * 'b) t`

. With applicatives, you can "map" each parameter of a multi-parameter function, allowing you to convert from `'a -> 'b -> 'c`

to `'a t -> 'b t -> 'c t`

. A monad is a functor that provides an operation `join : 'a t t -> 'a t`

. Equivalently, a monad generalizes the `flatmap`

operation. Monads are more powerful than plain functors and applicatives because a monadic value's "shape" can depend on the results of a computation.

Update Sept 18, 2019: Moomin on HN corrects me that not all generic types `'a t`

have a `map`

function; I have fixed the error in this article.

^ Hudak, P., Hughes, J.,Peyton Jones, S., and Wadler, P. (2007). A history of Haskell: being lazy with class. In (HOPL-III, 2007), sections 3.1 and 3.2

This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.