Haskell Parser sequencing not working

Question

I've been learning Haskell recently. I tried the code below in the book. But it does not work as expected.

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

the books says that:

>parse p "abcdef"
[ ((’a’, ’c’), "def") ]

But when I tried it, it was like:

*Main> pp "abcde"
[(([('a',"bcde")],[('a',"bcde")]),"abcde")]

---

The sequencing operator (+>>=) works but not the do notation. Why?

Here is the complete code. GHCi 8.2.2

{-# OPTIONS_GHC -fno-warn-tabs #-}
type Parser a = String -> [(a, String)]

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


parse :: Parser a -> String -> [ (a, String) ]
parse p inp = p inp


return' :: a -> Parser a
return' v = \inp -> [(v,inp)]


(+>>=) :: Parser a -> (a -> Parser b) -> Parser b
p +>>= f = \inp -> case parse p inp of
                    [] -> []
                    [(v, out)] -> parse (f v) out


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


pp = do  x <- item
         item
         y <- item
         return' (x,y)  --return (x,y) this won't work either

---

The output:

*Main> p "abcde"
[(('a','c'),"de")]
*Main> pp "abcde"
[(([('a',"bcde")],[('a',"bcde")]),"abcde")]

Where did I go wrong? How do I write function p with do notation?

Answer 1

To the compiler, your Parser type looks like this (not actual Haskell syntax):

type Parser a = ((->) String) α
 where α = [(a, String)]

So when you use >>= (which is under the hood invoked by the do syntax) with actions of this type, it takes on the signature

(>>=) :: ______m______ α -> (α -> ______m______ β) -> ______m______ β
(>>=) :: ((->) String) α -> (α -> ((->) String) β) -> ((->) String) β

i.e.

(>>=) :: Parser a -> ([(a,String)] -> Parser b) -> Parser b

which is not the same signature as (+>>=) – what you actually want is simply

(>>=)  :: __m___ a -> (a -> __m___ b) -> __m___ b
(+>>=) :: Parser a -> (a -> Parser b) -> Parser b

IOW, with >>= you don't actually use Parser as a monad, rather, Parser redirects you to another monad (the function aka Reader monad).

To actually get Parser to behave as a monad itself, with +>>='s semantics, you must make the compiler recognise it as an actual undecomposable entity. That means, you need newtype instead of type:

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

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


parse :: Parser a -> String -> [ (a, String) ]
parse (Parser p) inp = p inp


return' :: a -> Parser a
return' v = Parser $ \inp -> [(v,inp)]


(+>>=) :: Parser a -> (a -> Parser b) -> Parser b
Parser p +>>= f = Parser $ \inp -> case parse p inp of
                    [] -> []
                    [(v, out)] -> parse (f v) out


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


pp = do  x <- item
         item
         y <- item
         return' (x,y)

Here, pp will now give a clear compile error Could not deduce Monad Parser from a use of do notation.... That shows the compiler is actually trying to do the right thing, but for it to actually work you still need to write out the instance declaration. It's easy since the operators are already there:

instance Functor Parser where
  fmap = liftM  -- makes use of the `Monad` instance below
instance Applicative Parser where
  pure = return'
  (<*>) = ap
instance Monad Parser where
  return = return'
  (>>=) = (+>>=)

That's a bit of a backwards definition though – you're using the strongest and most special interface (monad) for defining the more fundamental operation of the functor type classes. The preferred instantiation path is top-down:

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

instance Applicative Parser where
  pure v = Parser $ \inp -> [(v,inp)]
  Parser pf <*> Parser px = Parser $
     \inp -> case pf inp of
        [] -> []
        [(f,out)] -> f <$> px out

instance Monad Parser where
  return = pure
  Parser p >>= f = ...