Monads are important in Haskell, and they are used in many scenarios. The concept of monads can be confusing at first, but in this chapter, you will learn what monads are and how to use them in complex programs.
Introduction
A
monad
is a way for values to be used in sequences of computations, resulting in a structure of computations. The sequential building blocks can be used to create computations, and the building blocks themselves can be structured as computations. As the official Haskell documentation states, “It is useful to think of a monad as a strategy for combining computations into more complex computations.”
A monad is characterized by these three elements:
A type constructor m
(when working with monads, it is a good practice to name the type constructor m)
A return function
, which returns values of the type m
A binding operation (>>=)
, which, by combining values of type m with computations that output values of type m, are used for producing new computations for m values
At the same time,
return and
>>= must follow
three laws—right unit, left unit, and associativity. We will talk about these rules later in this chapter. A general representation of a monad is shown here:
data m a = ...
return :: a -> m a
(>>=) :: m a -> (a -> m b) -> m b
On the first line, the type of the monad is m. On the second line, the value a is taken by the return function and is embedded into the monad m. On the third line, the binding function takes the monad instance m a and a computation that produces a monad instance m b from a’s and produces the new monad instance m b.
One of the most common monads is the
Maybe monad
, whose type constructor
m is
Maybe.
return and the binding operator have the following definition:
data Maybe a = Nothing | Just a
return :: a -> Maybe a
return x = Just x
(>>=) :: Maybe a -> (a -> Maybe b) -> Maybe b
m >>= g = case m of
Nothing -> Nothing
Just x -> g x
Looking at the general structure of a monad and the definition of the Maybe monad, you can say the following about the Maybe monad: the type constructor is Maybe, and the return function takes a value and wraps it with Just, bringing the value into Maybe. The binding function takes as parameters the value m :: Maybe a and the function g :: a -> Maybe b. In other words, it looks like this: (a -> Maybe b) == g. It also shows how to work with g to m: if m is Nothing, then the result also will be Nothing, or g is applied to x, resulting in a value of Maybe b.
The Three Rules
You have seen that a monad must follow three rules: right unit, left unit, and associativity. These three rules
show you the relation between a computation, the return function, and the binding operation.
All monads are instances of the
Monad type class from Prelude, which is defined as follows:
class Monad m where
return :: a -> m a
fail :: String -> m a
(>>=) :: m a -> (a -> m b) -> m b
(>>) :: m a -> m b -> m b
In this definition, the last rule can be expressed in terms of the third rule. Note that (>>=) is read as “bind,” and (>>) is read as “then.”
Before going further, we need to mention that the do notation works great with monads; it acts as syntactic sugar for operations. You will see some examples in the next sections.
The Right Unit
This
rule
states the following:
In this rule, f represents a computation. The rule says that if you make a computation f whose output is taken by return, then all that you did is nothing other than a computation. An example is the getLine function
. The right unit rule applied on getLine states that reading a string and then returning the value is the same thing as just reading the string.
Using the
do notation, the right unit rule says that the following programs make the same thing:
rightUnit1 = do
x <- f
return x
rightUnit2 = do
f
The Left Unit
This
rule
states the following:
In this rule, f is a computation, and a is a value. The rule says that if the result of a computation is a despite everything and you pass it to a computation f, then all what you did is to apply f directly on a. An example is the putStrLn function
. The left unit rule applied on putStrLn says that if putStrLn takes a computation whose result is the value a, then this is the same thing as printing the value a.
Using the
do notation, the right unit rule says that the following programs make the same thing:
leftUnit1 = do
x <- return a
f x
Associativity
The third
rule
says the following:
f >>= (x -> g x >>= h) ≡ (f >>= g) >>= h
In this representation, the ≡ sign means “is equivalent.” For short, this is the associativity rule for monads. To better understand, let’s simplify the rule for the moment.
f >>= (g >>= h) ≡ (f >>= g) >>= h
In this version of the rule, it is pretty simple to identify the associativity. In other words, this means that when you make computations, it doesn’t matter how they are grouped. Think of it as number addition: it doesn’t matter how you group the numbers when you add them.
Next, let’s take a look at (x -> g x >>= h). This says that you take a value x, perform the computation g on the x, and send the result to h. The right side (f >>= g) >>= h says that the result of f is sent to g, and the result of g (performed on the result of f) is sent to h.
This a little complicated, but in a few words, the last rule
says that when you have three computations, it doesn’t matter the manner in which you group them because the result will be the same in all scenarios.
Using the
do notation, the right unit rule says that the following programs make the same thing:
associativity1 = do
x <- f
do y <- g x
h y
associativity2 = do
y <- do x <- f
g x
h y
It is important to know that these three rules need to be assured by the programmer.
An Example
In this section, you will use the code examples provided at Yet Another Haskell Tutorial.
Let’s suppose you want to define a
binary tree
and then create a particular version of the
map function
that will apply a function to every leaf in the tree. It would look like this:
data Tree a
= Leaf a
| Branch (Tree a) (Tree a) deriving Show
mapTree :: (a -> b) -> Tree a -> Tree b
mapTree f (Leaf a) = Leaf (f a)
mapTree f (Branch lhs rhs) =
Branch (mapTree f lhs) (mapTree f rhs)
This works just fine, but if you want to count the leaves from left to right, it would fail. To do this, you need
a to use a
state, which counts the leaves thus far. The function that uses states is called
mapTreeState
, and it is defined as follows:
mapTreeState :: (a -> state -> (state, b)) ->
Tree a -> state -> (state, Tree b)
mapTreeState f (Leaf a) state =
let (state', b) = f a state
in (state', Leaf b)
mapTreeState f (Branch lhs rhs) state =
let (state' , lhs') = mapTreeState f lhs state
(state'', rhs') = mapTreeState f rhs state'
in (state'', Branch lhs' rhs')
The differences between
mapTree and
mapTreeState are that there are more arguments for
f and the type
-> Tree b was replaced with
-> state -> (state, Tree b). To make it easier to work, let’s use a type synonym declaration for the state, as shown here:
type State st a = st -> (st, a)
Next, add the following two functions that work on states:
returnState :: a -> State st a
returnState a = st -> (st, a)
bindState :: State st a -> (a -> State st b) ->
State st b
bindState m k = st ->
let (st', a) = m st
m' = k a
in m' st'
The function returnState
keeps the state st and returns the value a. In other words, for the value a, it generates something of type State st a.
The function bindState
transforms a into b. It works as follows: the initial state st is applied to m (whose type is State st a), resulting in a new state st and the value a. Next, applying the function k on a, it results in m' (whose type is State st b). Lastly, m' and the new state st' run.
Further, a new function is created, which uses the functions
returnState and
bindState.
mapTreeStateM :: (a -> State st b) -> Tree a -> State st (Tree b)
mapTreeStateM f (Leaf a) =
f a `bindState` ->
returnState (Leaf b)
mapTreeStateM f (Branch lhs rhs) =
mapTreeStateM f lhs `bindState` lhs' ->
mapTreeStateM f rhs `bindState`
hs' ->
returnState (Branch lhs' rhs')
For a
Leaf
, the function f is applied to a, whose result is bound to a function that generates a Leaf with other value. For a
Branch
, the function begins with the left side and binds the result to a function that begins with the right side, whose result is bound with a function that generates a new Branch.
Having all these, you can say that State st is actually a monad with return implemented as returnState
and (>>=) implemented as bindState
. In [7], it is proved that these functions follow the three rules for monads.
To take it a step further, you can create the
State st instance of
Monad, but just writing
instance Monad (State st) where { ... } won’t work, because instances cannot be made from non-fully-applied type synonyms. To improve this, you can convert the type synonym to a
newtype.
newtype State st a = State (st -> (st, a))
This implies that the
State constructor
needs to be packed and unpacked for the
Monad instance declaration.
import Control.Applicative
import Control.Monad (liftM, ap)
instance Functor (State state) where
fmap = liftM
instance Applicative (State state) where
pure = return
(<*>) = ap
newtype State st a = State (st -> (st, a))
instance Monad (State state) where
return a = State (state -> (state, a))
State run >>= action = State run'
where run' st =
let (st', a) = run st
State run" = action a
in run'' st'
Putting it all together, the function
mapTreeM
looks like this:
mapTreeM :: (a -> State state b) -> Tree a ->
State state (Tree b)
mapTreeM f (Leaf a) = do
b <- f a
return (Leaf b)
mapTreeM f (Branch lhs rhs) = do
lhs' <- mapTreeM f lhs
rhs' <- mapTreeM f rhs
return (Branch lhs' rhs')
If the type signature is removed, then a more general version of
mapTreeM is obtained.
mapTreeM :: Monad m => (a -> m b) -> Tree a ->
m (Tree b)
In fact,
mapTreeM can be applied in any monad, not just in
State. Now, let’s see some functions that take a current state and change it.
getState :: State state state
getState = State (state -> (state, state))
putState :: state -> State state ()
putState new = State (\_ -> (new, ()))
The function getState
returns the value of the current state, while putState inserts a new state, ignoring the current state.
Finally, to count the leaves, you can use the following function:
numberTree :: Tree a -> State Int (Tree (a, Int))
numberTree tree = mapTreeM number tree
where number v = do
cur <- getState
putState (cur+1)
return (v,cur)
To run the action, you should provide an initial state.
runStateM :: State state a -> state -> a
runStateM (State f) st = snd (f st)
Now let’s put it all together. The final code should look like this:
import Control.Applicative
import Control.Monad (liftM, ap)
instance Functor (State state) where
fmap = liftM
instance Applicative (State state) where
pure = return
(<*>) = ap
data Tree a
= Leaf a
| Branch (Tree a) (Tree a) deriving Show
newtype State st a = State (st -> (st, a))
instance Monad (State state) where
return a = State (state -> (state, a))
State run >>= action = State run'
where run' st =
let (st', a) = run st
State run'' = action a
in run'' st'
mapTreeM :: Monad m => (a -> m b) -> Tree a -> m (Tree b)
mapTreeM f (Leaf a) = do
b <- f a
return (Leaf b)
mapTreeM f (Branch lhs rhs) = do
lhs' <- mapTreeM f lhs
rhs' <- mapTreeM f rhs
return (Branch lhs' rhs')
getState :: State state state
getState = State (state -> (state, state))
putState :: state -> State state ()
putState new = State (\_ -> (new, ()))
numberTree :: Tree a -> State Int (Tree (a, Int))
numberTree tree = mapTreeM number tree
where number v = do
cur <- getState
putState (cur+1)
return (v,cur)
runStateM :: State state a -> state -> a
runStateM (State f) st = snd (f st)
Put it into a file called
Tree.hs and then load it into GHCi (don’t forget to change the current directory with the directory that contains the file
Tree.hs).
Prelude> :load Tree.hs
[1 of 1] Compiling Main ( Tree.hs, interpreted )
Ok, one module loaded.
And now, let’s see an example of tree.
testTree =
Branch
(Branch
(Leaf 'a')
(Branch
(Leaf 'b')
(Leaf 'c')))
(Branch
(Leaf 'd')
(Leaf 'e'))
Let’s apply the function
runStateM
and then print values in leaves.
*Main> runStateM (numberTree testTree) 1
Branch (Branch (Leaf ('a',1)) (Branch (Leaf ('b',2)) (Leaf ('c',3)))) (Branch (Leaf ('d',4)) (Leaf ('e',5)))
*Main> mapTreeM print testTree
'a'
'b'
'c'
'd'
'e'
Branch (Branch (Leaf ()) (Branch (Leaf ()) (Leaf ()))) (Branch (Leaf ()) (Leaf ()))
Useful Combinators
In the
Monad/Control.Monad, you can find some useful monadic
combinators
(note that
m is an instance of
Monad).
(=<<) :: (a -> m b) -> m a -> m b
mapM :: (a -> m b) -> [a] -> m [b]
mapM_ :: (a -> m b) -> [a] -> m ()
filterM :: (a -> m Bool) -> [a] -> m [a]
foldM :: (a -> b -> m a) -> a -> [b] -> m a
sequence :: [m a] -> m [a]
sequence_ :: [m a] -> m ()
liftM :: (a -> b) -> m a -> m b
when :: Bool -> m () -> m ()
join :: m (m a) -> m a
We will not discuss these combinators here, so please check the documentation.
Summary
In this chapter, you learned about monads.
As a final remark in this chapter, monads are extremely important in Haskell, so you need to understand them well.
References
- 1.
C. A. R. Hoareetal, “Tackling the Awkward Squad: Monadic Input/Output, Concurrency, Exceptions, and Foreign-Language Calls in Haskell,” Engineering Theories of Software Construction” (2001)
- 2.
M. Maruseac, A. S. Mena, A. Abel, A. Granin, H. Apfelmus, D. Austin, and J. Breitner, “Haskell Communities and Activities Report” (2017)
- 3.
M. P. Jones and L. Duponcheel, “Composing Monads,” Technical Report YALEU/DCS/RR-1004 (Department of Computer Science, Yale University, 1993)
- 4.
T. Schrijvers, and B. CdS Oliveira, “Monads, Zippers, and Views: Virtualizing the Monad Stack,” ACM SIGPLAN Notices 46.9: 32–44 (2011)
- 5.
J. Hedges, “Monad Transformers for Backtracking Search,” arXiv preprint arXiv:1406.2058 (2014)
- 6.
- 7.
- 8.
