Monad #

Like functors, monads come from category theory.

For programmers, a monad can be viewed as a functor that implements additional functions, while respecting certain constraints.

Monads serve a variety of purposes in functional programs. This includes (among other) writing to a log, or reading data.

In this section, we will only focus on two of the simplest monads, namely the type of lists and the option type (as we did for functors).

In Haskell #

We have seen in the previous section that a functor is a generic type that implements the function fmap.

A monad is a functor that implements two additional functions

return :: (Monad m) => a -> m a

and

join :: (Monad m) => m (m a) -> m a

Example. We have seen how the generic type “List” (written [ ] in Haskell) can be made a functor by implementing fmap.

We will see that it can also be made a monad, by implementing return and join.

Warning. If you want to use the function join, then import the module Control.Monad.

Core functions #

return (also called pure) #

The function

return :: (Monad m) => a -> m a

specifies how to produce an element of type m a out of an element of type a.

Example (continued). For the monad “List”, return wraps an element into a singleton list.

It can be defined as

return :: a -> [a]
return x = [x]

join #

The function

join :: (Monad m) => m (m a) -> m a

“flattens” an m (m a) into an m a.

Example (continued). For the monad “List”, join concatenates the inner lists of a list of lists.

It can be defined as

join :: [[a]] -> [a]
join xss = [ x | xs <- xss, x <- xs ]

Concrete illustration.

join [["Bolzano", "Merano"], ["Trento", "Rovereto"]]

evaluates to

["Bolzano", "Merano", "Trento" , "Rovereto"]

Derived functions #

Two useful higher-order functions can be derived from join and fmap (recall that a monad is a functor, so it implements fmap). Both are infix functions, noted >>= and >=> respectivbely.

>>= (pronounced “bind”) #

The function >>= has type

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

Let x :: m a and f :: (a -> m b).
Then the evaluation of x >>= f:

• applies f to each a “wrapped” inside x, and
• “flattens” (with join) the resulting m (m b) into an m b.

Example (continued). For the monad “List”, the function >>= can be defined as follows:

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

Concrete illustration (continued). Let us introduce a product type for Italian provinces:

data Province = ProvinceC { name :: String, cities :: [String] }

The expression

[
  ProvinceC { name = "AltoAdige" , cities = ["Bolzano", "Merano"] },
  ProvinceC { name = "Trentino" ,  cities = ["Trento", "Rovereto"]}
] >>= cities

evaluates to

["Bolzano", "Merano", "Trento" , "Rovereto"]

Observe that this is a list of strings (rather than a list of lists of strings).

Syntax. For the monad “List”, the function >>= may be easier to understand if we intuitively “swap” the order of its arguments.

The corresponding function is called concatMap. It can be defined as:

concatMap :: (a -> [b]) -> [a] -> [b]
concatMap f xs = xs >>= f    -- swap the order of `f` and `xs`

The type of concatMap is closer to the types of other higher-order functions encountered for lists: map, filter, etc.

So we can write

concatMap cities
[
  ProvinceC { name = "AltoAdige" , cities = ["Bolzano", "Merano"] },
  ProvinceC { name = "Trentino" ,  cities = ["Trento", "Rovereto"]}
]

Usage of >>= VS fmap VS function application #

Recap. The following table recaps when >>=, fmap and plain function application can be used, for some function f and expression x (depending on their types).

For instance, the first line reads as follows:

$\qquad$ if x has type a and f has type a -> b, then f x has type b.

type of $x$	type of $f$	expression $e$	equivalent expression $e'$	type of $e$ (and $e’$)
a	a -> b	f x	x & f	b
m a	a -> b	fmap f x	x & (fmap f)	m b
m a	a -> m b		x >>= f	m b

preds :: Int -> [Int]
preds x = [ y | y <- [0,1,2], y < x ]

preds :: Int -> [Int]
preds x = [ y | y <- [0,1,2], y < x ]

Derivation #

To go further. The function >>= need not be implemented if join and fmap already are. It can be derived as

(>>=) :: m a -> (a -> m b) -> m b
x >>= f = join (fmap f x)

