Designing a simple parser with functional programming

A calculator in functional programming

In this exercise, we will see how to implement a calculator from scratch using pure functional programming techniques. We will look at the basic principle of a parser, and at the possibilities offered by an applicative functor interface. No prior knowledge of any library is required for this exercise, apart from the Haskell prelude, whose basic functions we will use. We will define everything we need ourselves, and the complete code will be under 100 lines. This implementation can thus easily be translated into another programming language.

The goal of our exercise is to design a basic calculator, to be used as follows:

> evalExpr "(12 - 2) * 5"
Just 50
> evalExpr "12 - 2 * 5"
Just 2
> evalExpr "3 - foobar"
Nothing

Let's start the Calc module

module Calc where

Defining the type of an algebraic expression

The operations our calculator can perform on integers are addition, subtraction and multiplication.

data Expr = Add Expr Expr
          | Sub Expr Expr
          | Mul Expr Expr
          | Lit Integer

The evaluator for such an expression is easy to define recursively.

eval :: Expr -> Integer
eval e = case e of
  Add a b -> eval a + eval b
  Sub a b -> eval a - eval b
  Mul a b -> eval a * eval b
  Lit n   -> n

Defining the type of a parser

We are going to define a type that corresponds to a basic parser. In its simplest form, a parser is a function (->) that takes a stream (String) as parameter, and analyses the beginning of this stream until it can produce, if possible, (Maybe) a result. In that case, the result is returned, along with the rest of the stream (the unprocessed part). If no result can be produced, then nothing at all is returned (Nothing). The type is parameterized by r, which defines the type of the result the parser can produce. A parser that reads an integer from the stream could produce Integer values, so its type would be Parser Integer.

type Parser r = String -> Maybe (r, String)

Primitives to manipulate parsers

With our data type defining the general shape of a parser, we will now define primitives that will be useful to manipulate them. We will take the opportunity to define an "applicative functor" interface, which allows parsers to be combined and chained together.

First of all, we need a primitive that lets us build a parser by defining its result value in advance. This will be useful in particular when we no longer want to consume the stream and we already know which result to return.

pure :: a -> Parser a
pure x = \s -> Just (x, s)

Next, we will define the "map" function on our functor. Indeed, all applicative functors are, first of all, functors, which must therefore provide the map operation. For convenience, we will define it as an infix operator, so that f <$> x == map f x.

The definition of map for our functor is simple:

• we take a function to apply and a parser to apply it to
• if the parser succeeds, we apply the function to the result
• if the parser fails (Nothing), we do nothing

(<$>) :: (a -> b) -> Parser a -> Parser b
f <$> p = \s -> case p s of
  Just (a, s') -> Just (f a, s')
  Nothing      -> Nothing

We will then define another function, again as an infix operator for convenience. We will call it apply and write it <*>. This function is somewhat reminiscent of the previous one, except that this time the function to apply is contained in our parser functor. Apply will let us chain parsers along the stream, but not in just any way. With apply, we can chain parsers that will be the successive parameters of a function. The idea is the following: we have a function (or a constructor, which is similar) that must find its multiple parameters one after the other in the stream. Used together with map, our apply function lets us use this function directly with our parsers, without handling the stream explicitly. The principle of apply is simple: the left parser processes the stream; if it succeeds, it produces a function along with the rest of the stream. We then apply the right parser to the rest of the stream, and if that succeeds, we apply the function produced by the first parser to the result of the second parser, and return that together with the remaining stream. In the typical use case, we build the first parser with map over a function f, then chain the parameters of f with apply.

