mlugg.co.uk

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.

There are already loads of explanations of this; why make another one?

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

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

The Almighty Monad

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 functors (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 is 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, fmaping 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:

Thanks for reading! I hope this was helpful to someone.