We can also implement >>= and derive join from it, as follows:

join :: m (m a) -> m a
join x = x >>= id

So there is an alternative (equivalent) way to define a monad, where >>= is primitive and join is derived from it.

You will find this alternative definition in some textbooks or websites. This is also how join is implemented within the standard Haskell libraries.

>=> (pronounced “fish”) #

Another convenient function that can be derived from return and join is:

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

Intuitively, the relation between >>= and >=> is analogous to the relation between function application and function composition (or between their reversed versions & and >>>).

Disclaimer. Due to limited time, we will not cover (>=>) it in this course.

But if you know how, then feel free to use it in your assignments or exam.

Constraints #

We have seen earlier that the function fmap must satisfy additional constraints (sometimes called the functor laws) for a generic type to be a mathematically valid functor.

Similarly, the functions associated to a monad (e.g. return and join) must satisfy certain constraints.

Disclaimer. Due to limited time, we will not see these constraints in this course.

We refer to this page for a good introduction (in particular, these constraints may be easier to understand when expressed over return and >=>).

Maybe as a monad #

We have seen above how the functor “List” (noted [ ] in Haskell) can be made a monad, by implementing the functions return an join.

We will now do this with the functor Maybe.

Reminder. Maybe is the option type of Haskell. It is declared as:

data Maybe a = Nothing | Just a

return #

The function return for the type Maybe simply wraps a value (with the constructor Just):

return :: a -> Maybe a
return x = Just x

join #

The function join for the type Maybe transforms a Maybe (Maybe a) into a Maybe a in the expected way:

join :: Maybe (Maybe a) -> Maybe a
join (Just (Just x)) = Just x
-- covers the two remaining cases: `Nothing` and `Just Nothing`
join _ = Nothing

>>= #

The function >>= for the type Maybe can be defined as

(>>=) :: Maybe a -> (a -> Maybe b) -> Maybe b
-- propagate `Nothing`
Nothing >>= _ = Nothing
-- otherwise apply the function
Just x >>= f = f x

Equivalently, it can be derived from join and fmap, as explained above.

Example. Consider the function

maybeLog :: Float -> Maybe Float
maybeLog x | x < 0 = Nothing                 -- if the input is negative, then return `Nothing`
           | otherwise = Just (logBase 2 x)  -- otherwise compute its log base 2

The function >>= lets us apply maybeLog to an optional input.
For instance

Nothing >>= maybeLog          -- evaluates to `Nothing`

$\qquad$

Just (-8) >>= maybeLog       -- evaluates to `Nothing`

$\qquad$

 Just 8 >>= maybeLog          -- evaluates to `Just 3`

Usage #

The function >>= is convenient to chain computations that may “fail” (i.e. return Nothing): it lets us write code that automatically takes care of propagating failures (a.k.a. “null values”) in such scenarios.

Example (continued). In addition to maybeLog, consider the function

safeDiv :: Float -> Float -> Maybe Float
safeDiv _ 0 = Nothing          -- if the divisor is `0`, then return `Nothing`
safeDiv x y = Just (x / y)     -- otherwise perform a division

Intuitively,

• safeDiv only “succeeds” for a divisor $\neq 0$, and
• maybeLog only “succeeds” for an input $\ge 0$.

The function >>= lets us feed the output of safeDiv to maybeLog, without the need to check whether safeDiv succeeded.
For instance:

safeDiv 4 0 >>= maybeLog          -- evaluates to `Nothing` (`safeDiv` "fails")

$\qquad$

safeDiv 24 (-3) >>= maybeLog      -- evaluates to `Nothing` (maybeLog` "fails")

$\qquad$

safeDiv 24 3 >>= maybeLog         -- evaluates to `Just 3` (`safeDiv` and `maybeLog` both "succeed")

myFunction :: [Float] -> Maybe Float
myFunction xs = xs & filter (/= 5)
                   & maybeLast
                 >>= maybeLog
                   & fmap (+ 1)

myFunction :: [Float] -> Maybe Float
myFunction xs = xs & filter (/= 5)
                   & maybeLast
                 >>= maybeLog
                   & fmap (+ 1)