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

matchHeader :: L.ByteString -> L.ByteString -> Maybe L.ByteString

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

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

parseP5 s =
  case matchHeader (L.pack "P5") s of
    Nothing -> Nothing
    Just s1 ->
      case getNat s1 of
        Nothing -> Nothing
        Just (width, s2) ->
          case getNat (L.dropWhile isSpace s2) of
            Nothing -> Nothing
            Just (height, s3) ->
              case getNat (L.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)

That function threatened to march off the right side of the page if it got much longer. We brought the staircasing under control using the (>>?) function.

(>>?) :: 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 Maybe. 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 functions we pass in are actually called.

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.

parseP5_take2 :: L.ByteString -> Maybe (Greymap, L.ByteString)
parseP5_take2 s =
    matchHeader (L.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, L.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.

(==>) :: Parse a -> (a -> Parse b) -> Parse b
x ==> f = Parse (\st -> case runParse x st of
                          Left err -> Left err
                          Right (a, st') -> runParse (f a) st')

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.

module Logger
    (
      Logger
    , Log
    , execLogger
    , 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.

The 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 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're using a list of strings to keep the implementation simple.

type Log = [String]

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

execLogger :: 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 that can see an unwrapped value has to wrap its own result back up again.

Most monads have one or more execLogger-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 a function 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 execLogger: 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.

record :: String -> Logger ()

Again, most monads provide helper functions that add functionality on top of the base Monad typeclass.

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.

We'll use ghci to produce a simple example of our monad in use.

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

When we run the logged action using execLogger, we get back a two-tuple. The first element is the result, and 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> execLogger (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.

globToRegex cs =
    globToRegex' cs >>= \ds ->
    return ('^':ds)

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.

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

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.

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

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.

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.

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. There is one significant difference between the two, 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.

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"

The interesting exception is in the final clause above. Where we called error in the section called “Translating a glob pattern into a regular expression”, we now call fail from the Monad typeclass instead.

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's not a constant that's 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 type classes”.

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

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 call on a result wrapped in the Just constructor; the result of that application is then returned.

Since the Maybe ADT 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.

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.

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 addressMap carrier

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 a lovely piece of API design! The behaviours of success and failure are automatically customised to our needs, based on the monad we're calling lookup from. Better yet, lookup itself doesn't know or care what those behaviours are.

The case expressions above typecheck because we're comparing the result of lookup against values of type Maybe. But the code is horrible; let's make more sensible use of Maybe's status as a monad.

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. That being said, 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.

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.

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.

comprehensive xs ys = [(x,y) | x <- xs, y <- ys]

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

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 explicit notation.

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.

blockyPlain xs ys =
    xs >>=
      \x -> ys >>=
         \y -> return (x, y)

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.

XXX I think I need a shortish, compelling example here, and I don't have any in mind. Help!

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.

semicolon = do
  {
    act1;
    val1 <- act2;
    let { val2 = expr1 };
    actN;
  }

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

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.

type SimpleState s a = s -> (a, s)

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

type StringState a = SimpleState String a

Here, we've bound the type variable s to String. The type StringState still has an unbound type variable 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.

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.

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.

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.

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.

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.

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

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.

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.

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.

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. If we'd been using the state monad directly, we would have used a ByteString as the state.

The State monad will probably feel much 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 uniform 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 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:

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 values. The type StdGen is the standard RandomGen instance, and generated 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.

twoBadRandoms :: RandomGen g => g -> (Int, Int)
twoBadRandoms gen = (fst $ random gen, fst $ random gen)

Needless to say, this has nasty 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.
(-2072741646730966803,-2072741646730966803)

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

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.

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

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.

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.

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 run our getTwoRandoms function.

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.

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.

getCount :: CRState Int
getCount = crCount `liftM` get

We deliberately used record syntax to define our CountedRandom state, and this example should make it clear why. 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.

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.

putCountModify :: Int -> CRState ()
putCountModify a = modify $ \st -> st { crCount = a }

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

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 (>>=).

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.

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]