# The Greenhorn's Guide to becoming a Monad Cowboy Howdy! You all are probably wondering why this guide, when there are so many fine monad tutorials out there already. Well, I've noticed some people on the Haskell trail (and in the saloon) still talk of them monads like they were rattlesnakes hatched from a lawyer's briefcase. That just don't feel right! Actually, programming monads is much like cattle driving! So, let's get started.

First, let's talk about prefix, infix and postfix. Suppose you want to put the argument of a unary function before the function (postfix).

```
flop :: a -> (a -> b) -> b
flop x f = f x
```

The flop function takes two arguments (binary) and any such function can be written as infix using the inverted quotes.

```     x `flop` f
```

You can write the composite of functions f, g and h (all unary and with the right types) as

```     x `flop` f `flop` g `flop` h
```

That ain't hard, but what about a function with two arguments (binary)? Well, as you know, in Haskell them kind of functions are treated like they was two unary functions (currying). So, because flop is defined for any type, you can write

```    x 'flop` y `flop` f
```

Let's try it out in Hugs or GHCi, with x and y type Double and division (/) for the binary function

```     3.0 `flop` 5.0 `flop` (/)
```

We get an error message

```     ERROR - Cannot infer instance
*** Instance   : Fractional (a -> b)
*** Expression : flop (flop 3.0 5.0) (/)
```

Turns out I should have used brackets

```    3.0 `flop` (5.0 `flop` (/))
```

This works and gets 1.66666666666667 as answer in Hugs. But it's not what we want. The double flop changes f x y into y x f. We could use the Prelude function flip on (/) to get what we really, really want, which is x y f, but we won't do that. We'll use the lambda notation to force the result, using variable symbols.

```    3.0 `flop` (\x -> 5.0 `flop` (\y -> (x/y)))
```

So, can you define a function in this manner too? Sure, for example

```     divdbl :: Double -> Double -> Double
divdbl x y = x `flop`(\u -> y `flop` (\v -> (u/v)))
```

Now, I can imagine some of you are having trouble holding on to the fence, right now, 'cause you're laughing so hard. First I've used postfix notation for a function, then I needed the variables in lambda notation to get me out of a mess, and then I ended up with what I started with!

But the reason is, we're going to use this flop, or at least something like it, in a very general way in our monads. So, bear with me, even though it gets even crazier. Them Haskell boys would rather ride out into a raging blizzard in their longjohns, than do any programming without types. So, let's get us a type

```     newtype Wrapped a = Wrap a
```

Usually the type constructor and the value constructor get the same name, but we want to show the distinction here. You wrap a value of type a to get a wrapped type a. So, the type signature of a wrapped divison of wrapped doubles would be

```     divwrp :: Wrapped Double -> Wrapped Double -> Wrapped Double
```

Now, can we use the definition of divdbl above unchanged? Let's try. No, we get an error from Hugs.

```     Instance of Fractional (Wrapped Double) required for definition of divwrp
```

Seems we can't divide wrapped doubles. We fix this problem by redefining our flop in two ways. Firstly the definition, of course, but secondly the type of our function f. To recall, we had

```     flop :: a -> (a -> b) -> b
flop x f = f x
```

Now we replace this with

```     wrflop :: Wrapped a -> (a -> Wrapped b) -> Wrapped b
wrflop (Wrap x) f =  f x
```

Note the change, especially in f. The first argument, of type a, just becomes Wrapped a, and the result, which was type b, becomes Wrapped b. But f does not go from Wrapped a to Wrapped b, as you'd perhaps expect, but from a to Wrapped b.

Our function wrflop does not only change prefix to postfix, but also passes the unwrapped value of the argument to f, even though the argument itself is wrapped.

Now, some of you're smiling and bobbing your heads and nudging one another, 'cause you've heard this before. Monads are containers, right? Right!

Let's define a division function with wrapped doubles.

```     divwrp :: Wrapped Double -> Wrapped Double -> Wrapped Double
divwrp x y = x `wrflop`(\u -> y `wrflop` (\v -> (Wrap (u/v))))
```

Note the Wrap value constructor at the end, which you need to get a Wrapped result.

Run, with Hugs or GHCi

```     divwrp (Wrap 3.0) (Wrap 5.0)
```

Hugs gives an error message

```     ERROR - Cannot find "show" function for:
*** Expression : divwrp (Wrap 3.0) (Wrap 5.0)
*** Of type    : Wrapped Double
```

All right, that's just about displaying the result. We fix this with

```     instance Show a => Show (Wrapped a) where
show (Wrap a) = "Wrapped: " ++ (show a)
```

Now the result from Hugs is

```     Wrapped: 0.6
```

Just to recall, Show is the Class of all types which can be shown, that is, for which the show function, which evaluates to a String, can be defined. The actual definition for any particular type is done in an instance definition of Show.

Here we assume that the show function has already been defined for the particular type a. So all we have to do is give a definition for types Wrapped a.

Before we ride out to get us some monads there's one other thing we'd better look at first. Usually, you don't want to show the evaluation as a wrapped or monadic type, but you'll want the unwrapped result.

The old Haskell hands have a trick for this, which is to use named fields in their data and type definitions. (Recall that a newtype definition is just like a data definition, but with no choice operator (|). A newtype has only one value constructor.)

So we'll redefine our Wrapped type

```     newtype Wrapped a = Wrap {unwrap :: a}
```

This has nothing to do with monads, but the named field is automatically implemented as an accessor function to the Wrapped type. So now, without defining the show function, you can use for the wrapped division

```     unwrap (divwrp (Wrap 3.0) (Wrap 5.0))
```

This gives the expected value 0.6 ## Round 'em up

Now, I don't blame you for fidgeting and looking at them horses suspiciously, 'cause you're starting to smell manure, right? You haven't heard one useful thing yet, is what you're thinking. Bear with me.

This Wrapped type constructor, which can Wrap any type you like, can itself be parametrized. So now you have sort of twofold polymorphism, first for your type constructor and second for your type. Now, if a type constructor is one of them monads, you can say so with

```     Class Monad m where
```

and next you specify what's at least needed for such a type constructor to be a Monad.

Recall the Show Class we had earlier. This says what is needed for a type to be a member of that class, which is just that there is a function show which takes something of that type as argument, and has a String as its value.

What the function actually is depends on the type, and you specify that in an instance definition. With Monads it's the same, but the variable m is not a type. Recall that each type in Haskell has the same kind (yep, kind of super type) denoted by * . A type constructor takes a kind and returns a kind, so its supertype is * -> * . Now Monad is just the Class of them type constructors. When is a type constructor a monad?

```     Class Monad m where
(>>=) :: m a -> (a -> m b) -> m b
```

That's it, really. Now look at the wrflop function above. Get it? The directed fish hook, which, by the way, you should call 'bind', so's not to look foolish, reverts the postfix notation and hooks the value out of the container. Thirdly, and that's the useful part, the bind can do something different for each different Monad. All this must be implemented in an instance, of course. The class just provides the type signature.

Look at the divwrp function again, and note the actual division result had to be wrapped, for type consistency. We generalize this too, and it's called return

```     return :: a -> m a
```

You'll get the idea of returning the result, which is at the end, in the right type, but keep in mind the return is not like a return in an imperative language like C, or something.

Thirdly, in our Monad class, we have

```     (>>) :: m a -> m b -> m b
(>>) (m x) (m y) = (>>=) (m x) (\_ -> m y)
```

You might also see

```     m >> k = m >>= \_ -> k
```

Don't let this throw you out of the saddle! Substitute m for (m x) and k for (m y) and look at the infix and prefix positions, and you'll see the two definitions are the same. It just means x >> y evaluates to y. Why in the heck would anyone want to use that? Well, it's when monads are used to model actions, like in input/output. Then you might want to use a second monadic expression while disregarding the result of the first. We'll get to that.

Lastly, there's a fail function, which is used sometimes, but not often.

```     fail :: String -> m a
fail s = error s
```

Though we'll ramble around this, note that apparently the well known error function returns a monadic type! Note the fail can be overridden in an instance definition. Also keep in mind the bind and return must obey certain laws, for the definition to work. For the monads in the GHC library you can assume this has been checked, of course, but if you roll your own....look at the list example we'll be talkin' about later.

All right, all right...we'll get us a monad, real soon now, though y'all will probably be disappointed. It don't do much at all, no sir! But first the do notation, forgive the pun. Bear with me. Cause you're all so impatient we'll skip the pattern matching in the do notation. The simple case is where we only have names before the arrow. Then

```     do x <- e1; e2; ...; en
```

evaluates to

```     e1 >>= \x -> do e2;...;en
```

So, it's essentially a sequence of binds. Recall the definition of (>>). Now you see how that seamlessly fits in.

You can also have a let in a do notation. It's defined as

```     do let decllist; e2;...; en
```

which evaluates to

```     let decllist in do e2;...;en
```

So you don't need the keyword in in a monadic do notation, as you're used to with the usual function definitions. It's already part of the syntactic sugar.

Now, at last, the first monad. Define the type

```     newtype Wrapped a = Wrap {unwrap :: a}
```

Define the bind and return as Monad instances

```     instance Monad Wrapped where
(>>=) (Wrap x) f =  f x
return x = Wrap x
```

Note the fishhook is just our wrflop and the return is just our Wrap value constructor. But now we can rewrite our wrapped division in monadic do notation

```     divwrp :: Wrapped Double -> Wrapped Double -> Wrapped Double
divwrp x y = do u <- x
v <- y
return (u/v)
```

Run it in Hugs

```     unwrap (divwrp (Wrap 3.0) (Wrap 5.0))
```

This gives us the usual result 0.6. Note we still need the unwrap accessor function to get the value out of the Wrapped type. ## Brand 'em

Our Wrapped monad is actually the Identity monad, as defined in the Control.Monad.Identity GHC module. It don't do much, but now we're ready for some useful monads! All you have to do is define your binds and returns (keeping the laws in mind). Many have already been defined in modules, or even the prelude.

#### Type Constructor

```     Maybe
```

#### Type Definition

```     data Maybe a = Nothing | Just a
```

#### Bind and return definitions

```     instance Monad Maybe where
(>>=) Nothing f = Nothing
(>>=) (Just x) f = f x
return x = Just x
```

#### Rationale

The Maybe data type is for functions that might not always work out, like looking for things in a list, or floating point calculations which are not accurate enough for some arguments. But what if the arguments themselves could or could not be of type Maybe?

If an argument itself is Nothing, it makes sense to define the result of the function Nothing too, right away. That's what the bind does. If the argument is Just x, the bind hooks the x out of the container and passes it to the function. The return constructs the Maybe value from a value. It can only be Just a.

#### Example

```     divsumdif:: Double -> Double -> Maybe Double
divsumdif x y | abs (x - y) <= 1.0e-4 = Nothing
| otherwise = Just ((x +y) / (x - y))

