CombinatorReview.lhs

[[combinator-review]]
= Combinator review

In this tutorial we will go through all the functions in
Text.Parsec.Combinator, and some useful ones in Control.Applicative
and Control.Monad as well.

> import Text.Parsec (ParseError)
> import Text.Parsec.String (Parser)
> import Text.Parsec.String.Parsec (try)
> import Text.Parsec.String.Char (oneOf, char, digit
>                                ,string, letter, satisfy)
> import Text.Parsec.String.Combinator (many1, choice, chainl1, between
>                                      ,count, option, optionMaybe, optional)
> import Control.Applicative ((<$>), (<*>), (<$), (<*), (*>), (<|>), many)
> import Control.Monad (void, ap, mzero)
> import Data.Char (isLetter, isDigit)
> import FunctionsAndTypesForParsing

== Text.Parsec.Combinator

You should look at the source for these functions and try to
understand how they are implemented.

<http://hackage.haskell.org/package/parsec-3.1.3/docs/src/Text-Parsec-Combinator.html>

The style of the source code in the Parsec library sources is a little
different to what we used at the end of the last tutorial. You can try
reimplementing each of the Text.Parsec.Combinator module functions
using the Applicative style. See if you can find a way to reassure
yourself that the rewritten versions you make are correct, perhaps via
writing automated tests, or perhaps some other method.

You should be able to easily understand the implementation of all the
functions in Text.Parsec.Combinator except possibly `anyToken` and
`notFollowedBy`.

=== choice

```haskell
choice :: [Parser a] -> Parser a
```

`choice ps` tries to apply the parsers in the list `ps` in order,
until one of them succeeds. It returns the value of the succeeding
parser.

> a :: Parser Char
> a = char 'a'
>
> b :: Parser Char
> b = char 'b'
>
> aOrB :: Parser Char
> aOrB = choice [a,b]

```
*Main> regularParse aOrB "a"
Right 'a'

*Main> regularParse aOrB "b"
Right 'b'

*Main> regularParse aOrB "c"
Left (line 1, column 1):
unexpected "c"
expecting "a" or "b"
```

==== using with try

If a parser fails with `(<|>)` or `choice`, then it will only try the
next parser if the last parser consumed no input.

TODO: make the parsers return the keyword and update the examples

> byKeyword :: Parser ()
> byKeyword = void $ string "by"
>
> betweenKeyword :: Parser ()
> betweenKeyword = void $ string "between"

Since both of these have the same prefix - b - if we combine them
using `choice` then it doesn't work correctly:

```
*Main> regularParse byKeyword "by"
Right ()

*Main> regularParse byKeyword "between"
Left (line 1, column 1):
unexpected "e"
expecting "by"

*Main> regularParse betweenKeyword "between"
Right ()

*Main> regularParse betweenKeyword "by"
Left (line 1, column 1):
unexpected "y"
expecting "between"

*Main> regularParse (choice [betweenKeyword,byKeyword]) "between"
Right ()

*Main> regularParse (choice [betweenKeyword,byKeyword]) "by"
Left (line 1, column 1):
unexpected "y"
expecting "between"

*Main> regularParse (choice [byKeyword,betweenKeyword]) "between"
Left (line 1, column 1):
unexpected "e"
expecting "by"

*Main> regularParse (choice [byKeyword,betweenKeyword]) "by"
Right ()
```

If we use `try` on the first option, then it all works fine.

```
*Main> regularParse (choice [try byKeyword,betweenKeyword]) "by"
Right ()

*Main> regularParse (choice [try byKeyword,betweenKeyword]) "between"
Right ()
```

=== count

```haskell
count :: Int -> Parser a -> Parser [a]
```

`count n p` parses `n` occurrences of `p`. If `n` is smaller or equal
to zero, the parser is equivalent to `return []`. It returns a list of
the n values returned by `p`.

```
*Main> regularParse (count 5 a) "aaaaa"
Right "aaaaa"

*Main> regularParse (count 5 a) "aaaa"
Left (line 1, column 5):
unexpected end of input
expecting "a"

*Main> regularParse (count 5 a) "aaaab"
Left (line 1, column 5):
unexpected "b"
expecting "a"

*Main> regularParse (count 5 aOrB) "aabaa"
Right "aabaa"
```

=== between

```haskell
between :: Parser open -> Parser close -> Parser a -> Parser a
```

`between open close p` parses `open`, followed by `p` and
`close`. It returns the value returned by `p`.

We can replace the betweenParens from the previous tutorial using
this:

> betweenParens :: Parser a -> Parser a
> betweenParens p = between (symbol '(') (symbol ')') p

It hardly seems worth it to make this change, but it might be slightly
quicker to read and understand if you aren't already familiar with
some code or haven't viewed it for a while. This is good for 'code
maintenance', where we need to fix bugs or add new features quickly to
code we haven't looked at for two years or something.

