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…

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

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