# Functors, Monads, and Everything in Between

As a Haskell junkie, I thought for my first post here I'd try to take on the infamously difficult task of explaining functors, applicative functors, and monads. This will assume basic Haskell knowledge.

Why not?

## Introduction

Imagine you have a list type. In Haskell, we can trivially define this as follows:

``````data List a = Cons a (List a) | Nil
``````

However, lists are defined in Prelude, so we don't actually need this definition. Let's make a simple list:

``````foo :: [Int]
foo = [1, 2, 3]
``````

Next, we'll define a simple function acting on `Int`s:

``````f :: Int -> Int
f x = x * 2
``````

Or, in pointfree notation:

``````f :: Int -> Int
f = (*2)
``````

Now, imagine we want to apply this function `f` to every element of our list `foo`. How do we do this?

It turns out there's a function in Prelude called `map` for this very purpose. Its type signature looks like this:

``````map :: (a -> b) -> [a] -> [b]
``````

It may look familiar to users of other languages; for instance, Python has a `map` function which is used similarly. We can use the function as follows to make our new list:

``````bar = map f foo
-- bar = [2, 4, 6]
``````

For completeness, here is an implementation of `map`:

``````map f (x:xs) = f x : map f xs
map f [] = []
``````

So far, so good. But what happens when we want to use a different container type, such as the `Data.Vector` type from the `vector` package? We would need a separate mapping function! That's not very fun: we want our functions to be more versatile than that. Haskell excels at abstraction and generalisation; there must be something we can do!

## Enter the Functor

A functor is, in essence, a wrapper around zero or more values which provides a function `fmap` which is analagous to `map` for lists. It is a typeclass which is defined like this:

``````class Functor f where
fmap :: (a -> b) -> f a -> f b
``````

`fmap` is the function which maps a function over everything in the "container". For lists, it is equivalent to `map`.

Notice that here, `f` is not a concrete type, but rather a type constructor which is later applied to arguments. This means that a functor is generic on the type it contains; for instance, `List` is a functor, so we can `fmap` over a list containing values of any type (the `a` in the above type).

Note that there is also an infix synonym for `fmap`: `(<\$>)`. This operator is often more readable than `fmap`:

``````foo = fmap (double . addThree) bar
-- vs
foo = double . addThree <\$> bar
-- ... which is analogous to
foo = double . addThree  \$  bar'
-- if bar' was just a plain Int.
``````

Functors are a lot more general than they may seem at first. A very common type in Haskell is the `Maybe` type, used for rudimentary error handling:

``````data Maybe a = Just a | Nothing
``````

This may not immediately seem like it fulfils the criteria for a functor, but it does! A value of type `Maybe Int`, for instance, contains some number of `Int`s; either zero (if the value is `Nothing`) or one (if the value is some `Just x`). We can therefore implement `fmap` for the `Maybe` type:

``````instance Functor Maybe where
fmap f (Just x) = Just (f x)
fmap f Nothing  = Nothing
``````

Great! We have a general way to apply a function to values wrapped in some "context". This allows us to write polymorphic functions that are useful in a wide variety of contexts. However, there is one small issue.

### The Functor Laws

Currently, we haven't specified what a `Functor` instance should actually do. We intuitively know what it should do; however, the following is a perfectly valid, but nevertheless nonsensical, implementation of `fmap` for `Maybe`:

``````instance Functor Maybe where
fmap _ _ = Nothing
``````

We solve this problem with laws. Laws are essentially a set of rules we write down and declare that every instance of this class must follow. The type system is unable to check this laws hold; we need to do this ourselves. Luckily, this is easy, as Haskell's purity allows you to use equational reasoning to prove them with ease.

There are two laws for the `Functor` typeclass:

``````fmap id = id
fmap g . fmap f = fmap (g . f)
``````

These are relatively simple, but are enough to ensure sane behaviour of the `fmap` function. The first law states that mapping `id` over the container - i.e. doing nothing to every element in it - is the same as doing nothing to the whole container. The second states that mapping a function `f` over a container and then mapping a function `g` over it is the same as just mapping the composition of those functions `g.f` over the container once.

