functor-applicative-monad.md 14.8 KB
Newer Older
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122
---
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}
123
must have type `'a t -> 'b t -> ('a * 'b) t`{.ocaml} for it to define an
124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356
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.
<sup id='footnote-1-origin'>[[1]](#footnote-1)</sup> **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. <p id='footnote-1'>
  <a href='#footnote-1-origin'>^</a>
  Hudak, P., Hughes, J.,Peyton Jones, S., and Wadler, P. (2007).
  <a href='https://www.microsoft.com/en-us/research/publication/a-history-of-haskell-being-lazy-with-class/'>
    A history of Haskell: being lazy with class</a>.
  In (HOPL-III, 2007), sections 3.1 and 3.2
</p>