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

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