onediv :: Double -> Maybe Double
onediv x | x >= 1.0e+5 || x <= 1.0e-5 = Nothing
| otherwise = Just (1.0 / x)

composediv :: Double -> Double -> Maybe Double
composediv x y = do  u <- onediv x
v <- onediv y
divsumdif u v
```

Running Hugs

```     composediv (1.0/6.0) (1.0/4.0)
Just 5.0

composediv 1.0e6 4.0
Nothing
```

Note the Maybe type apparently already has its show function defined in the Prelude. Also note the absence of the return function in the example.

Suppose you want divsumdif, knowing there is a possible inaccuracy in the first argument, but the second one is allright.

```     oneokcompose :: Double -> Double -> Maybe Double
oneokcompose x y = do u <- onediv x
divsumdif u y
```

Hugs

```     oneokcompose (1.0/6.0) 4.0
Just 5.0

oneokcompose 1.0e6 4.0
Nothing

oneokcompose (1.0/4.0) 4.0
Nothing
``` #### Type Constructor

```     State s
```

#### Type definition

```     newtype State s a = State { runState :: (s -> (a,s)) }
```

#### Bind and return definitions

```
(>>=) (State x) f = State (\st -> let (v,ns) = x st in runState (f v) ns )
return x = State (\s -> (x,s))
```

#### Rationale

How `bout that? Bet you Java slickers ain't seen nothing like this before! No, sir! But recall monadic computation is just function composition in postfix form with some type trickery. As an aside, them tricks are supposed to keep folks from shootin' themselves in the foot. That's the reason, though it might look strange. But let's move on.

