Let's take another look at the parseP5 function that we wrote in Chapter 10, Code case study: parsing a binary data format.

-- file: ch10/PNM.hs
matchHeader :: L.ByteString -> L.ByteString -> Maybe L.ByteString

-- "nat" here is short for "natural number"
getNat :: L.ByteString -> Maybe (Int, L.ByteString)

getBytes :: Int -> L.ByteString
         -> Maybe (L.ByteString, L.ByteString)

parseP5 s =
  case matchHeader (L8.pack "P5") s of
    Nothing -> Nothing
    Just s1 ->
      case getNat s1 of
        Nothing -> Nothing
        Just (width, s2) ->
          case getNat (L8.dropWhile isSpace s2) of
            Nothing -> Nothing
            Just (height, s3) ->
              case getNat (L8.dropWhile isSpace s3) of
                Nothing -> Nothing
                Just (maxGrey, s4)
                  | maxGrey > 255 -> Nothing
                  | otherwise ->
                      case getBytes 1 s4 of
                        Nothing -> Nothing
                        Just (_, s5) ->
                          case getBytes (width * height) s5 of
                            Nothing -> Nothing
                            Just (bitmap, s6) ->
                              Just (Greymap width height maxGrey bitmap, s6)

When we introduced this function, it threatened to march off the right side of the page if it got much more complicated. We brought the staircasing under control using the (>>?) function.

-- file: ch10/PNM.hs
(>>?) :: Maybe a -> (a -> Maybe b) -> Maybe b
Nothing >>? _ = Nothing
Just v  >>? f = f v

We carefully chose the type of (>>?) to let us chain together functions that return a Maybe value. So long as the result type of one function matches the parameter of the next, we can chain functions returning Maybe together indefinitely. The body of (>>?) hides the details of whether the chain of functions we build is short-circuited somewhere, due to one returning Nothing, or completely evaluated.

Useful as (>>?) was for cleaning up the structure of parseP5, we had to incrementally consume pieces of a string as we parsed it. This forced us to pass the current value of the string down our chain of Maybes, wrapped up in a tuple. Each function in the chain put a result into one element of the tuple, and the unconsumed remainder of the string into the other.

-- file: ch10/PNM.hs
parseP5_take2 :: L.ByteString -> Maybe (Greymap, L.ByteString)
parseP5_take2 s =
    matchHeader (L8.pack "P5") s       >>?
    \s -> skipSpace ((), s)           >>?
    (getNat . snd)                    >>?
    skipSpace                         >>?
    \(width, s) ->   getNat s         >>?
    skipSpace                         >>?
    \(height, s) ->  getNat s         >>?
    \(maxGrey, s) -> getBytes 1 s     >>?
    (getBytes (width * height) . snd) >>?
    \(bitmap, s) -> Just (Greymap width height maxGrey bitmap, s)

skipSpace :: (a, L.ByteString) -> Maybe (a, L.ByteString)
skipSpace (a, s) = Just (a, L8.dropWhile isSpace s)

Once again, we were faced with a pattern of repeated behaviour: consume some string, return a result, and return the remaining string for the next function to consume. However, this pattern was more insidious: if we wanted to pass another piece of information down the chain, we'd have to modify nearly every element of the chain, turning each two-tuple into a three-tuple!

We addressed this by moving the responsibility for managing the current piece of string out of the individual functions in the chain, and into the function that we used to chain them together.

-- file: ch10/Parse.hs
(==>) :: Parse a -> (a -> Parse b) -> Parse b

firstParser ==> secondParser  =  Parse chainedParser
  where chainedParser initState   =
          case runParse firstParser initState of
            Left errMessage ->
                Left errMessage
            Right (firstResult, newState) ->
                runParse (secondParser firstResult) newState

We also hid the details of the parsing state in the ParseState type. Even the getState and putState functions don't inspect the parsing state, so any modification to ParseState will have no effect on any existing code.

