Monads

Another incredibly useful tool is to be able to perform composition in context. That is, that given something of f a and a function from a -> f b, how do we get an f b?

Consider the following example. We can write 123 divided by 4 and then divided by 5 via the following straightforward program:

x, y, z :: Int
x = 123
y = (`div` 4) x
z = (`div` 5) y

However, we know that div is unsafe since dividing it by 0 gives a zero division error. Therefore, we should write a safe div function that returns Nothing if division by 0 is to be expected:

safeDiv x y :: Int -> Maybe Int
safeDiv x 0 = Nothing
safeDiv x y = div x y

However, composing safeDiv is now no longer straightforward:

x = 123
y = (`safeDiv` 4) x
z = ???

     safeDiv                             safeDiv
        ┏━━━━                ?              ┏━━━━
Int ━━━━┫      Maybe Int  <----->   Int ━━━━┫     Maybe Int
        ┗━━━━                               ┗━━━━

Let us try using fmap:

x :: Int
x = 123

y :: Maybe Int
y = (`safeDiv` 4) x

z :: Maybe (Maybe Int)
z = fmap (`safeDiv` 5) y

Although this typechecks, the resulting type Maybe (Maybe Int) is incredibly awkward. It tells us that there is potentially a Maybe Int term, which means that there is potentially a potential Int. What would be better is to collapse the Maybe (Maybe Int) into just Maybe Int.

For this, we introduce the notion of a Monad, which again, can be described by a typeclass with some rules governing their methods. The primary feature of a Monad m is that it is an Applicative where we can collapse an m (m a) into an m a in the most obvious way. However, for convenience's sake, Haskell defines the Monad typeclass in a slightly different (but otherwise equivalent) formulation¹:

class Applicative m => Monad m where
    return :: a -> m a -- same as pure
    (>>=) :: m a -> (a -> m b) -> m b -- composition in context

These methods are governed by the following laws:

• Left identity: return a >>= h = h a
• Right identity: m >>= return = m
• Associativity: (m >>= g) >>= h = m >>= (\x -> g x >>= h)

return is practically the same as pure (in fact it is almost always defined as return = pure). Although the word return feels incredibly odd, we shall see very shortly why it was named this way. >>= is known as the monadic bind^{1 2}, and allows us to perform computation in context on a term in context, thereby achieving composition in context.

>>= is somewhat similar to fmap, in that while fmap allows us to apply an a -> b onto an f a, >>= allows us to apply an a -> m b onto an m a.

Let us see an instance of Monad:

instance Monad Maybe where
    return :: a -> Maybe a
    return = pure

    (>>=) :: Maybe a -> (a -> Maybe b) -> Maybe b
    Nothing >>= _ = Nothing
    Just x >>= f  = f x

With this instance, instead of using fmap to bring our Maybe Int into a Maybe (Maybe Int), we can use >>= to just bring it to a Maybe Int!

x :: Int
x = 123

y :: Maybe Int
y = (`safeDiv` 4) x

z :: Maybe Int
z = y >>= (`safeDiv` 5)

As we know, function composition (g . f) x is sort of to say "do f and then do g on x". Similarly, when f and g are computations in context and x is a term in context, x >>= f >>= g also means "do f and then do g on x"! However, >>= is incredibly powerful because the actual definition of >>= depends on the monad you use—therefore, monads allow us to overload composition in context!³

     safeDiv   |                       safeDiv
        ┏━━━━  |                          ┏━━━━
Int ━━━━┫      | Maybe Int  >>=   Int ━━━━┫     Maybe Int
        ┗━━━━  |                          ┗━━━━

Therefore, if you had f :: a -> b and g :: b -> c and x :: a, you would write g (f x) for f and then g. However, if you had f :: a -> m b and g :: b -> m c and x :: m a, you would write x >>= f >>= g for f and then g.

Beyond the Railways

As we know, data structures like Maybe, Either and Validation support the railway pattern, and them being functors, applicatives and (in the case of Maybe and Either) monads makes them ergonomic to use. However, the use of functors, applicatives and monads extend beyond just the railway pattern.

As described in Chapter 4.1 (Context/Notions of Computation), types like [] and IO provide context around a type. As it turns out, these types are also functors, applicatives and monads. While we have not touched IO at all so far, and will only do so in the next chapter, let us see the instance definitions for []:

instance Functor [] where
    fmap :: (a -> b) -> [a] -> [b]
    fmap = map

instance Applicative [] where
    pure :: a -> [a]
    pure x    = [x]

    (<*>) :: [a -> b] -> [a] -> [b]
    fs <*> xs = [f x | f <- fs, x <- xs]

