content: 
  [[applicative-style-parsing-code]]
  = Applicative style parsing code
  
  Now we can go back over the expression parsing code written in the
  last tutorial, and make it much more concise, and also make it more
  readable. We are going to do this mainly by using functions from the
  typeclass Applicative.
  
  Remember you can (and should) use the functions `regularParse` and its
  variations (TODO list them here) to try out the all these parsers in
  ghci, and you can write your own variations to experiment with if you
  are unsure about anything.
  
  > import Text.Parsec.String (Parser)
  > import Text.Parsec.String.Char (oneOf, char, digit, letter, satisfy)
  > import Text.Parsec.String.Combinator (many1, chainl1)
  > import Control.Applicative ((<$>), (<*>), (<*), (*>), (<|>), many, (<$))
  > import Control.Monad (void, ap)
  > import Data.Char (isLetter, isDigit)
  > import FunctionsAndTypesForParsing
  
  Here is the SimpleExpr type again:
  
  > data SimpleExpr = Num Integer
  >                 | Var String
  >                 | Add SimpleExpr SimpleExpr
  >                 | Parens SimpleExpr
  >                   deriving (Eq,Show)
  
  Here is the basic pattern behind most of the rewrites we are going to
  cover. Here is a function which takes a constructor and two parsers
  for the two arguments for the constructor. It parses the two
  arguments, then applies the constructor to the results:
  
  > myParser1 :: (a -> b -> c) -> Parser a -> Parser b -> Parser c
  > myParser1 ctor pa pb = do
  >     a <- pa
  >     b <- pb
  >     return $ ctor a b
  
  TODO: concrete example, plus examples at the bottom of this section
  (for ctor <$> a, ctor <$> a <*> b, ctor <$> a <*> b <*> c).
  
  This can be rewritten without the do syntactic sugar like this:
  
  > myParser2 :: (a -> b -> c) -> Parser a -> Parser b -> Parser c
  > myParser2 ctor pa pb =
  >     pa >>= \a -> pb >>= \b -> return $ ctor a b
  
  And can also be rewritten like this:
  
  > myParser3 :: (a -> b -> c) -> Parser a -> Parser b -> Parser c
  > myParser3 ctor pa pb = ctor `fmap` pa `ap` pb
  
  (This uses functions from Applicative instead of Monad.) We replace
  the use of `>>=` with `fmap` and `ap`. This isn't always possible, but
  it often is.
  
  Here is the version using the operators for `fmap` and `ap` (`fmap`
  changed to `<$>`, and `ap` changed to `<*>`).
  
  > myParser4 :: (a -> b -> c) -> Parser a -> Parser b -> Parser c
  > myParser4 ctor pa pb = ctor <$> pa <*> pb
  
  This style takes less typing, and is often much simpler to write and
  read.
  
  This pattern 'scales', you can use:
  
  ```
  Ctor <$> pa
  ```
  
  for a single argument constructor. This might also be familiar to you
  as
  
  ```
  fmap Ctor pa
  ```
  
  or
  
  ```
  Ctor `fmap` pa
  ```
  
  All of which mean the same thing, just slightly different spellings.
  
  This can also be written using Monad operators:
  
  ```
  pa >>= liftM ctor
  ```
  
  or
  
  ```
  liftM ctor =<< pa
  ```
  
  (`liftM` is in the module `Control.Monad`)
  
  These `liftM` versions effectively mean the same thing as the previous
  versions with `fmap` and `<$>`.
  
  You can use
  
  ```
  Ctor <$> pa <*> pb <*> pc
  ```
  
  for three args, and so on. So you use `<$>` between the pure
  constructor and the first arg, then `<*>` between each subsequent arg.
  
  Let's go over the simple expression parsers and try to rewrite them
  using this style. We will see a few other new functions. I will break
  things down into a lot of steps.
  
  == lexeme
  
  Here is the old lexeme parser, 'D' suffix for 'do notation'.
  
  > lexemeD :: Parser a -> Parser a
  > lexemeD p = do
  >            x <- p
  >            whitespace
  >            return x
  
  > whitespace :: Parser ()
  > whitespace = void $ many $ oneOf " \n\t"
  
  First, we can move the `whitespace` from its own separate line.
  
  > lexemeA0 :: Parser a -> Parser a
  > lexemeA0 p = do
  >            x <- p <* whitespace
  >            return x
  
  The expression `pa <* pb` means run `pa`, then run `pb`, and return
  the result of `pa`. It is sort of equivalent to this code:
  
  ```haskell
  (<*) :: Parser a -> Parser b -> Parser a
  (<*) pa pb = do
      a <- pa
      void pb
      return a
  ```
  
  (It isn't implemented this way, since `(<*)` only needs Applicative
  and not Monad.)
  
  Now we can use the usual monad syntax rewrites, first eliminate the
  name `x`.
  
  > lexemeA1 :: Parser a -> Parser a
  > lexemeA1 p = do
  >              p <* whitespace
  
  Now remove the redundant do:
  
  > lexemeA :: Parser a -> Parser a
  > lexemeA p = p <* whitespace
  
  == num
  
  Now let's tackle the `num` parser.
  
  > numD :: Parser SimpleExpr
  > numD = do
  >     n <- lexemeD $ many1 digit
  >     return $ Num $ read n
  
  Let's move 'read' to the first line.
  
  > numA0 :: Parser SimpleExpr
  > numA0 = do
  >     n <- read <$> lexemeA (many1 digit)
  >     return $ Num n
  
  This uses `(<$>)` which we saw above. You may have done code rewrites
  like this using `fmap` with IO in other Haskell code.
  
  Now let's move the `Num` ctor as well:
  
  > numA1 :: Parser SimpleExpr
  > numA1 = do
  >     n <- (Num . read) <$> lexemeA (many1 digit)
  >     return n
  
  You can also write it in this way:
  
  > numA2 :: Parser SimpleExpr
  > numA2 = do
  >     n <- Num <$> read <$> lexemeA (many1 digit)
  >     return n
  
  Why does this work? It it equivalent to the previous version partly
  because of the applicative laws.
  
  Let's break it down:
  
  > numA2'' :: Parser SimpleExpr
  > numA2'' = do
  >     n <- numb
  >     return n
  >   where
  >     numb :: Parser SimpleExpr
  >     numb = Num <$> int
  >     int :: Parser Integer
  >     int = read <$> lexemeA (many1 digit)
  
  In terms of style, which do you think looks better:
  `(a . b) <$> p` or `a <$> b <$> p`.
  
  The next step for num, we can eliminate the temporary name `n` and the
  `do`:
  
  > numA3 :: Parser SimpleExpr
  > numA3 = (Num . read) <$> lexemeA (many1 digit)
  
  In more 'industrial' parser code, I would usually write some
  tokenization parsers separately like this:
  
  > integerA4 :: Parser Integer
  > integerA4 = read <$> lexemeA (many1 digit)
  
  Then the num expression parser looks like this:
  
  > numA4 :: Parser SimpleExpr
  > numA4 = Num <$> integerA4
  
  and we also get a integer parser which we can reuse if we need to
  parse an integer in another context.
  
  == var
  
  Here is the previous var parser:
  
  > varD :: Parser SimpleExpr
  > varD = lexemeA $ do
  >     fc <- firstChar
  >     rest <- many nonFirstChar
  >     return $ Var (fc:rest)
  >   where
  >     firstChar = satisfy (\a -> isLetter a || a == '_')
  >     nonFirstChar = satisfy (\a -> isDigit a || isLetter a || a == '_')
  
  The first thing we can do is to make the `firstChar` and
  `nonFirstChar` a little easier to read, using `(<|>)`, `char`,
  `letter` and `digit`:
  
  > varA0 :: Parser SimpleExpr
  > varA0 = lexemeA $ do
  >     fl <- firstChar
  >     rest <- many nonFirstChar
  >     return $ Var (fl:rest)
  >   where
  >     firstChar = letter <|> char '_'
  >     nonFirstChar = digit <|> firstChar
  
  Here is another way of making the function a little better:
  
  > varA0' :: Parser SimpleExpr
  > varA0' = lexemeA $ do
  >     fl <- satisfy validFirstChar
  >     rest <- many (satisfy validNonFirstChar)
  >     return $ Var (fl:rest)
  >   where
  >     validFirstChar a = isLetter a || a == '_'
  >     validNonFirstChar a = validFirstChar a || isDigit a
  
  We can lift the `(:)` using the Applicative operators.
  
  > varA1 :: Parser SimpleExpr
  > varA1 = do
  >     i <- iden
  >     return $ Var i
  >   where
  >     iden = lexemeA ((:) <$> firstChar <*> many nonFirstChar)
  >     firstChar = letter <|> char '_'
  >     nonFirstChar = digit <|> firstChar
  
  We used the prefix version of `(:)` to use it with `(<$>)` and
  `(<*>)`. The lexemeA call was moved to the `iden` helper function.
  
  Now tidy it up using `(<$>)` with the `Var` constructor:
  
  > varA2 :: Parser SimpleExpr
  > varA2 = Var <$> iden
  >   where
  >     iden = lexemeA ((:) <$> firstChar <*> many nonFirstChar)
  >     firstChar = letter <|> char '_'
  >     nonFirstChar = digit <|> firstChar
  
  We could also split the `iden` into a separate top level function,
  with the same idea as with splitting the `integer` parser.
  
  == parens
  
  Here is the starting point:
  
  > parensD :: Parser SimpleExpr
  > parensD = do
  >     void $ lexemeA $ char '('
  >     e <- simpleExprD
  >     void $ lexemeA $ char ')'
  >     return $ Parens e
  
  Here is the rewrite in one step:
  
  > parensA0 :: Parser SimpleExpr
  > parensA0 =
  >     Parens <$> (lexemeA (char '(')
  >                 *> simpleExprD
  >                 <* lexemeA (char ')'))
  
  // f'in asciidoc, the first operator following is (*>)
  
  Here you can see that there is a `(\*>)` which works in the opposite
  direction to `(<*)`. The precendence of these operators means that we
  have to use some extra parentheses (!) here.
  
  TODO: lost the chained <*. Put something below about this so there is
  a concrete example.
  
  == simple expr
  
  Here is the old version:
  
  > termD :: Parser SimpleExpr
  > termD = numD <|> varD <|> parensD
  
  > simpleExprD :: Parser SimpleExpr
  > simpleExprD = chainl1 termD op
  >   where
  >     op = do
  >          void $ lexemeA $ char '+'
  >          return Add
  
  We can simplify the `op` function using the techniques we've already
  seen:
  
  > simpleExprA0 :: Parser SimpleExpr
  > simpleExprA0 = chainl1 termD op
  >   where op = lexemeA (char '+') *> return Add
  
  The pattern `p *> return f` can use a different operator like this:
  `f <$ p`. Here it is in the expression parser:
  
  > simpleExprA1 :: Parser SimpleExpr
  > simpleExprA1 = chainl1 termD op
  >   where op = Add <$ lexemeA (char '+')
  
  You could also write the `op` parser inline:
  
  > simpleExprA2 :: Parser SimpleExpr
  > simpleExprA2 = chainl1 termD (Add <$ lexemeA (char '+'))
  
  Maybe this last step makes it less readable?
  
  == summary
  
  Here is the finished job for all the simple expression code without
  separate token parsers:
  
  > num' :: Parser SimpleExpr
  > num' = (Num . read) <$> lexemeA (many1 digit)
  
  > var' :: Parser SimpleExpr
  > var' = Var <$> iden
  >   where
  >     iden = lexemeA ((:) <$> firstChar <*> many nonFirstChar)
  >     firstChar = letter <|> char '_'
  >     nonFirstChar = digit <|> firstChar
  
  > parens' :: Parser SimpleExpr
  > parens' =
  >     Parens <$> (lexemeA (char '(')
  >                 *> simpleExpr'
  >                 <* lexemeA (char ')'))
  
  > term' :: Parser SimpleExpr
  > term' = num' <|> var' <|> parens'
  
  > simpleExpr' :: Parser SimpleExpr
  > simpleExpr' = chainl1 term' op
  >   where op = Add <$ lexemeA (char '+')
  
  Here they are with separate token parsers and a helper function:
  
  > lexeme :: Parser a -> Parser a
  > lexeme p = p <* whitespace
  
  > identifier :: Parser String
  > identifier = lexeme ((:) <$> firstChar <*> many nonFirstChar)
  >   where
  >     firstChar = letter <|> char '_'
  >     nonFirstChar = digit <|> firstChar
  
  > integer :: Parser Integer
  > integer = read <$> lexeme (many1 digit)
  
  Here is a lexeme wrapper for parsing single character symbols.
  
  > symbol :: Char -> Parser ()
  > symbol c = void $ lexeme $ char c
  
  Here is another little helper function. It barely pays its way in this
  short example, but even though it is only used once, I think it is
  worth it to make the code clearer.
  
  > betweenParens :: Parser a -> Parser a
  > betweenParens p = symbol '(' *> p <* symbol ')'
  
  Now the expression parsers:
  
  > num :: Parser SimpleExpr
  > num = Num <$> integer
  
  > var :: Parser SimpleExpr
  > var = Var <$> identifier
  
  > parens :: Parser SimpleExpr
  > parens = Parens <$> betweenParens simpleExpr
  
  > term :: Parser SimpleExpr
  > term = num <|> var <|> parens
  
  > simpleExpr :: Parser SimpleExpr
  > simpleExpr = chainl1 term' op
  >   where op = Add <$ lexemeA (char '+')
  
  Splitting the lexer parser layer out means that we have one place
  where we have to remember to add `lexeme` wrappers, and also I think
  makes the code easier to follow.
  