A function which uses state is just a function from a type a to a type b, but the result also depends on something else, a state. Secondly, the function can change the state. In functional programming you never change anything, but of course you can get a new state as a function result. So a stateful function itself, before even thinking of a monad, is of type

```     f :: a -> s -> (b,s)
```

It's a binary function which evaluates to a tuple. Get it? If you take the first argument only, the result is a function which takes a state and returns a tuple. It's just currying. Now you wrap this up in a State. That's your definition of the return.

Look at the newtype definition. This is also kind of binary, right? State s a, with s and a of a certain type, is a type. So (State s) is a type constructor. State is also a type constructor, which evaluate to a type constructor. It's just currying with types. But your monad m a is now monad State s a so you need State s and not State in your instance definition.

The bind function, the fish hook. What does it do? Well, it converts (m x) f to f (m x) and gives the x to f. That's the same for all monads. Looking again at the type signature for bind in the Monad Class definition, we see the that x >>= f, for this instance, evaluates to type

```     State (\s -> (a,s))
```

In this case x is a function, which takes an s and gives a tuple (a,s), so that's what we use in the definition

```     State (\st -> let (v, ns) = x st in ......)
```

Here v is the value of type a, ns is the new state of type s.

These two are the arguments of our binary function f. But this is of type

```     a -> State ( s -> (b,s))
```

So you have f v, where value v is of type a. But now, to apply this to argument ns, you must first use the accessor function runState. So you get

```     (>>=) (State x) f = State (\st -> let (v,ns) = x st in runState (f v) ns )
```

#### Example

Define a function which turns a character into upper or lower case, depending on a state of true or false. You need module Data.Char for this.

```     chncase :: Char -> Bool -> (Char, Bool)
chncase x s | s == True = ((toLower x), False)
| otherwise = ((toUpper x), True)
```

With Hugs

```
chncase 'a' True
('a',False)
chncase 'a' False
('A',True)
chncase 'A' True
('a',False)
chncase 'A' False
('A',True)

chncase 'A'
ERROR - Cannot find "show" function for:
*** Expression : chncase 'A'
*** Of type    : Bool -> (Char,Bool)
```

Note that the error just refers to the show function. Taking just one argument returns a perfectly valid Haskell type.

Redefine the function as a State monad.

```     chncasewst :: Char -> State Bool Char
chncasewst x = State (\st -> chncase x st)
```

Note we've done nothing, except redefine the function with one argument only, and put the State value constructor in front for type correctness. But now we can use our monad definition of bind and return to compose the function.

```     chncasewst3 :: Char -> Char -> Char -> State Bool String
chncasewst3 x y z = do u <- chncasewst x
v <- chncasewst y
w <- chncasewst z
return [u,v,w]
```

Look at the type declaration. It's a function, which takes a Char, evaluates to a function which takes a Char, evaluates to a function which takes a Char, evalutes to a State Bool String. This, however, is a function which takes a Bool and evaluates a Char, Bool tuple. Just for fun, let's rewrite chncasewst3 with the fish hooks.

```     chncasewst3 :: Char -> Char -> Char -> State Bool String
chncasewst3 x y z = (chncasewst x) >>= (\u ->
(chncasewst y) >>= (\v ->
(chncasewst z) >>= (\w ->
return [u,v,w] )))
```

Note it's just postfix composition, with the fish hook doing the work. To actually get some result from this all, keep in mind it's of type State Bool String. So, as always, you'll have to use the accessor function. If you have not used a named field for your newtype definition, you'll have to write something yourself. In this case the content of the result is itself a function, which takes a Bool argument.

So, with Hugs or GHCi

```     runState (chncasewst3 'e' 'd' 'f') False
("EdF",True)
runState (chncasewst3 'E' 'D' 'F') False
("EdF",True)
runState (chncasewst3 'E' 'D' 'F') True
("eDf",False)
```

Of course, to clean it up, you could write

```     altcase3 :: Char -> Char -> Char -> Bool -> String
altcase3 x y z tof = charstr where
(charstr, _) = runState (chncasewst3 x y z) tof
```

With Hugs

```     altcase3 'd' 'e' 'f' True
"dEf"
altcase3 'd' 'e' 'f' False
"DeF"
``` Now, in this example all the arguments were of the same type. Course it don't have to be that way, so long as you use the correct types in your composition. But if they are of the same type, like here, you can map them monadic functions to a list, like any other function. Then there's a special function in the Prelude, called 'sequence', which will insert all the binds for you. In fact, this is so common, there's a function mapM which does both.

Have another look at

```     chncasewst :: Char -> State Bool Char
chncasewst x = State (\st -> chncase x st)
```

Checking the type of mapM with Hugs

```     :t mapM
mapM :: Monad a => (b -> a c) -> [b] -> a [c]
```

So let's define

```     altcasestring :: String -> State Bool String
altcasestring str = mapM chncasewst str
```

With Hugs

```     runState (altcasestring "abcdefg") True
("aBcDeFg",False)
runState (altcasestring "abcdefg") False
("AbCdEfG",True)
```

As before, you'd probably put the runState inside yet another function which will take a String and a Boolean and evaluate to a String

```     altstring2string :: String -> Bool -> String
altstring2string str tof = altstr where
(altstr, _) = runState (altcasestring str) tof
```

Hugs

```     altstring2string "ABCDEFG" True
"aBcDeFg"
altstring2string "ABCDEFG" False
"AbCdEfG"
```

There's lots more functions and tricks, so you monad cowboys just better look for 'em and start practicing! Yes, Sir! Meanwhile, here's another monad for you. #### Type constructor

```     []
```

#### Bind and return definitions

```     instance Monad [] where
(>>=) [x] f = concatMap f [x]
return x = [x]
```

#### Rationale

If you're still thinking of monads as special things, now 's the time to change your ways. The return function takes something of a type a to a list of type a. The function f takes something of type a to a list of type b. This is all in the general Monad Class declaration. The bind here is the standard concatMap function on lists, but in postfix notation.

#### Example

The instance definition is already in the Prelude, so you can use monadic notation straight away.

```     cross :: [a] -> [b] -> [(a,b)]
cross ls1 ls2 = do x <- ls1
y <- ls2
return (x,y)
```

Well, this does demonstrate a disadvantage of using the same symbols for all those different monads (overloading). You must keep track of what your code means when it all looks the same.

