How do I implement an Applicative instance for a parser without assuming Monad?

Question

I can't figure out how to implement an Applicative instance for this parser:

newtype Parser m s a = Parser { getParser :: [s] -> m ([s], a) }

without assuming Monad m. I expected to only have to assume Applicative m, since the Functor instance only has to assume Functor m. I finally ended up with:

instance Functor m => Functor (Parser m s) where
  fmap f (Parser g) = Parser (fmap (fmap f) . g)


instance Monad m => Applicative (Parser m s) where
  pure a = Parser (\xs -> pure (xs, a))

  Parser f <*> Parser x = Parser h
    where
      h xs = f xs >>= \(ys, f') -> 
        x ys >>= \(zs, x') ->
        pure (zs, f' x')

How do I do this? I tried substituting in for >>= by hand, but always wound up getting stuck trying to reduce a join -- which would also require Monad.

I also consulted Parsec, but even that wasn't much help:

instance Applicative.Applicative (ParsecT s u m) where
    pure = return
    (<*>) = ap

My reasons for asking this question are purely self-educational.

Dietrich Epp · Answer 1 · 2012-10-31T21:42:28.700

12

It's not possible. Look at the inside of your newtype:

getParser :: [s] -> m ([s], a)

Presumably, you want to pass [s] to the input of y in x <*> y. This is exactly the difference between Monad m and Applicative m:

In Monad you can use the output of one computation as the input to another.
In Applicative, you cannot.

It's possible if you do a funny trick:

Parser x <*> Parser y = Parser $
    \s -> (\(_, xv) (s', yv) -> (s', xv yv)) <$> x s <*> y s

However, this is almost certainly not the definition that you want, since it parses x and y in parallel.

Fixes

Your ParserT can be Applicative quite easily:

newtype ParserT m s a = ParserT { runParser :: [s] -> m ([s], a) }
-- or, equvalently
newtype ParserT m s a = ParserT (StateT [s] m a)

instance Monad m => Applicative (ParserT m s) where
    ...

Note that ParserT m s is not an instance of Monad as long as you don't define the Monad instance.

You can move the leftover characters outside the parser:

newtype ParserT m s a = ParserT { runParser :: [s] -> ([s], m a) }

instance Applicative m => Applicative (ParserT m s) where
    ParserT x <*> ParserT y = ParserT $ \s ->
        let (s', x') = x s
            (s'', y') = y s'
        in x' <*> y'
    ...

edited Oct 31 '12 at 21:42

answered Oct 31 '12 at 20:13

Dietrich Epp

205,541
37
345
415

So it's totally impossible to write any Applicative parser? (unless, of course, it's also a monad) That is, it's not just impossible because I picked a poor type, is it? – Matt Fenwick Oct 31 '12 at 20:40
@MattFenwick: It's totally possible to write an Applicative parser. The question of whether the parser is Applicative is different from the question of whether `m` is Applicative. Remember that `m` is not your parser, and the class of `m` might have very little to do with the class of `ParserT`. – Dietrich Epp Oct 31 '12 at 21:34
I guess I'm confused, b/c the 1st example still relies on monads, which I was trying to avoid, and the 2nd one has a different type?? – Matt Fenwick Oct 31 '12 at 22:27
@MattFenwick: You've asked for something impossible, so the "fixes" are necessarily going to change the parameters of the question until it is possible to answer. Remember: If you want to use the output of one `m a` computation as the input for another `a -> m b` computation, you *need* a Monad because that is basically the definition of Monad right there. So the fixes are to either allow `Monad m` context, or change the definition of the parser so you don't need to extract a value from a monadic computation. – Dietrich Epp Oct 31 '12 at 23:01
@MattFenwick The second one assumes all the possible parses use up exactly the same amount of tokens. The first one has to use monad to not make that assumption. DeitrichEpp is right - you need monad internally, and that doesn't make the parser monadic, just part of its implementation. The internal data's monadic but the higher-level structure is applicative. – AndrewC Nov 01 '12 at 11:32

score 3 · Accepted Answer · edited May 23 '17 at 12:09

Full marks for aiming to use Applicative as much as possible - it's much cleaner.

Headline: Your parser can stay Applicative, but your collection of possible parses need to be stored in a Monad. Internal structure: uses a monad. External structure: is applicative.

You're using m ([s],a) to represent a bunch of possible parses. When you parse the next input, you want it to depend on what's already been parsed, but you're using m because there's potentially less than or more than one possible parse; you want to do \([s],a) -> ... and work with that to make a new m ([s],a). That process is called binding and uses >>= or equivalent, so your container is definitely a Monad, no escape.

It's not all that bad using a monad for your container - it's just a container you're keeping some stuff in after all. There's a difference between using a monad internally and being a monad. Your parsers can be applicative whilst using a monad inside.

See What are the benefits of applicative parsing over monadic parsing?.

If your parsers are applicative, they're simpler, so in theory you can do some optimisation when you combine them, by keeping static information about what they do instead of keeping their implementation. For example,

string "Hello World!" <|> string "Hello Mum!"
== (++) <$> string "Hello " <*> (string "World" <|> string "Mum!")

The second version is better than the first because it does no backtracking.

If you do a lot of this, it's like when a regular expression is compiled before it's run, creating a graph (finite state automaton) and simplifying it as much as possible and eliminating a whole load of inefficient backtracking.

How do I implement an Applicative instance for a parser without assuming Monad?

2 Answers2

Fixes