Let's check that these laws hold for our (original) `Maybe` instance:

``````instance Functor Maybe where
fmap f (Just x) = Just (f x)
fmap f Nothing  = Nothing
``````

First, the first law:

``````fmap id = id
-- We need to split this into two cases to prove the laws:
fmap id (Just x) = id (Just x)
fmap id Nothing  = id Nothing
-- The first case:
fmap id (Just x)
= Just (id x)
= Just x
= id (Just x)
-- And the second:
fmap id Nothing
= Nothing
= id Nothing
``````

By performing a few trivial steps, we've proven that the first functor law holds. For reasons I won't explain here, the second law actually follows from the first; however, it can be manually proven in the same way as the first law. Doing so is left as an exericse to the reader.

### The Container Illusion

So far, I've talked about functors being "containers" for values. This is often correct - all the functors we've seen so far have directly contained values in their constructors. However, the `Functor` typeclass is completely opaque. It doesn't care how you get the values; it just cares that you can map over them. Therefore, you can also construct valid functors from processes that result in values.

An example of this which might be familiar to imperative programmers is a promise; however, even a function matches this criteria. A function ```r -> a``` can be seen as a functor on `a`; where `fmap` simply composes a new function onto the end of the given one. This is not just theoretical: in Haskell, there is a `Functor` instance in Prelude for `(->) r`, where `fmap = (.)`. Don't worry if you don't understand this; the point is that a functor doesn't neccesarily have to contain values, but can instead represent a process or computation to get them.

By now, we have described a typeclass that allows you to operate on values inside some "context". However, it is an incredibly limited interface. It cannot ever touch the context; only the contained values. This is a limitation we can get past with more complex interfaces.

## Applicative Functors: Combining Contexts

Imagine you have the following two values:

``````x = Just 1
y = Just 2
``````

If you want to add these values to create another `Maybe Int`, how can you go about it? You can try to `fmap` functions around, but you will quickly find that it is impossible without actually unwrapping the contained values using case statements. Why?

Functors only give us the ability to map functions of one argument over containers. If we run `fmap (+) x`, due to currying, we get a value of type `Maybe (Int -> Int)`, which we want to apply to `y :: Maybe Int`. However, we have no way of doing this. What we need to make this work is a function with the following signature:

``````(<*>) :: Maybe (a -> b) -> Maybe a -> Maybe b
``````

This would allow us to do the addition as follows:

``````(+) <\$> Just 1 <*> Just 2
``````

However, as it turns out, this operator is not fictional! If you open GHCi and type that in, you will get `Just 3` back as expected.

Note: There is some contention as to what to call the `<*>` operator. Names I've seen include "ap", "splat", and "spaceship".

This `<*>` operator is part of a different typeclass called `Applicative`, which is the typeclass describing applicative functors. Applicative functors allow you to combine the contexts of two wrapped values into one by applying a wrapped function to a wrapped value. This wrapped function is rarely gotten directly; instead, it is the result of mapping a function of multiple arguments across a functor.

The definition of the `Applicative` typeclass is as follows:

``````class (Functor f) => Applicative f where
pure :: a -> f a
(<*>) :: f (a -> b) -> f a -> f b
``````

We've discussed `(<*>)`, but what's this `pure`? This is the other ability applicative functors provide you: the ability to inject a value into a context. For `Maybe`, it simply applies the `Just` constructor; for lists, it creates a singleton list; etc.

Note that `Applicative` extends from `Functor`, since `fmap` can be implemented for any `Applicative` with `fmap f x = pure f <*> x`.

Let's write an `Applicative` instance for `Maybe`.

``````instance Applicative Maybe where
pure = Just
(Just f) <*> (Just x) = Just (f x)
_        <*> _        = Nothing
``````

The implementation of `<*>` can be guessed from the type. In essence, if both the function and its argument exist (i.e. are `Just something`), you can successfully create the result by applying the unwrapped function to the unwrapped argument; otherwise, you just get `Nothing`.

The implementation of `<*>` for types that can contain more than one value, such as lists, is less obvious. We won't worry too much about it here; but it turns out `<*>` for lists, by default, acts as a sort of explosive map:

``````Prelude> [(*1), (*10), (*100)] <*> [1, 2, 3]
[ 1
, 2
, 3
, 10
, 20
, 30
, 100
, 200
, 300
]
``````

### The Applicative Laws

Like `Functor`, there are a set of laws that `Applicative` instances should follow to be considered legal. They are as follows:

``````pure id <*> v = v                -- Identity
pure f <*> pure x = pure (f x)   -- Homomorphism
u <*> pure y = pure (\$ y) <*> u  -- Interchange
pure (.) <*> u <*> v <*> w = u <*> (v <*> w) -- Composition
``````

They're a bit of a mouthful! Let's look at them one by one.

The identity law is the most trivial. It is very similar to the identity law for functors: it effectively says that wrapping the `id` function using `pure` and then applying it to a wrapped value `b` should not affect the value. This also implies an important characteristic of `pure`: it does not have side effects. The meaning of this will be discussed in more depth later: but in essence, this means it cannot modify the context when applied using `<*>`. `pure id` applied over a `Just` should give you back a `Just`; and similarly for `Nothing`.

The homomorphism law is another relatively trivial identity. It says that wrapping a function and its argument and combining them with `<*>` is equivalent to applying the unwrapped function to the unwrapped value, then wrapping the result up.

The interchange law is a bit more complicated. On the left side, we have `u <*> pure y`; where `u :: f (a -> b)`, and `y :: a`. So, this will give us a value of type `f b`. The right hand side effectively performs the same application, but backwards - constructing `(\$ y)`, "the function that applied a function to `y`", and applying it to the function. The good news here is that understanding the law isn't too important - you can verify it with equational reasoning without having to know what it means.

The composition law tells us that composing two functions, `u` and `v`, within the functor, and applying the result to an argument `w`, is equivalent to applying `v` to `w` and then applying `u` to that. It is analogous to the fact that `(f . g) x = f (g x)`. As with the interchange law, it is not too important that you understand what it means, so don't worry if it just looks like a mess of symbols.

Now time for the big one; the m-word.

Monads have a slightly different interface for interacting with wrapped values that provides yet more power. This interface looks quite different to the ones we've seen so far initially, but we'll see similarities later.

``````class (Applicative m) => Monad m where
return :: a -> m a
(>>=) :: m a -> (a -> m b) -> m b
``````

`return` probably looks pretty familiar: save for it being in `Monad` rather than `Applicative`, it's identical to `pure`. In fact, it is guaranteed to be identical in behaviour too; its existence is a historical accident, and it can be safely ignored.

`(>>=)`, pronounced "bind", is the signature function of monads. It takes a wrapped value, and a function that takes an unwrapped value and produces a wrapped value, and it gives you back that wrapped value. Like `Functor` and `Applicative`, it has laws:

``````pure a >>= f = f a  -- Left identity
m >>= pure = m      -- Right identity
(m >>= f) >>= g = m >>= (\x -> f x >>= g)  -- Associativity
``````

The left identity law states that wrapping a value and then unwrapping it and applying a function is equivalent to just applying that function to the original value. Similarly, the right identity law says that if you unwrap a value and then wrap it back up, this is equivalent to doing nothing. The asssociativity law looks odd; while, again, it is not too important to have a strong understanding of the law, it can be easier to see why it represents associativity if you eta-abstract part of the left side:

``````(m >>= \x -> f x) >>= g = m >>= (\x -> f x >>= g)
``````

This looks a bit more like a conventional associativity law.

Bind tends to make the most sense when given in a specialised context; for instance, here is bind for `Maybe`:

``````(>>=) :: Maybe a -> (a -> Maybe b) -> Maybe b
``````

The behaviour of this function should hopefully be fairly clear from its signature; it takes a value that may or may not exist, and if it does feeds it into the given function, which again produces an "optional" value. In this context, this operator is useful for chaining a series of operations that could fail:

``````readSafe  :: String -> Maybe Float     -- Failure case: input is not a valid float
recipSafe :: Float  -> Maybe Float     -- Failure case: input is zero
floorSafe :: Float  -> Maybe Integer   -- Failure case: input is NaN or +/- Infinity