We'll intentionally keep the internals of the Logger module abstract.

-- file: ch14/Logger.hs
module Logger
    (
      Logger
    , Log
    , runLogger
    , record
    ) where

Hiding the details like this has two benefits: it grants us considerable flexibility in how we implement our monad, and more importantly, it gives users a simple interface.

Our Logger type is purely a type constructor. We don't export the value constructor that a user would need to create a value of this type. All they can use Logger for is writing type signatures.

The Log type is just a synonym for a list of strings, to make a few signatures more readable. We use a list of strings to keep the implementation simple.

-- file: ch14/Logger.hs
type Log = [String]

Instead of giving our users a value constructor, we provide them with a function, runLogger, that evaluates a logged action. This returns both the result of an action and whatever was logged while the result was being computed.

-- file: ch14/Logger.hs
runLogger :: Logger a -> (a, Log)

The Monad typeclass doesn't provide any means for values to escape their monadic shackles. We can inject a value into a monad using return. We can extract a value from a monad using (>>=) but the function on the right, which can see an unwrapped value, has to wrap its own result back up again.

Most monads have one or more runLogger-like functions. The notable exception is of course IO, which we usually only escape from by exiting a program.

A monad execution function runs the code inside the monad and unwraps its result. Such functions are usually the only means provided for a value to escape from its monadic wrapper. The author of a monad thus has complete control over how whatever happens inside the monad gets out.

Some monads have several execution functions. In our case, we can imagine a few alternatives to runLogger: one might only return the log messages, while another might return just the result and drop the log messages.

When executing inside a Logger action, user code calls record to record something.

-- file: ch14/Logger.hs
record :: String -> Logger ()

Since recording occurs in the plumbing of our monad, our action's result supplies no information.

Usually, a monad will provide one or more helper functions like our record. These are our means for accessing the special behaviors of that monad.

Our module also defines the Monad instance for the Logger type. These definitions are all that a client module needs in order to be able to use this monad.

Here is a preview, in ghci, of how our monad will behave.

ghci> let simple = return True :: Logger Bool
ghci> runLogger simple
(True,[])

When we run the logged action using runLogger, we get back a pair. The first element is the result of our code; the second is the list of items logged while the action executed. We haven't logged anything, so the list is empty. Let's fix that.

ghci> runLogger (record "hi mom!" >> return 3.1337)
(3.1337,["hi mom!"])

Here's how we kick off our glob-to-regexp conversion inside the Logger monad.

-- file: ch14/Logger.hs
globToRegex cs =
    globToRegex' cs >>= \ds ->
    return ('^':ds)

There are a few coding style issues worth mentioning here. The body of the function starts on the line after its name. By doing this, we gain some horizontal white space. We've also “hung” the parameter of the anonymous function at the end of the line. This is common practice in monadic code.

Remember the type of (>>=): it extracts the value on the left from its Logger wrapper, and passes the unwrapped value to the function on the right. The function on the right must, in turn, wrap its result with the Logger wrapper. This is exactly what return does: it takes a pure value, and wraps it in the monad's type constructor.

ghci> :type (>>=)
(>>=) :: (Monad m) => m a -> (a -> m b) -> m b
ghci> :type (globToRegex "" >>=)
(globToRegex "" >>=) :: (String -> Logger b) -> Logger b

Even when we write a function that does almost nothing, we must call return to wrap the result with the correct type.

-- file: ch14/Logger.hs
globToRegex' :: String -> Logger String
globToRegex' "" = return "$"

When we call record to save a log entry, we use (>>) instead of (>>=) to chain it with the following action.

-- file: ch14/Logger.hs
globToRegex' ('?':cs) =
    record "any" >>
    globToRegex' cs >>= \ds ->
    return ('.':ds)

Recall that this is a variant of (>>=) that ignores the result on the left. We know that the result of record will always be (), so there's no point in capturing it.

We can use do notation, which we first encountered in the section called “Sequencing”, to somewhat tidy up our code.