Hugs

```     cross "AB" [1,2,3]
[('A',1),('A',2),('A',3),('B',1),('B',2),('B',3)]
```

So the cross function evaluates to the Cartesian product. Another way to do this would be with list comprehension

```     cross :: [a] -> [b] -> [(a,b)]
cross ls1 ls2 = [ (x,y) | x <- ls1, y <- ls2 ]
```

Hugs

```     cross "AB" [1,2,3]
[('A',1),('A',2),('A',3),('B',1),('B',2),('B',3)]
```

Don't let the similarities in the two definitions confuse you. The use of the arrows is just another case of symbol overloading in the Haskell programming language. List comprehension is not monadic.

Let's use the list monad to examine the monad laws mentioned earlier. Each instance of the monad class has to comply with

```     (m x) >>= f >>= g = (m x) >>= (\y -> f y >>= g)
(>>=) (return x) f = f x
(>>=) (m x) return = m x
```

What does this mean? Define two functions (you need module Data.Char for this)

```     f :: Char -> [Int]
f x = [ord x, ord x]

g:: Int -> [Char]
g y = [chr y, chr y]
```

These are of the right monadic type. Monadic composition with the bind

```     gf1 :: [Char] -> [Char]
gf1 ls = ls >>= f >>= g
```

In do notation

```     gf1 :: [Char] -> [Char]
gf1 ls = do x <- ls
y <- f x
g y
```

Both versions clearly show the composition, but for the do notation you use self named variables. Hugs gives

```     gf1 "abc"
"aaaabbbbcccc"
```

The function gf1 quadruples each element in the list, but, just to demonstrate the use of different types in a monadic computation, through the intermediate ord function.

So, what does the notation

```     (\y -> f y >>= g)
```

stand for?

```     cfg :: Char -> [Char]
cfg x = (f x) >>= g

gf2 :: [Char] -> [Char]
gf2 ls = ls >>= (\y -> cfg y)
```

In do notation

```     gf2 :: [Char] -> [Char]
gf2 ls = do x <- ls
cfg x
```

Hugs

```     gf2 "abc"
"aaaabbbbcccc"
```

So, the first monadic law above states that functions like gf1 and gf2 must always evaluate to the same result. Monadic composition is associative.

The two laws with the return just say you can slap 'em on at the beginning and the end, even when they're not needed. A return is kind of an identity in monadic composition. So you can write

```     fm1 :: Char -> [Int]
fm1 x = do u <- return x
f u

fm2 :: Char -> [Int]
fm2 x = do u <- f x
return u
```

Hugs

```     fm1 'a'
[97,97]

fm2 'a'
[97,97]

f 'a'
[97,97]
``` #### Type constructor

```     Reader e
```

#### Type Definition

```     newtype Reader e a = Reader { runReader :: (e -> a) }
```

#### Bind and return definitions

```     instance Monad (Reader e) where
return x = Reader (\e -> x)
```

#### Rationale

If you're still wondering about the State monad, look at this one. It's also for a function of some type a which evaluates to a type b, but depends on a second argument. Other than with State, however, this second argument does not change when the function is evaluated. The function just reads it. That's why it's called the Reader monad, and the second argument is often referred to as environment.

#### Example

Because it's so much like state we'll use almost the same example.

```     chncase :: Char -> Bool -> Char
chncase x e | e == True = toLower x
| otherwise = toUpper x
```

Because e is not changed, we don't have to put it into the result. The next step is to convert this into a function which evaluates to a Reader Bool Char type.

```     chncasewrd :: Char -> Reader Bool Char
chncasewrd x = Reader (\e -> chncase x e)
```

Now we can define a monadic composition

```     chncasewrd3 :: Char -> Char -> Char -> Reader Bool String
chncasewrd3 x y z = do u <- chncasewrd x
v <- chncasewrd y
w <- chncasewrd z
return [u,v,w]
```

Hugs

```     runReader (chncasewrd3 'A' 'B' 'c') True
"abc"
runReader (chncasewrd3 'A' 'B' 'c') False
"ABC"
```

The rest is left as an exercise to the reader. Sorry, just horsin' around...

There are some helper functions which might come in handy.

```     ask :: Reader e e
```

runReader ask is a function which takes something of type e and returns something of type e. If that function is id, the identity function, the result will be the environment itself.

Hugs

```     runReader ask [1,2,3]
[1,2,3]
```

Often you have a function from the environment, typically some lookup function, like the standard one from the Prelude.

```     asks :: (e -> a) -> Reader e a
```

Hugs

```     runReader (asks \$ lookup 2) [(1,'a'),(2,'b'),(3,'c')]
Just 'b'
```

You might want to change the environment.

```     local :: (e -> e) -> Reader e a -> Reader e a
```

Here f e is the new environment to apply the Reader on. Actually, these three functions are defined in the GHC library as instances of a derived class, which is more general, but we don't care about that here.

Some more horsin' around now, just to show how it works. We'll use sample as the environment.

```     sample :: [(String, Int)]
sample = [("count",3), ("1",1), ("b",2)]
```

The following function uses lookup "count" to get the Int 3. The result is a Maybe, so we have to check for Nothing and get the value from Just. Note the use of fail from the monad class definition, which defaults to error. The last line of the function returns the result of the comparison of cnt and the length of the list.

```     countcorrect :: Reader [(String,Int)] Bool
countcorrect = do  maybecnt <- asks (lookup "count")
let ok (Just x) = return x
ok _ = fail "countcorrect: lookup failed"
cnt <- ok  maybecnt
return (cnt == (length env))
```

Hugs

```     sample
[("count",3),("1",1),("b",2)]
True
Program error: countcorrect: lookup failed
```

The next function illustrates the use of local. The function of type (e -> e) is the function (("c",3) :), which adds the element ("c",3) to the front of the list.

```     newcountcorrect :: Reader [(String,Int)] Bool
newcountcorrect = local (("c",3) :) countcorrect
```

Now the length of the new (local) environment list is 4, so newcountcorrect returns False.

```     runReader newcountcorrect sample
False
```

Since Reader and State are so similar, you might wonder if there are also helper functions defined for State monads. Yes, there are.

