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?
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!
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.
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.
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.
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
]
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.
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.
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.
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, 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.
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.