-- file: ch14/Logger.hs
globToRegex' ('*':cs) = do
    record "kleene star"
    ds <- globToRegex' cs
    return (".*" ++ ds)

The choice of do notation versus explicit (>>=) with anonymous functions is mostly a matter of taste, though almost everyone's taste is to use do notation for anything longer than about two lines. There is one significant difference between the two styles, though, which we'll return to in the section called “Desugaring of do blocks”.

Parsing a character class mostly follows the same pattern that we've already seen.

-- file: ch14/Logger.hs
globToRegex' ('[':'!':c:cs) =
    record "character class, negative" >>
    charClass cs >>= \ds ->
    return ("[^" ++ c : ds)
globToRegex' ('[':c:cs) =
    record "character class" >>
    charClass cs >>= \ds ->
    return ("[" ++ c : ds)
globToRegex' ('[':_) =
    fail "unterminated character class"

Our definition of (>>=) ensures that messages logged on the left will appear in the new log before those on the right. However, it says nothing about when the values a and b are evaluated: (>>=) is lazy.

Like most other aspects of a monad's behaviour, strictness is under the control of the monad's implementor. It is not a constant shared by all monads. Indeed, some monads come in multiple flavours, each with different levels of strictness.

Our Logger monad is a specialised version of the standard Writer monad, which can be found in the Control.Monad.Writer module of the mtl package. We will present a Writer example in the section called “Using typeclasses”.

A function suitable for executing the Maybe monad is maybe. (Remember that “executing” a monad involves evaluating it and returning a result that's had the monad's type wrapper removed.)

-- file: ch14/Maybe.hs
maybe :: b -> (a -> b) -> Maybe a -> b
maybe n _ Nothing  = n
maybe _ f (Just x) = f x

Its first parameter is the value to return if the result is Nothing. The second is a function to apply to a result wrapped in the Just constructor; the result of that application is then returned.

Since the Maybe type is so simple, it's about as common to simply pattern-match on a Maybe value as it is to call maybe. Each one is more readable in different circumstances.

Here's an example of Maybe in use as a monad. Given a customer's name, we want to find the billing address of their mobile phone carrier.

-- file: ch14/Carrier.hs
import qualified Data.Map as M

type PersonName = String
type PhoneNumber = String
type BillingAddress = String
data MobileCarrier = Honest_Bobs_Phone_Network
                   | Morrisas_Marvelous_Mobiles
                   | Petes_Plutocratic_Phones
                     deriving (Eq, Ord)

findCarrierBillingAddress :: PersonName
                          -> M.Map PersonName PhoneNumber
                          -> M.Map PhoneNumber MobileCarrier
                          -> M.Map MobileCarrier BillingAddress
                          -> Maybe BillingAddress

Our first version is the dreaded ladder of code marching off the right of the screen, with many boilerplate case expressions.

-- file: ch14/Carrier.hs
variation1 person phoneMap carrierMap addressMap =
    case M.lookup person phoneMap of
      Nothing -> Nothing
      Just number ->
          case M.lookup number carrierMap of
            Nothing -> Nothing
            Just carrier -> M.lookup carrier addressMap

The Data.Map module's lookup function has a monadic return type.

ghci> :module +Data.Map
ghci> :type Data.Map.lookup
Data.Map.lookup :: (Ord k, Monad m) => k -> Map k a -> m a

In other words, if the given key is present in the map, lookup injects it into the monad using return. Otherwise, it calls fail. This is an interesting piece of API design, though one that we think was a poor choice.

In practice, everyone uses Maybe as the result type for lookup. The result type of such a conceptually simple function provides generality where it is not needed: lookup should have been written to return Maybe.

Let's set aside the API question, and deal with the ugliness of our code. We can make more sensible use of Maybe's status as a monad.

-- file: ch14/Carrier.hs
variation2 person phoneMap carrierMap addressMap = do
  number <- M.lookup person phoneMap
  carrier <- M.lookup number carrierMap
  address <- M.lookup carrier addressMap
  return address

If any of these lookups fails, the definitions of (>>=) and (>>) mean that the result of the function as a whole will be Nothing, just as it was for our first attempt that used case explicitly.

This version is much tidier, but the return isn't necessary. Stylistically, it makes the code look more regular, and perhaps more familiar to the eyes of an imperative programmer, but behaviourally it's redundant. Here's an equivalent piece of code.

-- file: ch14/Carrier.hs
variation2a person phoneMap carrierMap addressMap = do
  number <- M.lookup person phoneMap
  carrier <- M.lookup number carrierMap
  M.lookup carrier addressMap

When we introduced maps, we mentioned in the section called “Partial application awkwardness” that the type signatures of functions in the Data.Map module often make them awkward to partially apply. The lookup function is a good example. If we flip its arguments, we can write the function body as a one-liner.

-- file: ch14/Carrier.hs
variation3 person phoneMap carrierMap addressMap =
    lookup phoneMap person >>= lookup carrierMap >>= lookup addressMap
  where lookup = flip M.lookup

The list monad is similar to a familiar Haskell tool, the list comprehension. We can illustrate this similarity by computing the Cartesian product of two lists. First, we'll write a list comprehension.

-- file: ch14/CartesianProduct.hs
comprehensive xs ys = [(x,y) | x <- xs, y <- ys]

For once, we'll use bracketed notation for the monadic code instead of layout notation. This will highlight how structurally similar the monadic code is to the list comprehension.

-- file: ch14/CartesianProduct.hs
monadic xs ys = do { x <- xs; y <- ys; return (x,y) }

The only real difference is that the value we're constructing comes at the end of the sequence of expressions, instead of the beginning as in the list comprehension. Also, the results of the two functions are identical.

ghci> comprehensive [1,2] "bar"
[(1,'b'),(1,'a'),(1,'r'),(2,'b'),(2,'a'),(2,'r')]
ghci> comprehensive [1,2] "bar" == monadic [1,2] "bar"
True

It's easy to be baffled by the list monad early on, so let's walk through our monadic Cartesian product code again in more detail. This time, we'll rearrange the function to use layout instead of brackets.

-- file: ch14/CartesianProduct.hs
blockyDo xs ys = do
    x <- xs
    y <- ys
    return (x, y)

For every element in the list xs, the rest of the function is evaluated once, with x bound to a different value from the list each time. Then for every element in the list ys, the remainder of the function is evaluated once, with y bound to a different value from the list each time.

What we really have here is a doubly nested loop! This highlights an important fact about monads: you cannot predict how a block of monadic code will behave unless you know what monad it will execute in.

We'll now walk through the code even more explicitly, but first let's get rid of the do notation, to make the underlying structure clearer. We've indented the code a little unusually to make the loop nesting more obvious.

-- file: ch14/CartesianProduct.hs
blockyPlain xs ys =
    xs >>=
    \x -> ys >>=
    \y -> return (x, y)

blockyPlain_reloaded xs ys =
    concat (map (\x ->
                 concat (map (\y ->
                              return (x, y))
                         ys))
            xs)

If xs has the value [1,2,3], the two lines that follow are evaluated with x bound to 1, then to 2, and finally to 3. If ys has the value [True, False], the final line is evaluated six times: once with x as 1 and y as True; again with x as 1 and y as False; and so on. The return expression wraps each tuple in a single-element list.

Here is a simple brute force constraint solver. Given an integer, it finds all pairs of positive integers that, when multiplied, give that value (this is the constraint being solved).

-- file: ch14/MultiplyTo.hs
guarded :: Bool -> [a] -> [a]
guarded True  xs = xs
guarded False _  = []

multiplyTo :: Int -> [(Int, Int)]
multiplyTo n = do
  x <- [1..n]
  y <- [x..n]
  guarded (x * y == n) $
    return (x, y)

Let's try this in ghci.

ghci> multiplyTo 8
[(1,8),(2,4)]
ghci> multiplyTo 100
[(1,100),(2,50),(4,25),(5,20),(10,10)]
ghci> multiplyTo 891
[(1,891),(3,297),(9,99),(11,81),(27,33)]

Back in the section called “The offside rule is not mandatory”, we mentioned that layout is the norm in Haskell, but it's not required. We can write a do block using explicit structure instead of layout.

-- file: ch14/Do.hs
semicolon = do
  {
    act1;
    val1 <- act2;
    let { val2 = expr1 };
    actN;
  }

-- file: ch14/Do.hs
semicolonTranslated =
    act1 >>
    let f val1 = let val2 = expr1
                 in actN
        f _ = fail "..."
    in act2 >>= f

Even though this use of explicit structure is rare, the fact that it uses semicolons to separate expressions has given rise to an apt slogan: monads are a kind of “programmable semicolon”, because the behaviours of (>>) and (>>=) are different in each monad.

When we write (>>=) explicitly in our code, it reminds us that we're stitching functions together using combinators, not simply sequencing actions.

As long as you feel like a novice with monads, we think you should prefer to explicitly write (>>=) over the syntactic sugar of do notation. The repeated reinforcement of what's really happening seems, for many programmers, to help to keep things clear. (It can be easy for an imperative programmer to relax a little too much from exposure to the IO monad, and assume that a do block means nothing more than a simple sequence of actions.)

Once you're feeling more familiar with monads, you can choose whichever style seems more appropriate for writing a particular function. Indeed, when you read other people's monadic code, you'll see that it's unusual, but by no means rare, to mix both do notation and (>>=) in a single function.

The (=<<) function shows up frequently whether or not we use do notiation. It is a flipped version of (>>=).

ghci> :type (>>=)
(>>=) :: (Monad m) => m a -> (a -> m b) -> m b
ghci> :type (=<<)
(=<<) :: (Monad m) => (a -> m b) -> m a -> m b

It comes in handy if we want to compose monadic functions in the usual Haskell right-to-left style.

-- file: ch14/CartesianProduct.hs
wordCount = print . length . words =<< getContents

Let's develop some simple code that's almost the State monad, then we'll take a look at the real thing. We'll start with our type definition, which has exactly the obvious type we described above.

-- file: ch14/SimpleState.hs
type SimpleState s a = s -> (a, s)

Our monad is a function that transforms one state into another, yielding a result when it does so. Because of this, the state monad is sometimes called the state transformer monad.

Yes, this is a type synonym, not a new type, and so we're cheating a little. Bear with us for now; this simplifies the description that follows.

Earlier in this chapter, we said that a monad has a type constructor with a single type variable, and yet here we have a type with two parameters. The key here is to understand that we can partially apply a type just as we can partially apply a normal function. This is easiest to follow with an example.

-- file: ch14/SimpleState.hs
type StringState a = SimpleState String a

Here, we've bound the type variable s to String. The type StringState still has a type parameter a, though. It's now more obvious that we have a suitable type constructor for a monad. In other words, our monad's type constructor is SimpleState s, not SimpleState alone.

The next ingredient we need to make a monad is a definition for the return function.

-- file: ch14/SimpleState.hs
returnSt :: a -> SimpleState s a
returnSt a = \s -> (a, s)

All this does is take the result and the current state, and “tuple them up”. You may by now be used to the idea that a Haskell function with multiple parameters is just a chain of single-parameter functions, but just in case you're not, here's a more familiar way of writing returnSt that makes it more obvious how simple this function is.

-- file: ch14/SimpleState.hs
returnAlt :: a -> SimpleState s a
returnAlt a s = (a, s)

Our final piece of the monadic puzzle is a definition for (>>=). Here it is, using the actual variable names from the standard library's definition of (>>=) for State.

-- file: ch14/SimpleState.hs
bindSt :: (SimpleState s a) -> (a -> SimpleState s b) -> SimpleState s b
bindSt m k = \s -> let (a, s') = m s
                   in (k a) s'

Those single-letter variable names aren't exactly a boon to readability, so let's see if we can substitute some more meaningful names.

-- file: ch14/SimpleState.hs
-- m == step
-- k == makeStep
-- s == oldState

bindAlt step makeStep oldState =
    let (result, newState) = step oldState
    in  (makeStep result) newState

To understand this definition, remember that step is a function with the type s -> (a, s). When we evaluate this, we get a tuple, and we have to use this to return a new function of type s -> (a, s). This is perhaps easier to follow if we get rid of the SimpleState type synonyms from bindAlt's type signature, and examine the types of its parameters and result.

-- file: ch14/SimpleState.hs
bindAlt :: (s -> (a, s))        -- step
        -> (a -> s -> (b, s))   -- makeStep
        -> (s -> (b, s))        -- (makeStep result) newState

The definitions of (>>=) and return for the state monad simply act as plumbing: they move a piece of state around, but they don't touch it in any way. We need a few other simple functions to actually do useful work with the state.

-- file: ch14/SimpleState.hs
getSt :: SimpleState s s
getSt = \s -> (s, s)

putSt :: s -> SimpleState s ()
putSt s = \_ -> ((), s)

The getSt function simply takes the current state and returns it as the result, while putSt ignores the current state and replaces it with a new state.

The only simplifying trick we played in the previous section was to use a type synonym instead of a type definition for SimpleState. If we had introduced a newtype wrapper at the same time, the extra wrapping and unwrapping would have made our code harder to follow.

In order to define a Monad instance, we have to provide a proper type constructor as well as definitions for (>>=) and return. This leads us to the real definition of State.

-- file: ch14/State.hs
newtype State s a = State {
      runState :: s -> (a, s)
    }

All we've done is wrap our s -> (a, s) type in a State constructor. By using Haskell's record syntax to define the type, we're automatically given a runState function that will unwrap a State value from its constructor. The type of runState is State s a -> s -> (a, s).

The definition of return is almost the same as for SimpleState, except we wrap our function with a State constructor.

-- file: ch14/State.hs
returnState :: a -> State s a
returnState a = State $ \s -> (a, s)

The definition of (>>=) is a little more complicated, because it has to use runState to remove the State wrappers.

-- file: ch14/State.hs
bindState :: State s a -> (a -> State s b) -> State s b
bindState m k = State $ \s -> let (a, s') = runState m s
                              in runState (k a) s'

This function differs from our earlier bindSt only in adding the wrapping and unwrapping of a few values. By separating the “real work” from the bookkeeping, we've hopefully made it clearer what's really happening.

We modify the functions for reading and modifying the state in the same way, by adding a little wrapping.

-- file: ch14/State.hs
get :: State s s
get = State $ \s -> (s, s)

put :: s -> State s ()
put s = State $ \_ -> ((), s)

We've already used Parse, our precursor to the state monad, to parse binary data. In that case, we wired the type of the state we were manipulating directly into the Parse type.

The State monad, by contrast, accepts any type of state as a parameter. We supply the type of the state, to give e.g. State ByteString.

The State monad will probably feel more familiar to you than many other monads if you have a background in imperative languages. After all, imperative languages are all about carrying around some implicit state, reading some parts, and modifying others through assignment, and this is just what the state monad is for.

So instead of unnecessarily cheerleading for the idea of using the state monad, we'll begin by demonstrating how to use it for something simple: pseudorandom value generation. In an imperative language, there's usually an easily available source of uniformly distributed pseudorandom numbers. For example, in C, there's a standard rand function that generates a pseudorandom number, using a global state that it updates.

Haskell's standard random value generation module is named System.Random. It allows the generation of random values of any type, not just numbers. The module contains several handy functions that live in the IO monad. For example, a rough equivalent of C's rand function would be the following:

-- file: ch14/Random.hs
import System.Random

rand :: IO Int
rand = getStdRandom (randomR (0, maxBound))

(The randomR function takes an inclusive range within which the generated random value should lie.)

The System.Random module provides a typeclass, RandomGen, that lets us define new sources of random Int values. The type StdGen is the standard RandomGen instance. It generates pseudorandom values. If we had an external source of truly random data, we could make it an instance of RandomGen and get truly random, instead of merely pseudorandom, values.

Another typeclass, Random, indicates how to generate random values of a particular type. The module defines Random instances for all of the usual simple types.

Incidentally, the definition of rand above reads and modifies a built-in global random generator that inhabits the IO monad.

After all of our emphasis so far on avoiding the IO monad wherever possible, it would be a shame if we were dragged back into it just to generate some random values. Indeed, System.Random contains pure random number generation functions.

The traditional downside of purity is that we have to get or create a random number generator, then ship it from the point we created it to the place where it's needed. When we finally call it, it returns a new random number generator: we're in pure code, remember, so we can't modify the state of the existing generator.

If we forget about immutability and reuse the same generator within a function, we get back exactly the same “random” number every time.

-- file: ch14/Random.hs
twoBadRandoms :: RandomGen g => g -> (Int, Int)
twoBadRandoms gen = (fst $ random gen, fst $ random gen)

Needless to say, this has unpleasant consequences.

ghci> twoBadRandoms `fmap` getStdGen
Loading package old-locale-1.0.0.0 ... linking ... done.
Loading package old-time-1.0.0.0 ... linking ... done.
Loading package random-1.0.0.0 ... linking ... done.
Loading package mtl-1.1.0.0 ... linking ... done.
(945769311181683171,945769311181683171)

The random function uses an implicit range instead of the user-supplied range used by randomR. The getStdGen function retrieves the current value of the global standard number generator from the IO monad.

Unfortunately, correctly passing around and using successive versions of the generator does not make for palatable reading. Here's a simple example.

-- file: ch14/Random.hs
twoGoodRandoms :: RandomGen g => g -> ((Int, Int), g)
twoGoodRandoms gen = let (a, gen') = random gen
                         (b, gen'') = random gen'
                     in ((a, b), gen'')

Now that we know about the state monad, though, it looks like a fine candidate to hide the generator. The state monad lets us manage our mutable state tidily, while guaranteeing that our code will be free of other unexpected side effects, such as modifying files or making network connections. This makes it easier to reason about the behavior of our code.

Here's a state monad that carries around a StdGen as its piece of state.

-- file: ch14/Random.hs
type RandomState a = State StdGen a

The type synonym is of course not necessary, but it's handy. It saves a little keyboarding, and if we wanted to swap another random generator for StdGen, it would reduce the number of type signatures we'd need to change.

Generating a random value is now a matter of fetching the current generator, using it, then modifying the state to replace it with the new generator.

-- file: ch14/Random.hs
getRandom :: Random a => RandomState a
getRandom =
  get >>= \gen ->
  let (val, gen') = random gen in
  put gen' >>
  return val

We can now use some of the monadic machinery that we saw earlier to write a much more concise function for giving us a pair of random numbers.

-- file: ch14/Random.hs
getTwoRandoms :: Random a => RandomState (a, a)
getTwoRandoms = liftM2 (,) getRandom getRandom

As we've already mentioned, each monad has its own specialised evaluation functions. In the case of the state monad, we have several to choose from.

The evalState and execState functions are simply compositions of fst and snd with runState, respectively. Thus, of the three, runState is the one most worth remembering.

Here's a complete example of how to implement our getTwoRandoms function.

-- file: ch14/Random.hs
runTwoRandoms :: IO (Int, Int)
runTwoRandoms = do
  oldState <- getStdGen
  let (result, newState) = runState getTwoRandoms oldState
  setStdGen newState
  return result

The call to runState follows a standard pattern: we pass it a function in the state monad and an initial state. It returns the result of the function and the final state.

The code surrounding the call to runState merely obtains the current global StdGen value, then replaces it afterwards so that subsequent calls to runTwoRandoms or other random generation functions will pick up the updated state.

It's a little hard to imagine writing much interesting code in which there's only a single state value to pass around. When we want to track multiple pieces of state at once, the usual trick is to maintain them in a data type. Here's an example: keeping track of the number of random numbers we are handing out.

-- file: ch14/Random.hs
data CountedRandom = CountedRandom {
      crGen :: StdGen
    , crCount :: Int
    }

type CRState = State CountedRandom

getCountedRandom :: Random a => CRState a
getCountedRandom = do
  st <- get
  let (val, gen') = random (crGen st)
  put CountedRandom { crGen = gen', crCount = crCount st + 1 }
  return val

This example happens to consume both elements of the state, and construct a completely new state, every time we call into it. More frequently, we're likely to read or modify only part of a state. This function gets the number of random values generated so far.

-- file: ch14/Random.hs
getCount :: CRState Int
getCount = crCount `liftM` get

This example illustrates why we used record syntax to define our CountedRandom state. It gives us accessor functions that we can glue together with get to read specific pieces of the state.

If we want to partially update a state, the code doesn't come out quite so appealingly.

-- file: ch14/Random.hs
putCount :: Int -> CRState ()
putCount a = do
  st <- get
  put st { crCount = a }

Here, instead of a function, we're using record update syntax. The expression st { crCount = a } creates a new value that's an identical copy of st, except in its crCount field, which is given the value a. Because this is a syntactic hack, we don't get the same kind of flexibility as with a function. Record syntax may not exhibit Haskell's usual elegance, but it at least gets the job done.

There exists a function named modify that combines the get and put steps. It takes as argument a state transformation function, but it's hardly more satisfactory: we still can't escape from the clumsiness of record update syntax.

-- file: ch14/Random.hs
putCountModify :: Int -> CRState ()
putCountModify a = modify $ \st -> st { crCount = a }

Now that we know about the relationship between functors and monads, If we look back at the list monad, we can see something interesting. Specifically, take a look at the definition of (>>=) for lists.

-- file: ch14/ListMonad.hs
instance Monad [] where
    return x = [x]
    xs >>= f = concat (map f xs)

Recall that f has type a -> [a]. When we call map f xs, we get back a value of type [[a]], which we have to “flatten” using concat.

Consider what we could do if Monad was a subclass of Functor. Since fmap for lists is defined to be map, we could replace map with fmap in the definition of (>>=). This is not very interesting by itself, but suppose we could go further.

The concat function is of type [[a]] -> [a]: as we mentioned, it flattens the nesting of lists. We could generalise this type signature from lists to monads, giving us the “remove a level of nesting” type m (m a) -> m a. The function that has this type is conventionally named join.

If we had definitions of join and fmap, we wouldn't need to write a definition of (>>=) for every monad, because it would be completely generic. Here's what an alternative definition of the Monad typeclass might look like, along with a definition of (>>=).

-- file: ch14/AltMonad.hs
import Prelude hiding ((>>=), return)

class Functor m => AltMonad m where
    join :: m (m a) -> m a
    return :: a -> m a

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

Neither definition of a monad is “better”, since if we have join we can write (>>=), and vice versa, but the different perspectives can be refreshing.

Removing a layer of monadic wrapping can, in fact, be useful in realistic circumstances. We can find a generic definition of join in the Control.Monad module.

-- file: ch14/MonadJoin.hs
join :: Monad m => m (m a) -> m a
join x = x >>= id

Here are some examples of what it does.

ghci> join (Just (Just 1))
Just 1
ghci> join Nothing
Nothing
ghci> join [[1],[2,3]]
[1,2,3]