```     get :: State s s
get = State (\s -> (s,s))

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

The first one evaluates to a tuple (s,s) when given a state s. The second one is a function which can take anything, and then will have s as the second value of the tuple. The () is the unit type, which is a sort of void, or null or noop. Again, these functions can be defined as instances of special classes, but we don't care here. Of course, if you run into trouble with my definitions, just import the standard modules you want. I won't mind. No, sir. Fact is, I recommend it!

An example of the use of get and put

```     tick :: State Int Int
tick = do  n <- get
put (n+1)
return n
```

Hugs

```     runState tick 5
(5,6)
```

Cleaning up the tick

```     increment :: Int -> Int
increment n = snd \$ runState tick n
```

Hugs

```     increment 5
6
``` Well, we could go on like this for some more time, I suppose, because there's many more monads, but I figure enough is enough. Except for the IO Monad, that is.

Try Hugs

```     :t getLine
getLine :: IO String

:t putStrLn
putStrLn :: String -> IO ()

:t putStr
putStr :: String -> IO ()
```

Now, what the heck is goin' on here? Well, there's a problem with things that do more than just evaluate, in functional programming. Take putStrLn and putStr, for example. They take the same input type, but where's the output? It's out, that's where! So how do you express the difference, that is that one adds a newline and the other does not? Answer, you can't!

But using monads allows you to model actions just like they were functions. Recall the trouble we had getting the value out of the State monad? Well, with the IO monad you can't get the value. Actually IO uses a token which is passed, but this is made invisible to the user. But now you can do all input and output inside the same type, and all other functions, including the monadic ones, are protected from type errors.

```     module Main where

main :: IO ()
main = do putStrLn "Enter a string:"
str <- getLine
let nwstr = reverse str
putStrLn nwstr
```

The type of the action, inside the IO () , is the unit type. As mentioned before, it's similar to void, null, noop or whatever.

Hugs

```     main
Enter a string:
danoM
```

Rewrite with the bind operator

```     main :: IO ()
main = putStrLn "Enter a string:"
>> getLine
>>= (\str -> let newstr = reverse str
in putStrLn newstr)
```

Hugs

```     main
Enter a string:
danoM
```

Recall the default definition of the (>>) operator in the general Monad Class declaration? Here's an example of its use. The action getLine, of type IO String, does not operate on the putStrLn before, which outputs the user prompt. The getLine binds the next function, though, which is the putStrLn which outputs that argument variable. In between you have the pure functional part, which reverses the string. So, the IO monad allows for a very clear separation between input/output and the rest. Of course, normally you wouldn't use the let for this, but

```     module Main where

main:: IO ()
main = do putStrLn "Enter a string:"
str <- getLine
putStrLn (reverse str)
```

The result is the same, and you still have a clear separation of your functions and the input of arguments and the output of evaluations. And because the IO monad can have anything for its inner type, and these have to be correct, you have input/output with all the usual type checking facilities from Hugs and GHC.

You might wonder, why the main all of a sudden? No 'special reason, but how many functions are you going to have, which take no arguments and evaluate to the unit type? But you could define the same action as useraction, or anything else, if you like. More useful would be another action, or function, which gets you the string.

```     userrev :: IO String
userrev = do putStrLn "Enter a string:"
str <- getLine
return (reverse str)
```

Hugs

```     userrev :: IO String
Enter a string:

```

It runs all right, but it won't give you an answer! You can't get the string out of the IO wrapper! What you can do

```     main:: IO ()
main = userrev >>= putStrLn
```

Look at the bind. It does exactly what it's supposed to do, it changes the postfix to prefix and takes the String argument out of the IO String. Now the putStrLn can use it.

Hugs

```     main
Enter a string:
danoM
``` ## Breed 'em

Well, y'all know, that if you put a horse and a donkey together, of opposite genders, at the right place and the right time, you might get yourself a mule. Which is a good thing, because that mule will have the characteristics of both a horse and a donkey!

#### Type Constructor

```     StateT s m
```

#### Type Definition

```     newtype StateT s m a = StateT { runStateT :: (s -> m (a,s)) }
```

#### Bind and return definitions

```     instance (Monad m) => Monad (StateT s m) where
return a = StateT (\s -> return (a,s))
(StateT x) >>= f = StateT ( \s -> do (v,ns) <- x s
(StateT nx) <- return (f v)
nx ns )
```

#### Rationale

The type constructor is like the one for State, but with one extra parameter. Note that the type definition places the tuple inside the inner monad, not the first element of that tuple. In general each different monad transformer uses its own type definition. There is no general structure or design pattern for monad transformers.

The bind and return definitions of StateT use the bind and return of the inner monad, here with the do notation. The return is just like the one for State, but it takes the return of monad m as its parameter. The bind should be read the same way. Again x is a function, running it will evaluate to m (v,ns), therefore (v,ns) is the parameter in the lambda notation. The function takes the value v, the return makes it a monad, and value constructor StateT takes it to the right type. Now the function nx takes parameter ns. Yes sir! Sure looks like a monad rodeo trick to me, but greenhorns can use it easily. I'll show ya.

#### Example

We'll use the same basic function as with State, but now we'll check if the character is a letter. We use Maybe, which is a monad. The function was

```     chncase :: Char -> Bool -> (Char, Bool)
chncase x s | s == True = ((toLower x), False)
| otherwise = ((toUpper x), True)
```

The new version is

```     mbcase :: Char -> Bool -> Maybe (Char, Bool)
mbcase x s | isAlpha x = Just (chncase x s)
| otherwise = Nothing
```

Adapt this for use in StateT

```     mbcasewst :: Char -> StateT Bool Maybe Char
mbcasewst x = StateT (\st -> mbcase x st)
```

Now we can use monadic function composition

```     mbcasewst3 :: Char -> Char -> Char -> StateT Bool Maybe String
mbcasewst3 x y z = do u <- mbcasewst x
v <- mbcasewst y
w <- mbcasewst z
return [u,v,w]
```

Hugs

```     runStateT (mbcasewst3 'a' 'b' 'c') True
Just ("aBc",False)
runStateT (mbcasewst3 'a' 'b' 'c') False
Just ("AbC",True)
runStateT (mbcasewst3 '1' 'b' 'c') True
Nothing
runStateT (mbcasewst3 'a' 'b' '3') True
Nothing
runStateT (mbcasewst3 '1' 'b' '3') True
Nothing
```

You can use mbcasewst on a list and define everything like an ordinary function

```     mbaltstr :: String -> Bool -> Maybe String
mbaltstr str tof =  case (runStateT (mapM mbcasewst str) tof) of
Nothing -> Nothing
Just (rstr,_) -> Just rstr
```

Hugs

```     mbaltstr "abcdefg" True
Just "aBcDeFg"
mbaltstr "abcdefg" False
Just "AbCdEfG"
mbaltstr "abc4efg" True
Nothing
```

StateT also has helper functions put and get

```     get :: (Monad m) => StateT s m s
get = StateT (\s -> return (s,s))