Here are the support functions for this parser.

> symbol :: Char -> Parser Char
> symbol c = lexeme $ char c

> lexeme :: Parser a -> Parser a
> lexeme p = p <* whitespace

> whitespace :: Parser ()
> whitespace = void $ oneOf " \n\t"

=== option

```haskell
option :: a -> Parser a -> Parser a
```

`option x p` tries to apply parser `p`. If `p` fails without
consuming input, it returns the value `x`, otherwise the value returned
by `p`.

```
*Main> regularParse (option "" (count 5 aOrB)) "aaaaa"
Right "aaaaa"

*Main> regularParse (option "" (count 5 aOrB)) "caaaa"
Right ""

*Main> regularParse (option "" (count 5 aOrB)) "aaaa"
Left (line 1, column 5):
unexpected end of input
expecting "a" or "b"

*Main> regularParse (option "" (count 5 aOrB)) "aaaac"
Left (line 1, column 5):
unexpected "c"
expecting "a" or "b"

*Main> regularParse (option "" (try (count 5 aOrB))) "aaaa"
Right ""
```

=== optionMaybe

```haskell
optionMaybe :: Parser a -> Parser (Maybe a)
```

`optionMaybe p` tries to apply parser `p`. If `p` fails without consuming
input, it returns `Nothing`, otherwise it returns `Just` the value returned
by `p`.

```
*Main> regularParse (optionMaybe (count 5 aOrB)) "aaaaa"
Right (Just "aaaaa")

*Main> regularParse (optionMaybe (count 5 aOrB)) "caaaa"
Right Nothing

*Main> regularParse (optionMaybe (count 5 aOrB)) "caaa"
Right Nothing

*Main> regularParse (optionMaybe (count 5 aOrB)) "aaaa"
Left (line 1, column 5):
unexpected end of input
expecting "a" or "b"

*Main> regularParse (optionMaybe (count 5 aOrB)) "aaaac"
Left (line 1, column 5):
unexpected "c"
expecting "a" or "b"

*Main> regularParse (optionMaybe (try $ count 5 aOrB)) "aaaac"
Right Nothing
```

=== optional

```haskell
optional :: Parser a -> Parser ()
```

`optional p` tries to apply parser `p`. It will parse `p` or
nothing. It only fails if `p` fails after consuming input. It discards
the result of `p`.

```
*Main> parseWithLeftOver (optional (count 5 aOrB)) "aaaaa"
Right ((),"")

*Main> parseWithLeftOver (optional (count 5 aOrB)) "caaaa"
Right ((),"caaaa")

*Main> parseWithLeftOver (optional (count 5 aOrB)) "caaa"
Right ((),"caaa")

*Main> parseWithLeftOver (optional (count 5 aOrB)) "aaaa"
Left (line 1, column 5):
unexpected end of input
expecting "a" or "b"

*Main> parseWithLeftOver (optional (count 5 aOrB)) "aaaac"
Left (line 1, column 5):
unexpected "c"
expecting "a" or "b"

*Main> parseWithLeftOver (optional (try $ count 5 aOrB)) "aaaac"
Right ((),"aaaac")
```

=== skipMany1

```haskell
skipMany1 :: Parser a -> Parser ()
```

`skipMany1 p` applies the parser `p` one or more times, skipping its result.

=== many1

```haskell
many1 :: Parser a -> Parser [a]
```

many1 p applies the parser p one or more times. Returns a list of the
returned values of p.

```haskell
  word  = many1 letter
```

=== sepBy

```haskell
sepBy :: Parser a -> Parser sep -> Parser [a]
```

sepBy p sep parses zero or more occurrences of p, separated by
sep. Returns a list of values returned by p.

```haskell
  commaSep p  = p `sepBy` (symbol ",")
```

=== sepBy1

```haskell
sepBy1 :: Parser a -> Parser sep -> Parser [a]
```

sepBy1 p sep parses one or more occurrences of p, separated by
sep. Returns a list of values returned by p.

=== endBy

```haskell
endBy :: Parser a -> Parser sep -> Parser [a]
```

endBy p sep parses zero or more occurrences of p, seperated and ended
by sep. Returns a list of values returned by p.

```haskell
   cStatements  = cStatement `endBy` semi
```

=== endBy1

```haskell
endBy1 :: Parser a -> Parser sep -> Parser [a]
```

endBy1 p sep parses one or more occurrences of p, seperated and ended
by sep. Returns a list of values returned by p.

=== sepEndBy

```haskell
sepEndBy :: Parser a -> Parser sep -> Parser [a]
```

sepEndBy p sep parses zero or more occurrences of p, separated and
optionally ended by sep, ie. haskell style statements. Returns a list
of values returned by p.

```haskell
  haskellStatements  = haskellStatement `sepEndBy` semi
```

