© Stefania Loredana Nita and Marius Mihailescu 2019
Stefania Loredana Nita and Marius MihailescuHaskell Quick Syntax Referencehttps://doi.org/10.1007/978-1-4842-4507-1_12

12. Monads

Stefania Loredana Nita1  and Marius Mihailescu1
(1)
Bucharest, Romania
 

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.”1

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:
f >>= return ≡ f

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:
return a >>= f ≡ f a

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
leftUnit2 = do
  f a

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.2

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.3

Summary

In this chapter, you learned about monads.
  • What a monad is

  • What the rules are that structures and computations need to follow to be considered a monad

  • How to create a monad

  • What are some useful combinators

As a final remark in this chapter, monads are extremely important in Haskell, so you need to understand them well.

References

  1. 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. 2.

    M. Maruseac, A. S. Mena, A. Abel, A. Granin, H. Apfelmus, D. Austin, and J. Breitner, “Haskell Communities and Activities Report” (2017)

     
  3. 3.

    M. P. Jones and L. Duponcheel, “Composing Monads,” Technical Report YALEU/DCS/RR-1004 (Department of Computer Science, Yale University, 1993)

     
  4. 4.

    T. Schrijvers, and B. CdS Oliveira, “Monads, Zippers, and Views: Virtualizing the Monad Stack,” ACM SIGPLAN Notices 46.9: 32–44 (2011)

     
  5. 5.

    J. Hedges, “Monad Transformers for Backtracking Search,” arXiv preprint arXiv:1406.2058 (2014)

     
  6. 6.
     
  7. 7.
     
  8. 8.
     
..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.
Reset
3.147.69.50