put :: (Monad m) => s -> StateT s m ()
put s = StateT (\_ -> return ((),s))
```

They're very similar to the ones for State. So similar, in fact, their signatures are declared in a MonadState class in the standard library, with the actual definitions as instances of that same MonadState class. Other monads, like Reader and ReaderT, also use an intermediate class. These definitions, however, depend on non Haskell 98 features, and are somewhat complicated by themselves, so I've just skipped that part here. But be aware, when you're using the standard library documentation, that they've done it that way.

There's a generalized function to let you use a monad in a monad transformer

```     class MonadTrans t where
lift :: (Monad m) => m a -> t m a
```

Its definition for StateT is

```     instance MonadTrans (StateT s) where
lift c = StateT ( \s -> c >>= (\x -> return (x,s)))
```

Note that it just puts the state it's given into the StateT value (this makes sense, when you think about it). But lift is widely used with monad transformers, and even with StateT it can have its use. Suppose you have

```     mbexcl :: Char -> Maybe Char
mbexcl x | x == '!' || x == '?' = Just x
| otherwise = Nothing
```

Now, using lift, you can use this in our example

```     mbcasewst4 :: Char -> Char -> Char -> Char -> StateT Bool Maybe String
mbcasewst4 x y z ec = do u <- mbcasewst x
v <- mbcasewst y
w <- mbcasewst z
p <- lift (mbexcl ec)
return [u,v,w,p]
```

Hugs

```     runStateT (mbcasewst4 'a' 'b' 'c' '?') True
Just ("aBc?",False)
runStateT (mbcasewst4 'a' 'b' 'c' '4') True
Nothing
runStateT (mbcasewst4 'a' 'b' 'c' 'd') True
Nothing
```

You can also use monad transformers with IO. This is special, because you can't get a result out of an IO monad. There is no runIO accessor function. Recall this is done on purpose, to keep input/output apart from the functions. For the same reason there's no IOT monad transformer. To use standard IO with a transformer monad you use liftIO, which is, for each case, an instance of the MonadIO class.

```     class (Monad m) => MonadIO m where
liftIO :: IO a -> m a
```

If you import Control.Monad.Trans you don't even have to bother with the actual definition. Note, however, that to use the transformer library with Hugs you need to use the -98 option. There's another house keeping note. In the following example it would be natural to use getChar, but then you need to specify unbuffered IO, because else the input will be cluttered with newlines. We avoid this by using getLine, and taking the head for the input character. Finally, if you want the actual instance definition, you'll have to dig into the GHC source code. The documentation appears to be broken here. Now, using chncase as defined above, we define

```     iocase :: Bool -> IO (Char, Bool)
iocase s = getLine >>= (\str -> return (chncase (head str) s))

iocasewst :: StateT Bool IO Char
iocasewst = StateT (\s -> iocase s)
```

This is almost exactly like the example with Maybe. Monadic composition with some user prompts

```     iocasewst3 :: StateT Bool IO String
iocasewst3 = do  liftIO \$ putStrLn "Three Characters"
liftIO \$ putStrLn "First.."
u <- iocasewst
liftIO \$ putStrLn "Second.."
v <- iocasewst
liftIO \$ putStrLn "Third.."
w <- iocasewst
return [u,v,w]
```

Note the use of liftIO for putStrLn with its argument. If you experiment with this in Hugs or GHCi, using runStateT with argument True or False, you'll have a problem. You can't get the result out of the IO. To actually see the result you need something like

```     display :: StateT Bool IO String -> Bool -> IO ()
display x s =  do u <- (runStateT x) s
print u
```

or the shorter equivalent

```     display x s = ((runStateT x) s) >>= print
```

Now a Hugs session could be

```     display iocasewst3 True
Three Characters
First..
a
Second..
b
Third..
c
("aBc",False)
``` #### Type Constructor

```     WriterT w m
```

#### Type Definition

```     newtype WriterT w m a = WriterT {runWriterT :: m (a,w) }
```

#### Bind and return definitions

```    instance (Monoid w, Monad m) => Monad (WriterT w m) where
return a = WriterT \$ return (a, mempty)
m >>= f  = WriterT \$ do
(a, w)  <- runWriterT m
(b, nw) <- runWriterT (f a)
return (b, w `mappend` nw)
```

#### Rationale

The WriterT transformer, and the Writer monad, which we've skipped, but will use later, are mostly used to add a small log message to a function result. In a monadic composition these messages are then automatically appended.

The type of a log message is usually String , mempty is [] , and infix mappend is string concatenation. Likewise for any other list. But a monoid, implemented in Data.Monoid, is more general. A monoid consists of an associative binary operator, and a neutral element. List concatenation is a monoid, but so is addition over types in Num (with 0 as the neutral) and multiplication over types in Num (with 1 as the neutral). So, you can do more with Writer and WriterT than append log messages. Just so you know.

#### Example

We'll start with this (like before), to change the case of letters. Then we'll use WriterT as the outer monad transformer, and State as the inner monad.

```     chncase :: Char -> Bool -> (Char, Bool)
chncase x s | s == True = ((toLower x), False)
| otherwise = ((toUpper x), True)
```

To add a log message, we must use

```     logchncase :: Char -> Bool -> ((Char, String), Bool)
logchncase x s | s == True = (((toLower x), "Low "), False)
| otherwise = (((toUpper x), "Up "), True)
```

This adds a log message. Why change the types like this? Look at the bind and return definitions for WriterT. If we use a State monad, then the return of an a is a function s -> (a,s) (skipping the State value constructor). But the WriterT definition says that the return of this transformer monad is the return of the inner monad, applied to the tuple (a, mempty). We will use String for the log message, so we need a tuple (Char, String) to be able to construct the two monads from the non monadic base function. First the State monad.

```     statecase :: Char -> State Bool (Char,String)
statecase x = State (\s -> logchncase x s)
```

Nothing new here. And now the WriterT monad transformer

```     logstatecase :: Char -> WriterT String (State Bool) Char
logstatecase x = WriterT (statecase x)
```

Yeeehah....Hugs

```     runState (runWriterT (logstatecase 'a')) True
(('a',"Low "),False)
runState (runWriterT (logstatecase 'a')) False
(('A',"Up "),True)
```

Watch the order of runWriterT and runState. Recall the notion of monads as packages or containers? You pack from inner to outer, you unpack from outer to inner. Of course, the purpose of all this processing of the base function is to enable monadic composition. For example

```     logstatecase3 :: Char -> Char -> Char -> WriterT String (State Bool) String
logstatecase3 x y z =  do  u <- logstatecase x
v <- logstatecase y
w <- logstatecase z
return [u,v,w]
```

Using the accessor functions runWriterT and runState as before, we now see that not only the State bind is applied, but also the WriterT bind.

```     runState (runWriterT (logstatecase3 'a' 'b' 'c')) True
(("aBc","Low Up Low "),False)
runState (runWriterT (logstatecase3 'a' 'b' 'c')) False
(("AbC","Up Low Up "),True)
```

The second example is similar, but now we use the StateT transformer, defined above, and the Writer monad. The definitions for the Writer monad are

```     newtype Writer w a = Writer {runWriter :: (a,w)}

