# Joachim Breitner's Homepage

## Showcasing Applicative

My plan for this week’s lecture of the CIS 194 Haskell course at the University of Pennsylvania is to dwell a bit on the concept of `Functor`

, `Applicative`

and `Monad`

, and to highlight the value of the `Applicative`

abstraction.

I quite like the example that I came up with, so I want to share it here. In the interest of long-term archival and stand-alone presentation, I include all the material in this post.^{1}

### Imports

In case you want to follow along, start with these imports:

```
import Data.Char
import Data.Maybe
import Data.List
import System.Environment
import System.IO
import System.Exit
```

### The parser

The starting point for this exercise is a fairly standard parser-combinator monad, which happens to be the result of the student’s homework from last week:

```
newtype Parser a = P (String -> Maybe (a, String))
runParser :: Parser t -> String -> Maybe (t, String)
P p) = p
runParser (
parse :: Parser a -> String -> Maybe a
= case runParser p input of
parse p input Just (result, "") -> Just result
-> Nothing -- handles both no result and leftover input
_
noParserP :: Parser a
= P (\_ -> Nothing)
noParserP
pureParserP :: a -> Parser a
= P (\input -> Just (x,input))
pureParserP x
instance Functor Parser where
fmap f p = P $ \input -> do
<- runParser p input
(x, rest) return (f x, rest)
instance Applicative Parser where
pure = pureParserP
<*> p2 = P $ \input -> do
p1 <- runParser p1 input
(f, rest1) <- runParser p2 rest1
(x, rest2) return (f x, rest2)
instance Monad Parser where
return = pure
>>= k = P $ \input -> do
p1 <- runParser p1 input
(x, rest1)
runParser (k x) rest1
anyCharP :: Parser Char
= P $ \input -> case input of
anyCharP :rest) -> Just (c, rest)
(c-> Nothing
[]
charP :: Char -> Parser ()
= do
charP c <- anyCharP
c' if c == c' then return ()
else noParserP
anyCharButP :: Char -> Parser Char
= do
anyCharButP c <- anyCharP
c' if c /= c' then return c'
else noParserP
letterOrDigitP :: Parser Char
= do
letterOrDigitP <- anyCharP
c if isAlphaNum c then return c else noParserP
orElseP :: Parser a -> Parser a -> Parser a
= P $ \input -> case runParser p1 input of
orElseP p1 p2 Just r -> Just r
Nothing -> runParser p2 input
manyP :: Parser a -> Parser [a]
= (pure (:) <*> p <*> manyP p) `orElseP` pure []
manyP p
many1P :: Parser a -> Parser [a]
= pure (:) <*> p <*> manyP p
many1P p
sepByP :: Parser a -> Parser () -> Parser [a]
= (pure (:) <*> p1 <*> (manyP (p2 *> p1))) `orElseP` pure [] sepByP p1 p2
```

A parser using this library for, for example, CSV files could take this form:

```
parseCSVP :: Parser [[String]]
= manyP parseLine
parseCSVP where
= parseCell `sepByP` charP ',' <* charP '\n'
parseLine = do
parseCell '"'
charP <- manyP (anyCharButP '"')
content '"'
charP return content
```

### We want EBNF

Often when we write a parser for a file format, we might also want to have a formal specification of the format. A common form for such a specification is EBNF. This might look as follows, for a CSV file:

```
cell = '"', {not-quote}, '"';
line = (cell, {',', cell} | ''), newline;
csv = {line};
```

It is straightforward to create a Haskell data type to represent an EBNF syntax description. Here is a simple EBNF library (data type and pretty-printer) for your convenience:

```
data RHS
= Terminal String
| NonTerminal String
| Choice RHS RHS
| Sequence RHS RHS
| Optional RHS
| Repetition RHS
deriving (Show, Eq)
ppRHS :: RHS -> String
= go 0
ppRHS where
Terminal s) = surround "'" "'" $ concatMap quote s
go _ (NonTerminal s) = s
go _ (Choice x1 x2) = p a 1 $ go 1 x1 ++ " | " ++ go 1 x2
go a (Sequence x1 x2) = p a 2 $ go 2 x1 ++ ", " ++ go 2 x2
go a (Optional x) = surround "[" "]" $ go 0 x
go _ (Repetition x) = surround "{" "}" $ go 0 x
go _ (
= c1 ++ x ++ c2
surround c1 c2 x
| a > n = surround "(" ")"
p a n | otherwise = id
'\'' = "\\'"
quote '\\' = "\\\\"
quote = [c]
quote c
type Production = (String, RHS)
type BNF = [Production]
ppBNF :: BNF -> String
= unlines . map (\(i,rhs) -> i ++ " = " ++ ppRHS rhs ++ ";") ppBNF
```

### Code to produce EBNF

We had a good time writing combinators that create complex parsers from primitive pieces. Let us do the same for EBNF grammars. We could simply work on the `RHS`

type directly, but we can do something more nifty: We create a data type that keeps track, via a *phantom* type parameter, of what Haskell type the given EBNF syntax is the specification:

```
newtype Grammar a = G RHS
ppGrammar :: Grammar a -> String
G rhs) = ppRHS rhs ppGrammar (
```

So a value of type `Grammar t`

is a description of the textual representation of the Haskell type `t`

.

Here is one simple example:

```
anyCharG :: Grammar Char
= G (NonTerminal "char") anyCharG
```

Here is another one. This one does not describe any interesting Haskell type, but is useful when spelling out the special characters in the syntax described by the grammar:

```
charG :: Char -> Grammar ()
= G (Terminal [c]) charG c
```

A combinator that creates new grammar from two existing grammars:

```
orElseG :: Grammar a -> Grammar a -> Grammar a
G rhs1) (G rhs2) = G (Choice rhs1 rhs2) orElseG (
```

We want the convenience of our well-known type classes in order to combine these values some more:

```
instance Functor Grammar where
fmap _ (G rhs) = G rhs
instance Applicative Grammar where
pure x = G (Terminal "")
G rhs1) <*> (G rhs2) = G (Sequence rhs1 rhs2) (
```

Note how the `Functor`

instance does not actually use the function. How should it? There are no values inside a `Grammar`

!

We cannot define a `Monad`

instance for `Grammar`

: We would start with `(G rhs1) >>= k = …`

, but there is simply no way of getting a value of type `a`

that we can feed to `k`

. So we will do without a `Monad`

instance. This is interesting, and we will come back to that later.

Like with the parser, we can now begin to build on the primitive example to build more complicated combinators:

```
manyG :: Grammar a -> Grammar [a]
= (pure (:) <*> p <*> manyG p) `orElseG` pure []
manyG p
many1G :: Grammar a -> Grammar [a]
= pure (:) <*> p <*> manyG p
many1G p
sepByG :: Grammar a -> Grammar () -> Grammar [a]
= ((:) <$> p1 <*> (manyG (p2 *> p1))) `orElseG` pure [] sepByG p1 p2
```

Let us run a small example:

```
dottedWordsG :: Grammar [String]
= many1G (manyG anyCharG <* charG '.') dottedWordsG
```

```
*Main> putStrLn $ ppGrammar dottedWordsG
'', ('', char, ('', char, ('', char, ('', char, ('', char, ('', …
```

Oh my, that is not good. Looks like the recursion in `manyG`

does not work well, so we need to avoid that. But anyways we want to be explicit in the EBNF grammars about where something can be repeated, so let us just make `many`

a primitive:

```
manyG :: Grammar a -> Grammar [a]
G rhs) = G (Repetition rhs) manyG (
```

With this definition, we already get a simple grammar for `dottedWordsG`

:

```
*Main> putStrLn $ ppGrammar dottedWordsG
'', {char}, '.', {{char}, '.'}
```

This already looks like a proper EBNF grammar. One thing that is not nice about it is that there is an empty string (`''`

) in a sequence (`…,…`

). We do not want that.

Why is it there in the first place? Because our `Applicative`

instance is not lawful! Remember that `pure id <*> g == g`

