Functors, Applicatives, and Monads in Haskell | Eric Way's Personal Site

Definitions, examples using Maybe and [], laws, and more.

Functors

We are familiar with map. It takes a function a -> b and a list of values [a] and produces another list of values[b]. We unwrap each value a from the list [a] and apply a -> b to it, collect all the results b, and wrap them again to produce the list [b]. Here [] is a wrapper around values and map is an operation defined based on the wrapper.

For another example, consider the wrapper Maybe. We could have a function a -> b and a Maybe a and we want to produce Maybe b. The semantic is similar. We try to unwrap a value from Maybe a:

• Sometimes we get an a because we have a Just a. Then we apply a -> b to it, collect the result b, and wrap it again with Just b, which is also a Maybe b.
• Other times we can get nothing because we have a Nothing. Then we simply produce Nothing. Note that this produced Nothing, which is a Maybe b, is different than the input Nothing, which is a Maybe a.

In either case, a Maybe b is produced.

The semantics can vary for different wrappers, but the pattern is the same. Generally, suppose we have a wrapper f. We would like to define an operation based on f, such that it takes a function a -> b and a wrapped value f a and produces another wrapped value f b. We call such an operation fmap, a generalization of map. With the definition of fmap, the wrapper f is called a functor.

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

fmap can also be written as the infix operator <$>.

Functor laws

A proper fmap must satisfy two laws:

fmap id			= id
fmap (g . h) 	= fmap g . fmap h

Due to currying, fmap g has type f a -> f b, where g :: a -> b. That is, given the function g, fmap g takes a wrapped value f a and produce another wrapped value f b.

The first law states that when g :: a -> a is the identity function, fmap g should also be the identify function (with type f a -> f a).

The second law states that function composition should be preserved for any functions g :: b -> c and h :: a -> b.

Applicatives

fmap has an annoying limit. It only accepts functions with one argument. But we might need more. For example, we might need to apply + to two Maybe Int‘s. We produce Just the sum of the two Int‘s if they are all Just, and Nothing if at least one of them is Nothing, i.e. (Just 2) + (Just 3) = (Just 5) and (Just 2) + Nothing = Nothing.

If we try to use fmap on this problem, what can we get? Remembering + :: Int -> Int -> Int, and we find that fmap + (Just 2) is Just (2+). We now have a function wrapped by Just! At this stage we can do nothing with a wrapped function, because in the definition of fmap the function a -> b is unwrapped.

So we introduce an operation <*> to handle wrapped functions:

(<*>)	::	f (a -> b) -> f a -> f b

We define <*> on Maybe such that, if Maybe (a -> b) and Maybe a are both Just‘s, we unwrap them, apply the function a -> b to the value a, obtain the result b, and wrap it to produce a Just b, which is Maybe b; otherwise, we simply produce a Nothing, which is also Maybe b.

And naturally, we now have (Just (2+)) <*> (Just 3) = (Just 5) and (Just (2+)) <*> Nothing = Nothing. If we expand Just (2+) and rewrite fmap as <$>, we now have

(+) <$> (Just 2) <*> (Just 3)

Looks nice, right?

To further illustrate, define a function

add :: Int -> Int -> Int -> Int
add x y z = x + y + z

and apply

add <$> (Just 2) <*> Nothing <*> (Just 3)

Step 1, applying fmap, we get

(Just (add 2)) <*> Nothing <*> (Just 3)

where Just (add 2) has type Maybe (Int -> Int -> Int).

Step 2, we feed Nothing to a wrapped function Just (add 2) , and we get

Nothing <*> (Just 3)

where Nothing has type Maybe (Int -> Int), which is a wrapped (but vanishing) function.

Step 3, “applying” the Nothing function to Just 3 and we get Nothing, due to the definition of <*>.

So applicatives are simply a way to handle curried functions in the context of wrappers by defining <*>.

As we have seen, applicatives (in effect) can defined using <$> and <*>. However, the formal way to define them is to use pure and <*>, where

pure :: a -> f a

which is simply “wrapping”. For example, for Maybe, pure a is Just a.

It is not hard to observe that <$> is in fact a combination of pure and <*>:

g <$> a = pure g <*> a

They are the same that we produce a wrapped function at “step 1” using fmap, and that we produce a wrapped function at “step 0” by directly wrapping it using pure.