(<*>) :: Parser (a -> b) -> Parser a -> Parser b
p1 <*> p2 = \s -> case p1 s of
                   Just (f, s') -> case p2 s' of
                     Just (a, s'') -> Just (f a, s'')
                     Nothing       -> Nothing
                   Nothing -> Nothing

This apply operator is at the heart of the applicative functor concept. At first, the concept is not easy to grasp, so if needed I encourage you to look for general documentation on the subject. You can also keep reading this document until you reach the usage examples, then come back to the definition above to better understand them.

The next two functions are convenient variants of apply, which ignore the right parameter and the left parameter respectively. They are useful when we want to consume a portion of the stream with a parser without using the result as a function parameter. Imagine for example that you want to parse the addition of two integers, to build the value Add Int1 Int2. Parsing the "+" sign is necessary to validate the expression, but we will not use the parsed sign afterwards, once the operation has been identified. You can therefore write Add <$> number <*> (plus *> number): the Add constructor will be used with the two retained parameters, but the parser will have checked and consumed the '+' sign in the stream.

(<*) :: Parser a -> Parser b -> Parser a
p1 <* p2 = const <$> p1 <*> p2

(*>) :: Parser a -> Parser b -> Parser b
p1 *> p2 = (flip const) <$> p1 <*> p2

Another tool we will need is the or operator, written <|>. Its behaviour is simple too: if the left parser succeeds, its result is returned and the right parser is ignored. Otherwise, the value of the right parser is returned. This operator lets us try several parsers on our stream, when several possibilities are available.

(<|>) :: Parser a -> Parser a -> Parser a
p1 <|> p2 = \s -> let r1 = p1 s in
  case r1 of
   Just _  -> r1
   Nothing -> p2 s

This or function defines the alternative functor nature of our Parser a type.

The runParser function simply applies a parser to a stream and returns the result, if there is one, and if the stream has been entirely consumed.

runParser :: Parser a -> String -> Maybe a
runParser p s = case p s of
  Just (r, "") -> Just r
  _            -> Nothing

Useful combinators

Equipped with our primitives, we can now define a few combinators that we will use to define our parsers.

To begin with, we can define the many combinator, which repeats a parser and produces the list of results. Note that the many parser never fails: if it cannot apply its parameter parser, it succeeds with the empty list as result. Its recursive definition relies on map (with the list constructor (:) as the function) and apply for the two parameters (the head and the recursive tail).

many :: Parser a -> Parser [a]
many p = ((:) <$> p <*> many p) <|> pure []

Some is a variant of many, which requires at least one successful occurrence (the head of the list) for the parser to succeed.

some :: Parser a -> Parser [a]
some p = ((:) <$> p <*> many p)

Check is a combinator that works on the first character of the stream. It checks a predicate (parameter) on this character and, on success, produces the character as result (and consumes it from the stream). Otherwise it fails.

check :: (Char -> Bool) -> Parser Char
check f = \s -> case s of
  (x:xs) | f x -> Just (x, xs)
  _            -> Nothing

Parsers

We will now define the few parsers we need to analyse an arithmetic expression.

The char parser parses a specific character at the head of the stream.

char :: Char -> Parser Char
char c = check (== c)

The oneOf parser takes a list of char as parameter, and tries to parse one of these characters at the head of the stream.

oneOf :: [Char] -> Parser Char
oneOf cs = check (\c -> elem c cs)

The spaced parser consumes the spaces around a parser, and returns the result of that parser. It is used to clean the stream of separators that have no semantic meaning.

spaced :: Parser a -> Parser a
spaced p = spaces *> p <* spaces
  where spaces = many (check (== ' '))

number reads an integer from the stream. It uses the Haskell read function to convert a character string into an integer.

number :: Parser Integer
number = read <$> some digit
  where digit = oneOf "0123456789"

That's it, this is all we need as basic parsers to split arithmetic expressions, and thus define the expression parser expr.

As a reminder, the grammar of our calculator is the following

number = digit { digit }
digit  = 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
expr   = mul + mul | mul - mul | mul
mul    = factor * factor | factor
factor = "(" expr ")" | number

The translation into a parser is straightforward with the toolbox we defined above. For the sake of brevity, we also define a small helper function binOp which combines a binary operator (the Add, Sub and Mul constructors) and a parser that will be applied twice.

This parser directly builds the syntax tree corresponding to our expression. The flexibility of our parser lets us express the operator precedence rules directly, through the order in which the parsers are applied.

expr :: Parser Expr
expr = add_sub
  where
    add_sub = binOp Add '+' mul <|> binOp Sub '-' mul <|> mul
    mul = binOp Mul '*' factor <|> factor
    factor = parens <|> lit
    lit = Lit <$> spaced number
    parens = spaced (char '(' *> expr <* char ')')
    binOp c o p = c <$> (p <* spaced (char o)) <*> p

The following small tool combines the expression parser and the evaluator into a single function.

evalExpr :: String -> Maybe Integer
evalExpr s = (fmap eval) $ runParser expr s

Complete code

Here is the complete code of our tool. To use it, copy the content into a file, load it with ghci (ghci calc.hs), and use the evalExpr function.

module Calc where

data Expr = Add Expr Expr
          | Sub Expr Expr
          | Mul Expr Expr
          | Lit Integer

eval :: Expr -> Integer
eval e = case e of
  Add a b -> eval a + eval b
  Sub a b -> eval a - eval b
  Mul a b -> eval a * eval b
  Lit n   -> n


type Parser r = String -> Maybe (r, String)

pure :: a -> Parser a
pure x = \s -> Just (x, s)

(<$>) :: (a -> b) -> Parser a -> Parser b
f <$> p = \s -> case p s of
  Just (a, s') -> Just (f a, s')
  Nothing      -> Nothing

(<*>) :: Parser (a -> b) -> Parser a -> Parser b
p1 <*> p2 = \s -> case p1 s of
                   Just (f, s') -> case p2 s' of
                     Just (a, s'') -> Just (f a, s'')
                     Nothing       -> Nothing
                   Nothing -> Nothing

(<*) :: Parser a -> Parser b -> Parser a
p1 <* p2 = const <$> p1 <*> p2

(*>) :: Parser a -> Parser b -> Parser b
p1 *> p2 = (flip const) <$> p1 <*> p2

(<|>) :: Parser a -> Parser a -> Parser a
p1 <|> p2 = \s -> let r1 = p1 s in
  case r1 of
   Just _  -> r1
   Nothing -> p2 s

runParser :: Parser a -> String -> Maybe a
runParser p s = case p s of
  Just (r, "") -> Just r
  _            -> Nothing

many :: Parser a -> Parser [a]
many p = ((:) <$> p <*> many p) <|> pure []

some :: Parser a -> Parser [a]
some p = ((:) <$> p <*> many p)

check :: (Char -> Bool) -> Parser Char
check f = \s -> case s of
  (x:xs) | f x -> Just (x, xs)
  _            -> Nothing

char :: Char -> Parser Char
char c = check (== c)

oneOf :: [Char] -> Parser Char
oneOf cs = check (\c -> elem c cs)

spaced :: Parser a -> Parser a
spaced p = spaces *> p <* spaces
  where spaces = many (check (== ' '))

number :: Parser Integer
number = read <$> some digit
  where digit = oneOf "0123456789"

expr :: Parser Expr
expr = add_sub
  where
    add_sub = binOp Add '+' mul <|> binOp Sub '-' mul <|> mul
    mul = binOp Mul '*' factor <|> factor
    factor = parens <|> lit
    lit = Lit <$> spaced number
    parens = spaced (char '(' *> expr <* char ')')
    binOp c o p = c <$> (p <* spaced (char o)) <*> p

evalExpr :: String -> Maybe Integer
evalExpr s = (fmap eval) $ runParser expr s

Alternative definition, using Haskell's standard typeclasses

In its base library, Haskell provides typeclasses for the functor, applicative and alternative interfaces. Using these typeclasses brings a few advantages, in particular the fact that with a minimal instance definition, a whole set of useful functions automatically becomes available. This is the case for example of *>, many, some etc. Below is a definition based on these standard classes (about 50 lines of code).

module CalcApplicative where

import Control.Applicative

data Expr = Add Expr Expr
          | Sub Expr Expr
          | Mul Expr Expr
          | Lit Integer

eval :: Expr -> Integer
eval e = case e of
  Add a b -> eval a + eval b
  Sub a b -> eval a - eval b
  Mul a b -> eval a * eval b
  Lit n   -> n

-- New datatype required for the instances
data Parser r = Parser {parse :: String -> Maybe (r, String)}

-- Instances
instance Functor Parser where
  fmap f (Parser p) = Parser $ \s -> case p s of
    Just (a, s') -> Just (f a, s')
    Nothing      -> Nothing

instance Applicative Parser where
  pure x = Parser $ \s -> Just (x, s)
  Parser p1 <*> pp2 = Parser $ \s -> case p1 s of
    Just (f, s') -> case parse pp2 s' of
      Just (a, s'') -> Just (f a, s'')
      Nothing       -> Nothing
    Nothing -> Nothing

instance Alternative Parser where
  empty = Parser $ const Nothing
  (Parser p1) <|> pp2 = Parser $ \s -> p1 s <|> parse pp2 s

-- The rest is identical
runParser :: Parser a -> String -> Maybe a
runParser (Parser p) s = case p s of
  Just (r, "") -> Just r
  _            -> Nothing

check :: (Char -> Bool) -> Parser Char
check f = Parser $ \s -> case s of
  (x:xs) | f x -> Just (x, xs)
  _            -> Nothing

char :: Char -> Parser Char
char c = check (== c)

oneOf :: [Char] -> Parser Char
oneOf cs = check (\c -> elem c cs)

number :: Parser Integer
number = read <$> some digit
  where digit = oneOf "0123456789"

expr :: Parser Expr
expr = add_sub
  where
    add_sub = binOp Add '+' mul <|> binOp Sub '-' mul <|> mul
    mul = binOp Mul '*' factor <|> factor
    factor = parens <|> lit
    lit = Lit <$> number
    parens = char '(' *> expr <* char ')'
    binOp c o p = c <$> p <*> (char o *> p)

evalExpr :: String -> Maybe Integer
evalExpr s = (fmap eval) $ runParser expr $ concat $ words s

See also:

• Designing with categories (in French)
• Monads in functional programming (in French)
• AtikTeam collaborative platform