CODEWITHSUNDEEP
haskell
tony.0919
tony.0919

Reputation: 1203

Functional Parser example in Haskell using GHCi

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     = --...

Upvotes: 1

Views: 266

Answers (1)

rampion
rampion

Reputation: 89043

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'

Upvotes: 2

Related Questions