instance (Monoid w) => Monad (Writer w) where
return a = Writer (a, mempty)
m >>= f  = Writer \$ let
(a, w)  = runWriter m
(b, nw) = runWriter (f a)
in (b, w `mappend` nw)
```

With StateT and Writer the base function must be different from the one with WriterT and State. The definition of the StateT return, of a value a, uses the return of tuple (a,s). But this inner return is, for the Writer monad, a tuple (a,w), so the combination is a combined tuple ((a,s),w). The base function is

```     altlogchncase :: Char -> Bool -> ((Char,Bool),String)
altlogchncase x s | s == True = (((toLower x), False),"Low " )
| otherwise = (((toUpper x), True), "Up ")
```

We must construct the Writer on the result of the function

```     logcase :: Char -> Bool -> Writer String (Char,Bool)
logcase = (\ x s -> Writer (altlogchncase x s))
```

This must be changed to a StateT type

```     statelogcase :: Char -> StateT Bool (Writer String) Char
statelogcase x = StateT (\s -> logcase x s)
```

```     runWriter (runStateT (statelogcase 'a') True)
(('a',False),"Low ")
runWriter (runStateT (statelogcase 'a') False)
(('A',True),"Up ")
```

```     statelogcase3 :: Char -> Char -> Char -> StateT Bool (Writer String) String
statelogcase3 x y z = do u <- statelogcase x
v <- statelogcase y
w <- statelogcase z
return [u,v,w]
```

Looks pretty much like the other one. Well, with monads, that's the idea, isn't it?. Hugs..

```     runWriter (runStateT (statelogcase3 'a' 'b' 'c') True)
(("aBc",False),"Low Up Low ")
runWriter (runStateT (statelogcase3 'a' 'b' 'c') False)
(("AbC",True),"Up Low Up ")
```

In this example, usage of StateT with Writer is equivalent to WriterT and State, but in general the order of application may lead to very different results. As a note, the inner monad can itself be a monad transformer, with an inner monad, so with transformers you can breed real monster monads, if you're so inclined.

## Drive 'em When monads have the same type, they can be put in a list, and in the Prelude there is a general function for that

```    sequence :: Monad a => [a b] -> a [b]
```

So, this takes a list of monads, and evaluates to a monad of a list. The definition is

```     sequence :: Monad m => [m a] -> m [a]
sequence = foldr mcons (return [])
where mcons p q = do x <- p
xs <- q
return (x:xs)
```

The usage is pretty simple. Recall the example earlier with the State monad

```     chncase :: Char -> Bool -> (Char, Bool)
chncase x s | s == True = ((toLower x), False)
| otherwise = ((toUpper x), True)

chncasewst :: Char -> State Bool Char
chncasewst x = State (\st -> chncase x st)
```

Define a list

```     stbcls :: [State Bool Char]
stbcls = map chncasewst "abcdefg"
```

Now, with sequence, you can evaluate this with no further ado...ha,ha..

```     runState (sequence stbcls) True
("aBcDeFg",False)
```

Fact is, it's so common to map monads to some list and sequence them, there's a short cut, called mapM

```     mapM :: Monad m => (a -> m b) -> [a] -> m [b]
mapM f ls  =  sequence (map f ls)
```

So, with Hugs, or GHCi, of course

```     runState (mapM chncasewst "abcdefg") True
("aBcDeFg",False)
```

Both sequence and mapM have versions with an underscore at the end.

```     sequence_ :: Monad m => [m a] -> m ()
sequence_  =  foldr (>>) (return ())

mapM_ :: Monad m => (a -> m b) -> [a] -> m ()
mapM_ f ls  =  sequence_ (map f ls)
```

So, these do not return anything, that is, they return the unit value, of the unit type. This is what you want when performing I/O. So, for example

```     mapM_ print [1..3]
1
2
3
```

These functions also work with monad transformers, of course. Recall the definitions used earlier

```     mbcase :: Char -> Bool -> Maybe (Char, Bool)
mbcase x s | isAlpha x = Just (chncase x s)
| otherwise = Nothing

mbcasewst :: Char -> StateT Bool Maybe Char
mbcasewst x = StateT (\st -> mbcase x st)
```

Note that, in the following, we must use runStateT, and not runState

```     runStateT (mapM mbcasewst "abcdefg") True
Just ("aBcDeFg",False)
runStateT (mapM mbcasewst "abc_defg") True
Nothing
```

A list is a monad too. Recall the cross function we defined to get Cartesian products of lists? If these lists have the same type, we can put them in a list and use sequence

```     sequence ["AB", ".", "12", ".", "abc" ]
["A.1.a","A.1.b","A.1.c","A.2.a","A.2.b","A.2.c","B.1.a","B.1.b","B.1.c","B.2.a","B.2.b","B.2.c"]
sequence [ [1,2], [3,4],[5,6,7]]
[[1,3,5],[1,3,6],[1,3,7],[1,4,5],[1,4,6],[1,4,7],[2,3,5],[2,3,6],[2,3,7],[2,4,5],[2,4,6],[2,4,7]]
```

Right at the beginning we talked about flopping a function first and then using it to get something out of a monad. Well, there's also a flip to this fishook or bind. Compare the following

```     cross1 ls1 ls2 =  do x <- ls1
y <- ls2
return (x,y)

