#PrayForKyoAni | Blog post: Five wonderful angels: A love letter to K-On | Help KyoAni recover

Posted on August 31, 2019

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:

match opt with
| Some x -> Some (x + 1)
| None -> None

In this situation, pattern matching can get verbose. For option types, the map function abstracts away the pattern match:

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

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?

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, rather than the desired int option. However, you can use the monadic bind operation defined on the option type:

let (>>=) opt f =
match opt with
| Some a -> f a
| None -> None

str_opt >>= int_of_string_opt

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

do x <- m1
m2

roughly translates to m1 >>= \x -> do m2, and

do m1
m2

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 =

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.

1. ^ 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