instance Monad []  where
    return :: a -> [a]
    return = pure

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

Observe the definition of >>= for lists. The idea is that whatever fmap f xs produces (which is a 2+D list), xs >>= f flattens that result (it doesn't flatten it recursively, just the top layer). It does so by applying f onto every single xs in the list. As per the type signature, each f x produces a term of the type [b], which is a list. We extract each y from that list, and put them all as elements of the resulting list. Let us see the action of >>= through an example:

ghci> fmap (\x -> return x) [1, 2, 3]
[[1], [2], [3]] -- fmap gives a 2D list
ghci> [1, 2, 3] >>= (\x -> return x)
[1, 2, 3]       -- >>= gives a 1D list

ghci> fmap (\x -> return (x, x + 1)) [1, 2, 3]
[[(1, 2)], [(2, 3)], [(3, 4)]] -- fmap gives a 2D list
ghci> [1, 2, 3] >>= (\x -> return (x, x + 1))
ghci> [(1, 2), (2, 3), (3, 4)] -- >>= gives a 1D list

ghci> [1, 2] >>= (\x -> [3] >>= (\y -> >>= return (x, y)))
[(1, 3), (2, 3)]

The last function can be written a little more clearly. Suppose we want to write a function that produces the "cartesian product" of two lists. Writing this function using the monad methods can look unwieldy, but will ultimately pay off as you will see shortly:

cartesian_product :: [a] -> [b] -> [(a, b)]
cartesian_product xs ys = xs >>= (\x -> 
                          ys >>= (\y -> 
                          return (x, y)))

As we expect, everything works!

ghci> cartesian_product [1,2] [3]
[(1,3),(2,3)]

Do-notation

The definition of cartesian_product above is hard to read. However, this form of programming is (as you will surely see) very common—we bind each x from xs, then bind each y from ys, and return (x, y). Why not let us write the same implementation in this way:

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

Wouldn't this be much more straightforward? In fact, Haskell supports this! This is known as do notation, and is supported as long as the expression's type is a monad. do notation is just syntactic sugar for a series of >>= and lambda expressions:

do e1 <- e2           ==>      e2 >>= (\e1 -> whatever code)
   whatever code

Therefore, the definition of cartesian_product using do notation is translated as follows:

do x <- xs                 xs >>= (\x ->              xs >>= (\x ->
   y <- ys           ==>      do y <- ys         ==>  ys >>= (\y ->
   return (x, y)                 return (x, y))       return (x, y)))

More importantly, go back to the definition of cartesian_product using do notation. Compare that definition with the (more-or-less) equivalent definition in Python:

def cartesian_product(xs, ys):
    for x in xs:
        for y in ys:
            yield (x, y)

What we have done was to recover imperative programming with do-notation! Even better: while for loops in Python only work on iterables, do notation in Haskell works on any monad!

-- do notation with lists
pairs :: [a] -> [(a, a)]
pairs ls = do x <- ls
              y <- ls
              return (x, y)

-- do notation with Maybe
z :: Maybe Int
z = do y <- 123 `safeDiv` 4
       y `safeDiv` 5

-- do notation with Either
parseUser :: String -> String -> String -> Either String User
parseUser name email salary
  = do e <- parseEmail email
       s <- parseSalary salary
       return $ User name e s

Other languages like Python, C etc. define keywords like for, while, if-else as part of the language so that programmers can use different meanings of what and then means. For example, a while loop lets you write programs like (1) check condition, and then (2) if its true do the loop body, and then (3) check the condition again, etc. In Functional Programming languages like Haskell, it is monads that decide what and then means—this is great because you get to define your own monads and decide what composition of computation means!

cartesian_product :: Monad m => m a -> m b -> m (a, b)
cartesian_product xs ys = do
    x <- xs
    y <- ys
    return (x, y)

ghci> cartesian_product [1, 2] [3]
[(1, 3), (2, 3)]
ghci> cartesian_product (Just 1) (Just 2)
Just (1, 2)
ghci> cartesian_product (Just 1) Nothing
Nothing
ghci> cartesian_product (Right 1) (Right 2)
Right (1, 2)
ghci> cartesian_product getLine getLine -- getLine is like input() in Python
alice -- user input
bob   -- user input
("alice","bob")

As you can tell, each monad has its own way of composing computation in context and has its own meaning behind the context it provides. This is why monads are such a powerful tool for functional programming! It is for this reason that we will dedicate the entirety of the next chapter to monads.