cross2 ls1 ls2 = ls1 >>= (\x -> ls2 >>= (\y ->  return (x,y)))

cross3 ls1 ls2 = (\x -> (\y -> return (x,y)) =<< ls2) =<< ls1

cross4 ls1 ls2 = (=<<) (\x -> (=<<) (\y -> return (x,y))  ls2) ls1

cross5 ls1 ls2 = concatMap (\x -> concatMap (\y -> [(x,y)]) ls2) ls1
```

They are all the same, for lists that is. But look at how the flow of cross2 is more natural than the one in cross3. However, suppose you have an application, like

```     z x = h( g (f x)))
```

You would probably write this as

```     z x = h \$ g \$ f x
```

but you can't do that when the argument is a monad m x and f, g and h have type a -> m b and the like. But you can use (=<<) for this

```     z (m x) = h =<< g =<< f (m x)
```

Now, of course this suggests point free programming with monads. The above function with (\$) would become

```     z = h . g . f
```

```     (<=<) :: Monad m => (b -> m c) -> (a -> m b) -> a -> m c

z = h <=< g <=< f
```

This is called right to left Kleisli composition of monads. You'll have to admit, this sounds really nice. And, obviously, there's also a right to left Kleisli composition

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

This is more like the fish hook or bind we have all come to love. Now take a look at the monad laws again

```     return >=> f == f
f >=> return == f
(f >=> g) >=> h == f>=> (g >=> h)
```

These laws become very clear now. 'Cherchez la type', if you'll pardon my French. Before we move on, please note again the directions of the two variants. In the second one, the rightmost function is also the last one to be applied. If you take the functions as points (or objects) and (>=>) as arrows (or morphisms) you can write the composition as a triangle. Yes, that's right, it's a category, referred to as the Kleisli category by many saloon regulars. But note that composition only works within the same monad, so there are in fact many different Kleisli categories. Hmmm... what about monad transformers...I don't know, actually. But feel free to join in when you figure it out! Yes, Sir! Anyway, the flipped Kleisli variant, which we discussed first, follows conventional function composition, with the leftmost the last to be applied.

Now, for something completely different, as our Python friends would say. There are several related functions, called liftM, liftM2 etc., up to liftM5, that take functions, with the arities suggested by the names, to functions of monads of the arguments. For example

```     liftM :: (Monad m) => (a -> b) -> (m a -> m b)
liftM f x =  do a <- x
return (f a)

liftM2 :: (Monad m) => (a -> b -> c) -> (m a -> m b -> m c)
liftM2 f x y =  do a1 <- x
a2 <- y
return (f a1 a2)
```

These are not to be confused with the lift functions used for monad transformers. The liftM function is actually identical to the fmap , which is declared in the Functor class definition. Every monad is also a functor, even an applicative functor. Yep...that's right. Another monadic function is called ap.

```     ap :: (Monad m) => m (a -> b) -> m a -> m b
ap mf mx = do f <- mf
x <- mx
return (f x)
```

Now, liftM, return and ap can be used more generally than with monads. Unfortunately, these classes are not very well integrated in the Haskell language libraries, as yet. So, you use fmap for functors, (<\$>) for applicative functors, and liftM for monads, even though they're all the same. You use 'pure' for applicative functors and 'return' for monads. You also use (<*>) for applicative functors and 'ap' for monads. Of course you can define monads as instances of functors and applicative functors, or even use the WrappedMonad type constructor, which is defined in the Control.Applicative library.

Impressed? Intimidated even? No worries, mate! When you're drivin' monads out on that Haskell trail, you just fake it till you make it! So, consider the following function, which uses the monadic parser from the Text.ParserCombinators.Parsec library, shipped with GHC and Hugs. You also need to import Control.Monad and, for Hugs, use the -98 flag.

```     p_abc :: Parser String
p_abc = do as <- many (char 'a')
let n = length as
bs <- pnTimes n (char 'b')
cs <- pnTimes n (char 'c')
return (as ++ bs ++ cs)

pnTimes :: Int -> Parser a -> Parser [a]
pnTimes 0 p = return []
pnTimes n p = (:) `liftM` p `ap` pnTimes (n-1) p
```

As you can see, Parser String is a monad, and though it's hidden in the type synonym, because that feature is not used here, a general parser (in Parsec) can even take a user state. It's very easy, for example, to add the number of parsed tokens using this feature (not used here). The function 'many' is standard in Parsec and parses zero or more of something, here the character 'a'. The function p_abc recognizes strings beginning with 0 or more letters 'a', followed by as many lettrs 'b' and 'c'. Because the parser is a monad it can use the count of the 'a' letters it has seen, and compare that with what's coming next. To run a Parsec parser interactively you need parseTest, as shown below, but that's just for displaying the result.

```     parseTest p_abc "aaabbbccc"
"aaabbbccc"
parseTest p_abc "aaaaabbbbbccccc"
"aaaaabbbbbccccc"
parseTest p_abc "aaaaabbccccc"
parse error at (line 1, column 8):
unexpected "c"
expecting "b"
```

Note the usage of liftM and ap, both in infix notation. This is a very common combination, which can be extended to functions of arbitrary arity. So, you don't really need liftM2 and so on. You can also use liftM followed by the appropriate number of ap's. Well, folks, that's it. Sure, there's lots more to discuss, but I hope you'll agree, by now, that them monads ain't scary, like rattlesnakes. What the heck, I even overheard one trail boss referring to them as warm, cuddly things...well, now! But them Haskell boys have come up with many useful monads and remember, you can easily define one yourself. So long as you don't forget to check the monad laws! You can breed with monads to get new combinations. You can use all the notation and all the predefined functions. Finally, you can treat them as applicative functors too, and use some handy functions to get them in line. So, thinkin' again, maybe them monads are cute little critters after all! Yes Sir, maybe they are!  