Monads

In Haskell, there Monad provides a class.

class Monad f where
  return :: a -> f a
  (>>=) :: f a -> (a -> f b) -> f b -- 'bind'

Technically, a monad is a functor—that is, a map from types to types—associated with two operations, return and (>>=). The role of return is to bring an ordinary value of type a into the monad, by turning it into a new thing of type f a. The role of (>>=) is to sequence programs that have monadic effects. (>>=) takes a program of type f a, along with a program of type f b, but indexed by a value of type a (i.e., a function of type a -> f b), and gives back a program of type f b. Essentially, in m >>= k, m is providing some value of type a, which is allowed to somehow fill in k's missing a-shaped piece, giving back a result of type f b.

Monads must satisfy certain laws; in particular the following:

return a >>= k   =  k a                     -- Left identity
m >>= return     =  m                       -- Right identity
(m >>= n) >>= o  =  m >>= (\x -> n x >>= o) -- Associativity

One particular monad is the Maybe monad. Thus Maybe has the following monadic instance:

instance Monad Maybe where
  return        = Just
  Nothing >>= _ = Nothing
  Just a >>= k  = k a

Another example is the list monad:

instance Monad [] where
  return a     = [a]
  [] >>= _     = []
  (a:as) >>= k = k a ++ as >>= k

One great thing about using monads in Haskell is the availability of do notation. In particular, rather than writing a monadic program in the form

m >>= \x -> k x

one can write it using do notation as

do x <- m
   k x

For example, if one wanted to have a program that adds two numbers inside the Maybe monad, one could do the following:

addTwoNumbers :: Maybe Integer
addTwoNumbers = do m <- Just 3
                   n <- Just 2
                   return (m + n)

By unpacking the do notation, it's possible to rewrite this program as

Just 3 >>= \m -> Just 2 >>= \n -> return (m + n)

which computes to Just 5. If we wanted to have a program that fails, we could write the following instead:

addTwoNumbers :: Maybe Integer
addTwoNumbers = do m <- Just 3
                   n <- Just 2
                   i <- Nothing 
                   return (m + n)

This program fails because it attempts to pull an integer i out of a Nothing, i.e., a failed computation. Indeed, such failure results regardless of whether or not the hypothetical value i is actually used.

To take another example, imagine we want to do an operation on two numbers, but which, this time, are extracted from lists of integers. Then we could do, e.g.,

combineTwoNumbersFromLists :: [Integer]
combineTwoNumbersFromLists = do m <- [1, 2]
                                n <- [3, 4]
                                op <- [(+), (*)]
                                return (m `op` n)

This program should compute to

>>> combineTwoNumbersFromLists
[4,3,5,4,5,6,6,8]

Note that the order of the do statements affects the order of the integers as they occur in the computed result, although the identity and number of these integers won't vary. In particular, first 1 is added to 3, then 1 is multiplied by 3, then 1 is added to 4, then multiplied by 4, and then we do the same thing with 2.

In my opinion, the monad laws look a bit nice when presented using do notation.

do x <- return a   =  k a           -- Left identity
   k x
do x <- m          =  m             -- Right Identity
   return x
do y <- do x <- m  =  do x <- m     -- Associativity
           n x           y <- n x
   o y                   o y