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.

Answer 1

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.

Answer 2

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

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

2. 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'
       ...