pipeline :: String -> Maybe Integer
pipeline x = readSafe x >>= recipSafe >>= floorSafe
``````

This is all a monad fundamentally is: a "container" for values where you can combine functions resulting in those containers. However, the uses of this pattern turn out to be very powerful.

### Composable Computation Descriptions

You may have heard monads be described as "composable computation descriptions" and wondered what that meant. Indeed, so far we have not seen anything that would indicate a use like this.

Recall earlier I discussed how calling a functor a "container" for values can be misleading. The same applies for monads; they are opaque, and may not immediately contain a value, instead holding (for instance) a function to create that value. In fact, there is a `Monad` instance for `(->) r`! It may be helpful to look at that instance.

`(->) r` is the type of "functions from `r`". The bind operator specialised to it (and cleaned up slightly) looks like this:

``````(>>=) :: (r -> a) -> (a -> r -> b) -> r -> b
``````

While the usage of this function may not immediately be obvious, you may be able to see that there is only one way to implement it (as a total function at least). That implementation looks like this:

``````(>>=) x f e = f (x e) e
``````

Or, rewritten slightly:

``````x >>= f = \e -> f (x e) e
``````

The second way of writing it potentially makes it clearer what this function does. It turns out this is called the `Reader` monad, representing computations that need some "environment" in order to be run; an argument which never changes, but needs to be provided to every function. This is a common pattern; an example of where it could come up is the configuration for a program. Here, the bind operator composes a "wrapped value" with a function that operates on that value to give another "wrapped" value. Notice that unlike examples we have previously looked at, this monad does not really "contain" a value; instead, it describes a way of making one - a computation - and bind, rather than modifying the stored value, simply composes these computations, hence the name "composable computation descriptions".

Probably the most well-known example of a monad is Haskell's IO monad. In essence, a value of type `IO a` does not "contain" an `a`; instead, it represents an imperative, impure computation which has a result of type `a`. Binding into this IO action does not "extract" this result to operate on it; instead, it composes more work onto the end of the IO action. For example:

``````getLine :: IO String         -- getLine describes an impure way of getting a line from stdin
putStrLn :: String -> IO ()  -- putStrLn x describes an impure way of printing x to stdout

getLine >>= putStrLn :: IO ()  -- This describes an impure way of getting a line of stdin,
-- then printing it to stdout
``````

In fact, if you delve into the GHC sources and find the definition of `IO`, you will find that it looks a lot like a simple function `RealWorld -> (a, RealWorld)`, where `RealWorld` is a dummy value used to theoretically represent the state of the universe. This is essentially a specialisation of the incredibly useful `State` monad, but we won't cover that today.

This hopefully sheds some light on why we often refer to monads as composable computation descriptions. There are many more helpful monads out there, like the `Writer` monad - for outputting extra data, such as logs, alongside your code - and parser combinators.

### Contexts and Effects

The "context" of a functor essentially describes any information in the functor which is not directly contained in its value(s). For a list, this would be the length of the list. For `Maybe`, it is whether a value is present. For `IO`, it is the set of side effects (the actual IO actions) that occur. The "effects" of a monad are somewhat loosely defined, but essentially just describe the actions that take place when a computation in a monad is run.

One interesting point is that some computations do not require the monadic interface. Specifically, sequencing of operations only requires the interface on an applicative functor. There is a monadic operator for sequencing, defined as follows:

``````(>>) :: (Monad m) => m a -> m b -> m b
x >> y = x >>= const y
``````

However, this exists only for historical reasons; it can always be replaced with the following operator, defined in terms of `Applicative`:

``````(*>) :: (Applicative f) => f a -> f b -> f b
x *> y = flip const <\$> x <*> y
``````

This definition may make you wonder what happens if you use `const` rather than `flip const`. This function is also defined in Prelude:

``````(<*) :: (Applicative f) => f a -> f b -> f a
x <* y = const <\$> x <*> y
``````

This raises an important point: even though the left value is the one whose result we get, the effects are still sequenced from left to right; that is, `x <* y` "does" `x`, then "does" `y`, but gives you the result of `x`. Effects are always sequenced from left to right. There is only one exception to this rule: the reverse binding operator `(=<<)`:

``````(=<<) :: (a -> m b) -> m a -> m b
(=<<) = flip (>>=)
``````

However, it is rare to see this operator used in most code.

## A Sliding Scale of Power

Note: The title for this section is stolen straight from the Wikibooks page for Applicative Functors, which I would highly recommend you read for a more in-depth look at some of the concepts in this post.

By now, you hopefully have a reasonable grasp of the `Functor`, `Applicative` and `Monad` typeclasses. However, the relationship between them can feel somewhat arbitrary; the only thing they seem to have in common is "holding values". Let's look at the characteristic functions of the three typeclasses:

``````fmap :: (Functor f) => (a -> b) -> f a -> f b
(<*>) :: (Applicative f) => f (a -> b) -> f a -> f b
(>>=) :: (Monad m) => (a -> f b) -> f a -> f b
``````

These look quite distinct. However, if we replace `fmap` with `(<\$>)`, `(>>=)` with its flipped variant `(=<<)`, and align the signatures slightly, the similarities become clear:

``````(<\$>) :: (Functor     t) =>   (a ->   b) -> (t a -> t b)
(<*>) :: (Applicative t) => t (a ->   b) -> (t a -> t b)
(=<<) :: (Monad       t) =>   (a -> t b) -> (t a -> t b)
``````

These functions are all higher-order functions, which "lift" a function to the level of a functor. The difference between the three interfaces is the specific type of function being lifted. `(<\$>)` lifts simple ```a -> b``` functions into the functor; `(<*>)` lifts "wrapped" functions; and `(=<<)` lifts "monadic" functions.

These similarities may suggest to you that it is actually possible to use only the monadic interface to write valid `Functor` and `Applicative` implementations (assuming we implement `return` instead of `pure`). The definitions would be as follows:

``````pure = return
f <\$> x = x >>= pure . f
f <*> x =
f >>= \f' ->
x >>= \x' ->
pure (f' x')
``````

Why don't we do this?

The answer is generalisation. `Applicative` provides a much more powerful interface than `Functor`; similarly, `Monad` is much more powerful than `Applicative`. There therefore exist types which are functors, but not applicatives (such as tagged values); as well as types which are applicatives, but not monads (such as `ZipList`). (Besides, it's nice to know what a function is able to do with its arguments, and using the appropriate constraint helps with that; this is a part of type-oriented programming). How can we see this difference in power?

The answer is by asking how these functions can affect the context of a value. Functors are incredibly limited. By the functor laws, they must leave the context unchanged. This means that, for instance, `fmap`ing a function over a list cannot change the length of that list; nor can mapping over an IO action perform more IO; nor does fmapping over a `Reader` look at the environment; etc.

`(<*>)` is able to change the context. It takes two wrapped arguments, which means it receives two contexts that it must combine. The meaning of this varies, but it may involve sequencing actions - as with `IO` - or multiplying lengths - as with lists - etc. However, it is subject to a different restriction. For some `x <*> f`, while the contexts of `x` and `f` can affect the output context, the values stored cannot. To give a concrete example:

``````Just f <*> Just x
``````

The result of this expression will always use the `Just` constructor, no matter the values of `f` and `x`. Similarly:

``````[f, g] <*> [x, y]
``````

No matter the values of `f`, `g`, `x` and `y` in this example, the resulting list will always be 4 elements long.

You may, then, have guessed that monads remove this restriction. The defining feature of a monad is fundamentally the ability for values to affect context. Here is a simple example of this happening:

``````Just x >>= \y -> if y == 0 then Nothing else Just y
``````

In the above example, the value of `x` affects the context of the output. A more tangible example may come from IO:

``````getLine >>= \x -> if x == "" then putStrLn "Empty!" else putStrLn "Not empty!"
``````

In this example, the value which is read from standard input affects the context of the result - that is, the IO actions taken. This increased flexibility comes at the price of having fewer guarantees about what your functions do; a function with a `Functor` restriction is guaranteed to not change the context, whereas a function with a `Monad` restriction can effectively do anything.

## Conclusion

This post barely scratches the surface on the usefulness of monads. If you are interested in further reading, I recommend the following: