CODEWITHSUNDEEP
haskell
ICTOAUN
ICTOAUN

Reputation: 85

Why does this parser do-block fail?

I am trying to understand do-blocks/sequencing actions, parsers and monads.

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

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

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

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

I don't understand why

parse firstThird "ab"

evaluates to

[]

Why is it when one of the actions fail the whole do-block fails?

Upvotes: 2

Views: 100

Answers (1)

K. A. Buhr
K. A. Buhr

Reputation: 51129

You haven't included a Monad instance for your Parser, but a standard one might be given by:

instance Functor Parser where
  fmap = liftM
instance Applicative Parser where
  pure x = P $ \str -> [(x, str)]
  (<*>) = ap
instance Monad Parser where
  P p >>= f = P $ \str ->
    [result | (x, rest) <- p str, let P q = f x, result <- q rest]

With this instance, I can duplicate your result, and the parser is operating as intended. Usually a monadic parser is designed so that when a sequence of parsers is bound together (using the >>= operator, or as multiple steps in do-block notation), the intended meaning is that each parser is tried in sequence and must "succeed" in order for the entire sequence to be successful.

In your case, "success" is defined as a parser returning a non-empty list of possible parses. In order for firstThird to return a non-empty list, each of the three item parsers, in sequence, must produce a non-empty list. For the input string "ab", the first call to item produces the non-empty list [('a',"b")], the second call to item produces the non-empty list [('b',"")], and the third call to item has nothing left to parse and so returns the empty list []. No other parse is possible.

If you want to allow a parser to fail but continue the parse, you can use a combinator. There's a standard one named optional in Control.Applicative. To use it, you'd need an Alternative instance for your Parser:

instance Alternative Parser where
  empty = P $ \_ -> []
  P p <|> P q = P $ \str -> p str ++ q str
instance MonadPlus Parser

and then you can write:

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

which allows:

> parse firstThird "ab"
[(('a','b'),"")]
> parse firstThird "abc"
[(('a','c'),""),(('a','b'),"c")]

Note that "abc" can be parsed two ways with firstThird, with and without skipping parsing for the middle item.

This is the usual way of writing monadic parsers: the Monad is used for a sequence of parses, all of which must succeed, while the separate Alternative (AKA MonadPlus) instance and the <|> operator in particular are used to gracefully handle cases where parsers are allowed to fail and allow other parsers to be tried instead.

Upvotes: 2

Related Questions