Haskell: write yourself a Monad in almost no time

Having read a couple of messages about the difficulty to learn about Monads on the Haskell Beginners mailing list, I thought I’d give it a try and explain my experience. It might help someone with his/her learning experience.

A word of caution: being a beginner in Haskell myself I do not claim to have the widest of horizons talking about Monads, in fact it’s still rather limited. But I do have a very fresh memory of where the difficulties were for me. Might be a plus. But well, let’s just get started…

Heavily inspired by “Graham Hutton: Programming in Haskell” and “Bryan O’Sullivan, John Goerzen & Don Stewart: Real World Haskell” this will be about a Parser.

The type definitions:
type ParseState = String
newtype Parser a = P (ParseState -> (Maybe a, ParseState))

That is: a ParseState is just a String (the remaining input to parse). A Parser is a function from a ParseState to a pair of Maybe a (the result) and another ParseState (the input left to parse).

It is now easy to write a function parse that drives parsing:

parse :: Parser a -> ParseState -> (Maybe a, ParseState)
parse (P p) ps = p ps

parse takes a Parser and a ParseState and returns a pair of Maybe a (the result) and another ParseState (the input left to parse). Exactly as we wanted – see above.

Ok, now let’s write three simple parsers. One to handle failures, one to yield a constant result and one that simply returns the first character of the parse state as result.

-- fail a little more gracefully then just calling 'error'
failure s = P (\inp -> (Nothing, ""))

-- return parameter as parse result without touching the parser's input
inject :: a -> Parser a
inject s = P (\inp ->(Just s, inp))

-- just return first item of parse input
item :: Parser Char
item = P (\inp -> case inp of
   [] -> (Nothing, [])
   (s:ss) -> (Just s, ss))

So far we can do simple parsing, like for examle for the first item:
parse item "123"

In order to build more interesting parsers from these simple building blocks, however, we need the possibility to combine parsers. Two useful combinations are sequential composition (chaining parsers) and alternative parsing (use either parser1 or – if that fails – parser2).
Let’s write two functions that allow just that:

-- combine two parsers into a sequential one
-- Note that the second argument is a function, *not* a parser, that is
-- supposed to return a parser which can/should consider it's argument
-- (the result of the first parse).
chain :: Parser a -> (a -> Parser b) -> Parser b
chain pa f = P resultParser
where
resultParser input = case parse pa input of
   (Nothing, x) -> (Nothing, input)
   (Just a, x) -> parse (f a) x


-- choice: parse input with 'p1' and return result or, if the parse failed then
-- parse with 'p2' and return result no matter what
por :: Parser a -> Parser a -> Parser a
por p1 p2 = P (\inp -> case parse p1 inp of
   (Nothing, x) -> parse p2 inp
   x -> x)

While this gives us already everything we need to build rather sophisticated parsers, we still need to understand how to best make use of these building blocks.

So let’s continue here…

About these ads
This entry was posted in Uncategorized. Bookmark the permalink.

2 Responses to Haskell: write yourself a Monad in almost no time

  1. Pingback: Haskell: write yourself a Monad in almost no time (3) | Codingcactus's Blog

  2. Pingback: Haskell: write yourself a Monad in almost no time (2) | Codingcactus's Blog

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s