List is also an applicative, where pure is to transform a value into a singleton list, and <*> is to apply a list of functions to a list of values and produce a “Cartesian product” of results (in a flattened list). Here it is intuitive to think of a list as “all possible values” of some variable, e.g. the solution to an equation. If x has possible values [1, 2, 5] and y has possible values [10, 20], what are the possible values of x + y? The answer is simply

(+) <$> [1, 2, 5] <*> [10, 20]

or equivalently

pure (+) <*> [1, 2, 5] <*> [10, 20]

which produces [11, 21, 12, 22, 15, 25].

Applicative laws

pure id <*> x		= x
pure (g x)			= pure g <*> pure x
x <*> pure y 		= pure (\g -> g y) <*> x
x <*> (y <*> z) 	= (pure (.) <*> x <*> y) <*> z

Monads

Let’s review what we have now, which is just pure and <*>, as fmap can be built from them. We know that pure is to wrap, and <*> takes a wrapped function f (a -> b) and a wrapped value f a to produce another wrapped value f b. Notice that the wrapped function f (a -> b) here, once unwrapped, is just another plain, ordinary, pure function a -> b. In another words, at this stage, we only have “pure” functions (albeit possibly wrapped).

We have been using the letter f for a wrapper. We now change it to m, for reasons you can easily guess.

Consider an “effectful” function of type a -> m b, which introduces a wrapper “internally”. For example, we might want to halve an Int and produce another Int. However, this is impossible, because odd numbers cannot be halved. So we can only produce a Maybe Int. If the input Int is an odd number, we produce a Nothing. Otherwise, we produce Just the input divided by 2. The function halve thus has type Int -> Maybe Int.

halve x | even x    = Just (x `div` 2)
        | otherwise = Nothing

What if we want to apply halve to an Int multiple times? The first time we do this, we get a Maybe Int. The second time we do this, we need to check whether this Maybe Int is a Just or a Nothing. If it is a Just, we proceed with the extracted Int; if it is a Nothing, we produce a Nothing and happily (or sadly?) skip all the following operations as the final result is bound to be a Nothing.

Here a recurring pattern is: given a wrapped value m a and an effectful function a -> m b, produce a wrapped value m b. We define the operator >>= to handle it:

(>>=)	:: m a -> (a -> m b) -> m b

So now we can use

halve 8 >>= halve >>= halve

or equivalently

pure 8 >>= halve >>= halve >>= halve

which evaluates to Just 1.

We also have

halve 6 >>= halve >>= halve

which evaluates to Nothing.

Note that we could have written

halve 6 >>= \x ->
halve x

but \x -> halve x is simply halve.

halve is a single-argument function. Consider the following function safediv:

safediv :: Int -> Int -> Maybe Int
safediv _ 0 = Nothing
safediv n m | n `mod` m == 0 = Just (n `div` m)
            | otherwise      = Nothing

It takes two Int‘s and produces a Maybe Int. Suppose we want to (safely) calculate $(20 / 5) / (4 / 2)$, using >>= and lambda expressions, we write

safediv 20 5 >>= \n ->
safediv 4 2  >>= \m ->
safediv n m

which produces Just 2.

Using syntactic sugar, the above can be refactored as

do
	n <- safediv 20 5
	m <- safediv 4 2
	safediv n m

A wrapper with operations >>= and pure defined is called a monad. For monads, pure is written as return with the same definition.

A list is also a monad. For a list xs :: [a] and a function g :: a -> [b], xs >>= g applied g to each of the elements in the list xs, collecting all the results values in a list. For example, define mySqrt as

mySqrt :: Float -> [Float]
mySqrt 0 = [0]
mySqrt x | x > 0 = [sqrt x, -(sqrt x)]
         | x < 0 = []

Then

[4, 0, -1, 9] >>= mySqrt

evaluates to [2.0, -2.0, 0.0, 3.0, -3.0], and

do
    x <- [4, 0, -1, 9]
    y <- mySqrt x
    mySqrt y

evaluates to [1.4142135, -1.4142135, 0.0, 1.7320508, -1.7320508].

Using lists as a monad is similar to list comprehensions:

pairs :: [a] -> [b] -> [(a,b)]
pairs xs ys = do
                x <- xs
                y <- ys
                return (x,y)

while equivalently,

pairs :: [a] -> [b] -> [(a,b)]
pairs xs ys = [(x,y) | x <- xs, y <- ys]

Monad laws

return x >>= f    = f x
mx >>= return     = mx
(mx >>= f) >>= g  = mx >>= (\x -> (f x >>= g))