should hold. One way to achieve that is to improve the `Applicative`

instance to optimize this case away:

```
instance Applicative Grammar where
pure x = G (Terminal "")
G (Terminal "") <*> G rhs2 = G rhs2
G rhs1 <*> G (Terminal "") = G rhs1
G rhs1) <*> (G rhs2) = G (Sequence rhs1 rhs2)
(```
Now we get what we want:
```

```
*Main> putStrLn $ ppGrammar dottedWordsG
{char}, '.', {{char}, '.'}
```

Remember our parser for CSV files above? Let me repeat it here, this time using only `Applicative`

combinators, i.e. avoiding `(>>=)`

, `(>>)`

, `return`

and `do`

-notation:

```
parseCSVP :: Parser [[String]]
= manyP parseLine
parseCSVP where
= parseCell `sepByP` charG ',' <* charP '\n'
parseLine = charP '"' *> manyP (anyCharButP '"') <* charP '"' parseCell
```

And now we try to rewrite the code to produce `Grammar`

instead of `Parser`

. This is straightforward with the exception of `anyCharButP`

. The parser code for that inherently monadic, and we just do not have a monad instance. So we work around the issue by making that a “primitive” grammar, i.e. introducing a non-terminal in the EBNF without a production rule – pretty much like we did for `anyCharG`

:

```
primitiveG :: String -> Grammar a
= G (NonTerminal s)
primitiveG s
parseCSVG :: Grammar [[String]]
= manyG parseLine
parseCSVG where
= parseCell `sepByG` charG ',' <* charG '\n'
parseLine = charG '"' *> manyG (primitiveG "not-quote") <* charG '"' parseCell
```

Of course the names `parse…`

are not quite right any more, but let us just leave that for now.

Here is the result:

```
*Main> putStrLn $ ppGrammar parseCSVG
{('"', {not-quote}, '"', {',', '"', {not-quote}, '"'} | ''), '
'}
```

The line break is weird. We do not really want newlines in the grammar. So let us make that primitive as well, and replace `charG '\n'`

with `newlineG`

:

```
newlineG :: Grammar ()
= primitiveG "newline" newlineG
```

Now we get

```
*Main> putStrLn $ ppGrammar parseCSVG
{('"', {not-quote}, '"', {',', '"', {not-quote}, '"'} | ''), newline}
```

which is nice and correct, but still not quite the easily readable EBNF that we saw further up.

### Code to produce EBNF, with productions

We currently let our grammars produce only the right-hand side of one EBNF production, but really, we want to produce a RHS that may refer to other productions. So let us change the type accordingly:

```
newtype Grammar a = G (BNF, RHS)
runGrammer :: String -> Grammar a -> BNF
G (prods, rhs)) = prods ++ [(main, rhs)]
runGrammer main (
ppGrammar :: String -> Grammar a -> String
= ppBNF $ runGrammer main g ppGrammar main g
```

Now we have to adjust all our primitive combinators (but not the derived ones!):

```
charG :: Char -> Grammar ()
= G ([], Terminal [c])
charG c
anyCharG :: Grammar Char
= G ([], NonTerminal "char")
anyCharG
manyG :: Grammar a -> Grammar [a]
G (prods, rhs)) = G (prods, Repetition rhs)
manyG (
mergeProds :: [Production] -> [Production] -> [Production]
= nub $ prods1 ++ prods2
mergeProds prods1 prods2
orElseG :: Grammar a -> Grammar a -> Grammar a
G (prods1, rhs1)) (G (prods2, rhs2))
orElseG (= G (mergeProds prods1 prods2, Choice rhs1 rhs2)
instance Functor Grammar where
fmap _ (G bnf) = G bnf
instance Applicative Grammar where
pure x = G ([], Terminal "")
G (prods1, Terminal "") <*> G (prods2, rhs2)
= G (mergeProds prods1 prods2, rhs2)
G (prods1, rhs1) <*> G (prods2, Terminal "")
= G (mergeProds prods1 prods2, rhs1)
G (prods1, rhs1) <*> G (prods2, rhs2)
= G (mergeProds prods1 prods2, Sequence rhs1 rhs2)
primitiveG :: String -> Grammar a
= G (NonTerminal s) primitiveG s
```

The use of `nub`

when combining productions removes duplicates that might be used in different parts of the grammar. Not efficient, but good enough for now.

Did we gain anything? Not yet:

```
*Main> putStr $ ppGrammar "csv" (parseCSVG)
csv = {('"', {not-quote}, '"', {',', '"', {not-quote}, '"'} | ''), newline};
```

But we can now introduce a function that lets us tell the system where to give names to a piece of grammar:

```
nonTerminal :: String -> Grammar a -> Grammar a
G (prods, rhs))
nonTerminal name (= G (prods ++ [(name, rhs)], NonTerminal name)
```

Ample use of this in `parseCSVG`

yields the desired result:

```
parseCSVG :: Grammar [[String]]
= manyG parseLine
parseCSVG where
= nonTerminal "line" $
parseLine `sepByG` charG ',' <* newline
parseCell = nonTerminal "cell" $
parseCell '"' *> manyG (primitiveG "not-quote") <* charG '" charG
```

```
*Main> putStr $ ppGrammar "csv" (parseCSVG)
cell = '"', {not-quote}, '"';
line = (cell, {',', cell} | ''), newline;
csv = {line};
```

This is great!

### Unifying parsing and grammar-generating

Note how simliar `parseCSVG`

and `parseCSVP`

are! Would it not be great if we could implement that functionality only once, and get both a parser *and* a grammar description out of it? This way, the two would never be out of sync!

And surely this must be possible. The tool to reach for is of course to define a type class that abstracts over the parts where `Parser`

and `Grammer`

differ. So we have to identify all functions that are primitive in one of the two worlds, and turn them into type class methods. This includes `char`

and `orElse`

. It includes `many`

, too: Although `manyP`

is not primitive, `manyG`

is. It also includes `nonTerminal`

, which does not exist in the world of parsers (yet), but we need it for the grammars.

The `primitiveG`

function is tricky. We use it in grammars when the code that we might use while parsing is not expressible as a grammar. So the solution is to let it take two arguments: A `String`

, when used as a descriptive non-terminal in a grammar, and a `Parser a`

, used in the parsing code.

Finally, the type classes that we except, `Applicative`

(and thus `Functor`

), are added as constraints on our type class:

```
class Applicative f => Descr f where
char :: Char -> f ()
many :: f a -> f [a]
orElse :: f a -> f a -> f a
primitive :: String -> Parser a -> f a
nonTerminal :: String -> f a -> f a
```

The instances are easily written:

```
instance Descr Parser where
= charP
char = manyP
many = orElseP
orElse primitive _ p = p
= p
nonTerminal _ p
instance Descr Grammar where
= charG
char = manyG
many = orElseG
orElse primitive s _ = primitiveG s
= nonTerminal s g nonTerminal s g
```

And we can now take the derived definitions, of which so far we had two copies, and define them once and for all:

```
many1 :: Descr f => f a -> f [a]
= pure (:) <*> p <*> many p
many1 p
anyChar :: Descr f => f Char
= primitive "char" anyCharP
anyChar
dottedWords :: Descr f => f [String]
= many1 (many anyChar <* char '.')
dottedWords
sepBy :: Descr f => f a -> f () -> f [a]
= ((:) <$> p1 <*> (many (p2 *> p1))) `orElse` pure []
sepBy p1 p2
newline :: Descr f => f ()
= primitive "newline" (charP '\n') newline
```

And thus we now have our CSV parser/grammar generator:

```
parseCSV :: Descr f => f [[String]]
= many parseLine
parseCSV where
= nonTerminal "line" $
parseLine `sepBy` char ',' <* newline
parseCell = nonTerminal "cell" $
parseCell '"' *> many (primitive "not-quote" (anyCharButP '"')) <* char '"' char
```

We can now use this definition both to parse and to generate grammars:

```
*Main> putStr $ ppGrammar2 "csv" (parseCSV)
cell = '"', {not-quote}, '"';
line = (cell, {',', cell} | ''), newline;
csv = {line};
*Main> parse parseCSV "\"ab\",\"cd\"\n\"\",\"de\"\n\n"
Just [["ab","cd"],["","de"],[]]
```

### The INI file parser and grammar

As a final exercise, let us transform the INI file parser into a combined thing. Here is the parser (another artifact of last week’s homework) again using applicative style^{2}:

```
parseINIP :: Parser INIFile
= many1P parseSection
parseINIP where
=
parseSection <$ charP '['
(,) <*> parseIdent
<* charP ']'
<* charP '\n'
<*> (catMaybes <$> manyP parseLine)
= many1P letterOrDigitP
parseIdent = parseDecl `orElseP` parseComment `orElseP` parseEmpty
parseLine
= Just <$> (
parseDecl <*> parseIdent
(,) <* manyP (charP ' ')
<* charP '='
<* manyP (charP ' ')
<*> many1P (anyCharButP '\n')
<* charP '\n')
=
parseComment Nothing <$ charP '#'
<* many1P (anyCharButP '\n')
<* charP '\n'
= Nothing <$ charP '\n' parseEmpty
```

Transforming that to a generic description is quite straightforward. We use `primitive`

again to wrap `letterOrDigitP`

:

```
descrINI :: Descr f => f INIFile
= many1 parseSection
descrINI where
=
parseSection <* char '['
(,) <*> parseIdent
<* char ']'
<* newline
<*> (catMaybes <$> many parseLine)
= many1 (primitive "alphanum" letterOrDigitP)
parseIdent = parseDecl `orElse` parseComment `orElse` parseEmpty
parseLine
= Just <$> (
parseDecl <*> parseIdent
(,) <* many (char ' ')
<* char '='
<* many (char ' ')
<*> many1 (primitive "non-newline" (anyCharButP '\n'))
<* newline)
=
parseComment Nothing <$ char '#'
<* many1 (primitive "non-newline" (anyCharButP '\n'))
<* newline
= Nothing <$ newline parseEmpty
```

This yields this not very helpful grammar (abbreviated here):

```
*Main> putStr $ ppGrammar2 "ini" descrINI
ini = '[', alphanum, {alphanum}, ']', newline, {alphanum, {alphanum}, {' '}…
```

But with a few uses of `nonTerminal`

, we get something really nice:

```
descrINI :: Descr f => f INIFile
= many1 parseSection
descrINI where
= nonTerminal "section" $
parseSection <$ char '['
(,) <*> parseIdent
<* char ']'
<* newline
<*> (catMaybes <$> many parseLine)
= nonTerminal "identifier" $
parseIdent primitive "alphanum" letterOrDigitP)
many1 (= nonTerminal "line" $
parseLine `orElse` parseComment `orElse` parseEmpty
parseDecl
= nonTerminal "declaration" $ Just <$> (
parseDecl <$> parseIdent
(,) <* spaces
<* char '='
<* spaces
<*> remainder)
= nonTerminal "comment" $
parseComment Nothing <$ char '#' <* remainder
= nonTerminal "line-remainder" $
remainder primitive "non-newline" (anyCharButP '\n')) <* newline
many1 (
= Nothing <$ newline
parseEmpty
= nonTerminal "spaces" $ many (char ' ') spaces
```

```
*Main> putStr $ ppGrammar "ini" descrINI
identifier = alphanum, {alphanum};
spaces = {' '};
line-remainder = non-newline, {non-newline}, newline;
declaration = identifier, spaces, '=', spaces, line-remainder;
comment = '#', line-remainder;
line = declaration | comment | newline;
section = '[', identifier, ']', newline, {line};
ini = section, {section};
```

### Recursion (variant 1)

What if we want to write a parser/grammar-generator that is able to generate the following grammar, which describes terms that are additions and multiplications of natural numbers:

```
const = digit, {digit};
= {' ' | newline};
spaces = const | '(', spaces, expr, spaces, ')', spaces;
atom = atom, {spaces, '*', spaces, atom}, spaces;
mult = mult, {spaces, '+', spaces, mult}, spaces;
plus = plus; expr
```

The production of `expr`

is recursive (via `plus`

, `mult`

, `atom`

). We have seen above that simply defining a `Grammar a`

recursively does not go well.

One solution is to add a new combinator for explicit recursion, which replaces `nonTerminal`

in the method:

```
class Applicative f => Descr f where
… recNonTerminal :: String -> (f a -> f a) -> f a
instance Descr Parser where
…= let r = p r in r
recNonTerminal _ p
instance Descr Grammar where
…= recNonTerminalG
recNonTerminal
recNonTerminalG :: String -> (Grammar a -> Grammar a) -> Grammar a
=
recNonTerminalG name f let G (prods, rhs) = f (G ([], NonTerminal name))
in G (prods ++ [(name, rhs)], NonTerminal name)
nonTerminal :: Descr f => String -> f a -> f a
= recNonTerminal name (const p)
nonTerminal name p
runGrammer :: String -> Grammar a -> BNF
G (prods, NonTerminal nt)) | main == nt = prods
runGrammer main (G (prods, rhs)) = prods ++ [(main, rhs)] runGrammer main (
```

The change in `runGrammer`

avoids adding a pointless `expr = expr`

production to the output.

This lets us define a parser/grammar-generator for the arithmetic expressions given above:

```
data Expr = Plus Expr Expr | Mult Expr Expr | Const Integer
deriving Show
mkPlus :: Expr -> [Expr] -> Expr
= foldl Plus
mkPlus
mkMult :: Expr -> [Expr] -> Expr
= foldl Mult
mkMult
parseExpr :: Descr f => f Expr
= recNonTerminal "expr" $ \ exp ->
parseExpr exp
ePlus
ePlus :: Descr f => f Expr -> f Expr
exp = nonTerminal "plus" $
ePlus <$> eMult exp
mkPlus <*> many (spaces *> char '+' *> spaces *> eMult exp)
<* spaces
eMult :: Descr f => f Expr -> f Expr
exp = nonTerminal "mult" $
eMult <$> eAtom exp
mkPlus <*> many (spaces *> char '*' *> spaces *> eAtom exp)
<* spaces
eAtom :: Descr f => f Expr -> f Expr
exp = nonTerminal "atom" $
eAtom `orElse` eParens exp
aConst
aConst :: Descr f => f Expr
= nonTerminal "const" $ Const . read <$> many1 digit
aConst
eParens :: Descr f => f a -> f a
=
eParens inner id <$ char '('
<* spaces
<*> inner
<* spaces
<* char ')'
<* spaces
```

And indeed, this works:

```
*Main> putStr $ ppGrammar "expr" parseExpr
const = digit, {digit};
spaces = {' ' | newline};
atom = const | '(', spaces, expr, spaces, ')', spaces;
mult = atom, {spaces, '*', spaces, atom}, spaces;
plus = mult, {spaces, '+', spaces, mult}, spaces;
expr = plus;
```

### Recursion (variant 2)

Interestingly, there is another solution to this problem, which avoids introducing `recNonTerminal`

and explicitly passing around the recursive call (i.e. the `exp`

in the example). To implement that we have to adjust our `Grammar`

type as follows:

`newtype Grammar a = G ([String] -> (BNF, RHS))`

The idea is that the list of strings is those non-terminals that we are currently defining. So in `nonTerminal`

, we check if the non-terminal to be introduced is currently in the process of being defined, and then simply ignore the body. This way, the recursion is stopped automatically:

```
nonTerminalG :: String -> (Grammar a) -> Grammar a
G g) = G $ \seen ->
nonTerminalG name (if name `elem` seen
then ([], NonTerminal name)
else let (prods, rhs) = g (name : seen)
in (prods ++ [(name, rhs)], NonTerminal name)
```

After adjusting the other primitives of `Grammar`

(including the `Functor`

and `Applicative`

instances, wich now again have `nonTerminal`

) to type-check again, we observe that this parser/grammar generator for expressions, with genuine recursion, works now:

```
parseExp :: Descr f => f Expr
= nonTerminal "expr" $
parseExp
ePlus
ePlus :: Descr f => f Expr
= nonTerminal "plus" $
ePlus <$> eMult
mkPlus <*> many (spaces *> char '+' *> spaces *> eMult)
<* spaces
eMult :: Descr f => f Expr
= nonTerminal "mult" $
eMult <$> eAtom
mkPlus <*> many (spaces *> char '*' *> spaces *> eAtom)
<* spaces
eAtom :: Descr f => f Expr
= nonTerminal "atom" $
eAtom `orElse` eParens parseExp aConst
```

Note that the recursion is only going to work if there is at least one call to `nonTerminal`

somewhere around the recursive calls. We still cannot implement `many`

as naively as above.

### Homework

If you want to play more with this: The homework is to define a parser/grammar-generator for EBNF itself, as specified in this variant:

```
identifier = letter, {letter | digit | '-'};
spaces = {' ' | newline};
quoted-char = non-quote-or-backslash | '\\', '\\' | '\\', '\'';
terminal = '\'', {quoted-char}, '\'', spaces;
non-terminal = identifier, spaces;
option = '[', spaces, rhs, spaces, ']', spaces;
repetition = '{', spaces, rhs, spaces, '}', spaces;
group = '(', spaces, rhs, spaces, ')', spaces;
atom = terminal | non-terminal | option | repetition | group;
sequence = atom, {spaces, ',', spaces, atom}, spaces;
choice = sequence, {spaces, '|', spaces, sequence}, spaces;
rhs = choice;
production = identifier, spaces, '=', spaces, rhs, ';', spaces;
bnf = production, {production};
```

This grammar is set up so that the precedence of `,`

and `|`

is correctly implemented: `a , b | c`

will parse as `(a, b) | c`

.

In this syntax for BNF, terminal characters are quoted, i.e. inside `'…'`

, a `'`

is replaced by `\'`

and a `\`

is replaced by `\\`

– this is done by the function `quote`

in `ppRHS`

.

If you do this, you should able to round-trip with the pretty-printer, i.e. parse back what it wrote:

```
*Main> let bnf1 = runGrammer "expr" parseExpr
*Main> let bnf2 = runGrammer "expr" parseBNF
*Main> let f = Data.Maybe.fromJust . parse parseBNF. ppBNF
*Main> f bnf1 == bnf1
True
*Main> f bnf2 == bnf2
True
```

The last line is quite meta: We are using `parseBNF`

as a parser on the pretty-printed grammar produced from interpreting `parseBNF`

as a grammar.

### Conclusion

We have again seen an example of the excellent support for abstraction in Haskell: Being able to define so very different things such as a parser and a grammar description with the same code is great. Type classes helped us here.

Note that it was crucial that our combined parser/grammars are only able to use the methods of `Applicative`

, and *not* `Monad`

. `Applicative`

is less powerful, so by giving less power to the user of our `Descr`

interface, the other side, i.e. the implementation, can be more powerful.

The reason why `Applicative`

is ok, but `Monad`

is not, is that in `Applicative`

, the *results do not affect the shape of the computation*, whereas in `Monad`

, the whole point of the bind operator `(>>=)`

is that *the result of the computation is used to decide the next computation*. And while this is perfectly fine for a parser, it just makes no sense for a grammar generator, where there simply are no values around!

We have also seen that a phantom type, namely the parameter of `Grammar`

, can be useful, as it lets the type system make sure we do not write nonsense. For example, the type of `orElseG`

ensures that both grammars that are combined here indeed describe something of the same type.

It seems to be the week of applicative-appraising blog posts: Brent has posted a nice piece about enumerations using

`Applicative`

yesterday.↩︎I like how in this alignment of

`<*>`

and`<*`

the`>`

point out where the arguments are that are being passed to the function on the left.↩︎

Have something to say? You can post a comment by sending an e-Mail to me at <mail@joachim-breitner.de>, and I will include it here.