The Greenhorn's Guide to becoming a Monad Cowboy

cowboy_bar

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.

Saddle up

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.

Hat

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

Saddle

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.

Pistols

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.

Skull

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 
  

Barrel1

Type Constructor

     State s
  

Type definition

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

Bind and return definitions

  
     instance Monad (State s) where 
         (>>=) (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"  
    

Spurs

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.

Barrel2

Type constructor

     []   
   

Type definition

the standard Haskell list

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] 
    

Buffalo

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) 
              (Reader x) >>= f = Reader (\e -> runReader (f (x e)) e)
    

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
     ask = Reader id
    

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
     asks sel = ask >>= return . sel
     

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
     local f c = Reader (\e -> runReader c (f e))
     

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
                        env <- ask
                        return (cnt == (length env))    
      

Hugs

     sample
     [("count",3),("1",1),("b",2)]
     runReader countcorrect sample
     True
     runReader countcorrect [("1",1),("b",1)]
     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
   

Feathers

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 
     Monad 
    

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 
     Monad 
  

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: 
     Monad 


    

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: 
     Monad 
     danoM 
    

Trailer

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!

Monads that can take another monad in such a way, that the results are combined, are called monad transformers. Any monad is of type m a , and of course the general type a can itself be monadic, say m2 b . Now a monad transformer is defined in such a way, that it works on the value of the inner monad, b , and not just the m2 b . To distinguish such a monad transformer from its simpler cousin, it's called the same, but with a T at the end. So, you have State and StateT, Reader and ReaderT, and so on. Note that this is just by convention of the library writers, you can call them anything you like. The definition of each monad transformer can be different, and not all monads have a transformer. But monad transformers are monads, so they can be defined in the usual way. We'll take StateT as an example.

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)
    

Indian Bowl

Let's breed some more monads...

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)  
  

Another monad down! Yeeehah....Hugs again..

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

An example of monadic composition.

     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

Shooting Gun

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
   

and for monads you use

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

Warm Cuddly Animal

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!

cowboy with lasso

For further reading, I recommend Brent Yorgey's article 'The Typeclassopedia' in the Monad Reader 13. The reference monad tutorial is 'All about Monads' by Jeff Newbern. Henk-Jan van Tuyl has compiled a handy 'Tour of the Haskell Monad Functions'. To study monad usage in the wild, look at Parsec and read the 'Parsec, a fast combinator parser' tutorial, by Daan Leijen. Not to forget the obvious, the new book 'Real World Haskell' by O'Sullivan, Goerzen and Stewart, covers monads extensively. But this is just a personal selection, there are many more books, articles and tutorials available.

Copyrights

The text of this tutorial was written by Hans van Thiel, and made available under the simple permissive license , as if it were on the Haskell Wiki. Thanks to everybody whose ideas I've used, especially the authors of other tutorials, from which I've learned myself.

The western graphics are from

JsMagic

and the author is much obliged!

Last updated June 25, 2009

Valid XHTML 1.0 Strict