[Haskell-beginners] Parser as an instance of the monad class

[Brent Yorgey]

On Tue, Jan 11, 2011 at 11:39:48PM -0800, Paul Higham wrote:
> I am working my way through Graham Hutton's book and find that his
> approach to introducing monads is rather nice.  Trouble is that the
> code there does not work "out of the book".  Specifically, if you
> define the Parser type as follows:
> 
>    type Parser a :: String -> [(a,String)]
> 
> you can then define the return and bind functions as
> 
>    return v  =  \x -> [(v,x)]
>    p >>= f   =  \x -> case p x of
>                         [] -> []
>                         [(v,y)] -> (f v) y
> 
> but you get name conflicts with the functions of the same names in
> the Prelude.  Fair enough.
> 
> There are a number of ugly things that you can do at this point that
> are just plain wrong, so I thought that the right thing to do would
> be to get the Parser type to be manifested as an instance of the
> Monad class.  Ok, now what?  Since Parser is only a type synonym it
> cannot be used directly in the following way:
> 
>    instance Monad Parser where
>       return v = . . .
>       p >>= f  = . . .
> 
> but since Parser is not an algebraic type as it is defined that won't
> work either.  So how do you do it?  help .

Make Parser a newtype, like so:

  newtype Parser a = Parser (String -> [(a, String)])

Now you will have some extra Parser constructors to deal with, but you
can make this an instance of Monad just fine.

-Brent