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.

Answer 3

Your example can be progressively rewritten to a form which more clearly resembles an Applicative:

do
  many1 space
  ds <- many1 digit
  return $ read ds

1. definition of do notation:

   many1 space >> (many1 digit >>= \ds -> return $ read ds)
   

2. definition of $:

   many1 space >> (many1 digit >>= \ds -> return (read ds))
   

3. definition of .:

   many1 space >> (many1 digit >>= (return . read))
   

4. 3rd monad law (associativity):

   (many1 space >> many1 digit) >>= (return . read)
   

5. definition of liftM (in non-do notation):

   liftM read (many1 space >> many1 digit)
   

This is (or should be, if I haven't messed up :)) identical in behavior to your example.

Now, if you replace liftM with fmap with <$>, and >> with *>, you get the Applicative:

read <$> (many1 space *> many1 digit)

This is valid because liftM, fmap, and <$> are generally supposed to be synonyms, as are >> and *>.

This all works and we can do this because the original example didn't use the result of any parser to build a following parser.