Translate from monad to applicative

Question

OK, so I know what the Applicative type class contains, and why that's useful. But I can't quite wrap my brain around how you'd use it in a non-trivial example.

Consider, for example, the following fairly simple Parsec parser:

integer :: Parser Integer
integer = do
  many1 space
  ds <- many1 digit
  return $ read ds

Now how the heck would you write that without using the Monad instance for Parser? Lots of people claim that this can be done and is a good idea, but I can't figure out how exactly.

Answer 1

I'd write

integer :: Parser Integer
integer = read <$ many1 space <*> many1 digit

There's a bunch of left associative (like application) parser-building operators <$>, <*>, <$, <*. The thing in the far left should be the pure function which assembles the result value from the component values. The thing on the right of each operator should be a parser, collectively giving the components of the grammar left-to-right. Which operator to use depends on two choices, as follows.

  the thing to the right is    signal  / noise
  _________________________            
  the thing to the left is \           
                            +-------------------
                    pure /  |   <$>       <$
                  a parser  |   <*>       <*

So, having chosen read :: String -> Integer as the pure function which is going to deliver the semantics of the parser, we can classify the leading space as "noise" and the bunch of digits as "signal", hence

 read <$ many1 space <*> many1 digit
 (..)    (.........)     (.........)
 pure    noise parser     |
 (.................)      |
     parser              signal parser
 (.................................)
                    parser

You can combine multiple possibilities with

p1 <|> ... <|> pn

and express impossibility with

empty

It's seldom necessary to name components in parsers, and the resulting code looks more like a grammar with added semantics.

Answer 2

integer :: Parser Integer
integer = read <$> (many1 space *> many1 digit)

Or

integer = const read <$> many1 space <*> many1 digit

Whether you think either of these are more readable is up to you.