Functional Parser example in Haskell using GHCi

Question

I am a beginner of learning Haskell. Here is the problem I've encountered when using GHCi.

p :: Parser (Char, Char)
p =  do x <- item
        item
        y <- item
        return (x,y)

item :: Parser Char
item =  P (\inp -> case inp of
                      []     -> []
                      (x:xs) -> [(x,xs)])

item is another parser where item :: Parser Char, simply item is to parse a string

When I load the file then execute

parse p "abcdef"

An execption is then shown:

*** Exception: You must implement (>>=)

Any idea for fixing such problem ?

Updated information:

The Parser is defined as follow:

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

instance Monad Parser where
   return      :: a -> Parser a
   return v    =  P (\inp -> [(v,inp)])

   (>>=)       :: Parser a -> (a -> Parser b) -> Parser b
   p >>= f     = --...

How is Parser defined? Did you define it or do you expect it to be defined by another library, and if so, which library? — ErikR
– ErikR, Commented Dec 7, 2014 at 11:45

rampion · Accepted Answer · 2014-12-08 16:09:49Z

2

In order to use do notation, your Parser must be an instance of Monad:

instance Monad Parser where
  return :: a -> Parser a
  return = -- ...
  (>>=) :: Parser a -> (a -> Parser b) -> Parser b
  p >>= f = -- ...

The compiler needs you to fill in definitions of return and >>=.

do notation is syntatic sugar that desugars to use of >>= (pronounced "bind"). For example, your code desugars to:

p :: Parser (Char, Char)
p =  item >>= \x ->
     item >>= \_ ->
     item >>= \y ->
     return (x,y)

Or, with more explicit parentheses:

p = item >>= (\x -> item >>= (\_ -> item >>= (\y -> return (x,y))))

>>= describes how to combine a Parser a along with a function a -> Parser b to create a new Parser b.

Using your definition of Parser, a working Monad instance is

instance Monad Parser where
  return a = P $ \s -> [(a,s)]
  p >>= f = P $ concatMap (\(a,s') -> runParser (f a) s') . runParser p
  -- which is equivalent to
  -- p >>= f = P $ \s -> [(b,s'') | (a,s') <- runParser p s, (b,s'') <- runParser (f a) s']

Consider what >>= does in terms of a p :: Parser a and a function f :: a -> Parser b.

when unwrapped, p takes a String, and returns a list of (a,String) pairs
```
runParser p :: String -> [(a,String)]
```

for each (a,String) pair, we can run f on the a to get a new parser q:

map go . runParser p :: String -> [(Parser b,String)]
  where go :: (a, String) -> (Parser b, String)
        go (a,s') = let q = f a in (q, s')

if we unwrap q, we get a function that takes a String and returns a list of (b, String) pairs:

map go . runParser p :: String -> [(String -> [(b,String)],String)]
  where go :: (a, String) -> (String -> [(b,String)],String)
        go (a,s') = let q = f a in (runParser q, s')

we can run that function on the String that was paired with the a to get our list of `(b, String) pairs immediately:

map go . runParser p :: String -> [[(b,String)]]
  where go :: (a, String) -> [(b,String)]
        go (a,s') = let q = f a in runParser q s'

and if we flatten the list-of-lists that results we get an String -> [(b,String)], which is just unwrapped Parser b

concat . map go . runParser p :: String -> [(b,String)]
  where go :: (a, String) -> [(b,String)]
        go (a,s') = let q = f a in runParser q s'

edited Dec 8, 2014 at 16:09

answered Dec 7, 2014 at 11:33

rampion

89.6k49 gold badges209 silver badges321 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

tony.0919 Over a year ago

Thanks, rampion. The information is updated and show the definition of Parser. So how can I implement >>= in the given example.

rampion Over a year ago

Tony Ngan: what I and user5402 were asking for was a definition of the Parser datatype, not the definition of item. I think I was able to infer it from your use of the P constructor, but tell me if I'm wrong.

tony.0919 Over a year ago

I've updated it again. newtype Parser a = P (String -> [(a,String)]) , so what does s' mean in Monad instance you have mentioned above.

rampion Over a year ago

tony.0919: I've fleshed out my description of how >>= is implemented. Let me know if you have any questions about it.

Collectives™ on Stack Overflow

Functional Parser example in Haskell using GHCi

1 Answer 1

4 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

4 Comments

Your Answer

Sign up or log in

Post as a guest

Related