=== sepEndBy1

```haskell
sepEndBy1 :: Parser a -> Parser sep -> Parser [a]
```

sepEndBy1 p sep parses one or more occurrences of p, separated and
optionally ended by sep. Returns a list of values returned by p.

=== chainl

```haskell
chainl :: Parser a -> Parser (a -> a -> a) -> a -> Parser a
```

chainl p op x parser zero or more occurrences of p, separated by
op. Returns a value obtained by a left associative application of all
functions returned by op to the values returned by p. If there are
zero occurrences of p, the value x is returned.

=== chainl1

```haskell
chainl1 :: Parser a -> Parser (a -> a -> a) -> Parser a
```

chainl1 p op x parser one or more occurrences of p, separated by op
Returns a value obtained by a left associative application of all
functions returned by op to the values returned by p. . This parser
can for example be used to eliminate left recursion which typically
occurs in expression grammars.

=== chainr

```haskell
chainr :: Parser a -> Parser (a -> a -> a) -> a -> Parser a
```

chainr p op x parser zero or more occurrences of p, separated by op
Returns a value obtained by a right associative application of all
functions returned by op to the values returned by p. If there are no
occurrences of p, the value x is returned.

=== chainr1

```haskell
chainr1 :: Parser a -> Parser (a -> a -> a) -> Parser a
```

chainr1 p op x parser one or more occurrences of `p`, separated by op
Returns a value obtained by a right associative application of all
functions returned by op to the values returned by p.

=== eof

```haskell
eof :: Parser ()
```

This parser only succeeds at the end of the input. This is not a
primitive parser but it is defined using notFollowedBy.

```haskell
  eof  = notFollowedBy anyToken <?> "end of input"
```

The (<?>) operator is used for error messages. We will come back to
error messages after writing the basic SQL parser.

=== notFollowedBy

```haskell
notFollowedBy :: Show a => Parser a -> Parser ()
```

notFollowedBy p only succeeds when parser p fails. This parser does
not consume any input. This parser can be used to implement the
'longest match' rule. For example, when recognizing keywords (for
example let), we want to make sure that a keyword is not followed by a
legal identifier character, in which case the keyword is actually an
identifier (for example lets). We can program this behaviour as
follows:

```haskell
  keywordLet  = try (do{ string "let"
                       ; notFollowedBy alphaNum
                       })
```

=== manyTill

```haskell
manyTill :: Parser a -> Parser end -> Parser [a]
```

manyTill p end applies parser p zero or more times until parser end
succeeds. Returns the list of values returned by p. This parser can be
used to scan comments:

```haskell
  simpleComment   = do{ string "<!--"
                      ; manyTill anyChar (try (string "-->"))
                      }
```
// asciidoc: the string should be "-->"

Note the overlapping parsers anyChar and string "-\->", and therefore
the use of the try combinator.

=== lookAhead

```haskell
lookAhead :: Parser a -> Parser a
```

lookAhead p parses p without consuming any input.

If p fails and consumes some input, so does lookAhead. Combine with
try if this is undesirable.

=== anyToken

```haskell
anyToken :: Parser Char
```

The parser anyToken accepts any kind of token. It is for example used
to implement eof. Returns the accepted token.

== Control.Applicative

Here are the functions from Applicative that are used:

`(<$>)`, `(<*>)`, `(<$)`, `(<*)`, `(*>)`, `(<|>)`, `many`

TODO: examples for all of these

We've already seen all of these, except `(<$)`. This is often used to
parse a keyword and return a no argument constructor:

> data Something = Type1 | Type2 | Type3

> something :: Parser Something
> something = choice [Type1 <$ string "type1"
>                    ,Type2 <$ string "type2"
>                    ,Type3 <$ string "type3"]

// the first symbol following should be (<**>)
// the backslashes are for asciidoc
// todo: do this in the render.lhs?
// I wish I understood why you need backslashes in some places
// and not others

There is also `(<\**>)` which is `(<*>)` with the arguments flipped.

TODO: double check using these from Parsec instead of
Control.Applicative: possible performance implictions?

== Control.Monad

=== return

One use of return is to always succeed, and return a value:

> alwaysX :: Parser Char
> alwaysX = return 'x'

```
*Main> parseWithLeftOver (a <|> alwaysX) "a"
Right ('a',"")

*Main> parseWithLeftOver (a <|> alwaysX) "b"
Right ('x',"b")
```

=== mzero

This function is used in the implementation of `choice`:

> choice' :: [Parser a] -> Parser a
> choice' ps = foldr (<|>) mzero ps



TODO: go through a bunch of functions + do notation examples

 >>=
 =<<
 >>
 void
 mapM, mapM_
 sequence,sequence_
 guard
 return
mzero
mplus
when, unless
liftMN
ap
quick note about fail, will return to this in the error messages stage

TODO: using trace