Making a Calculator in Haskell with Parsec

In this article, I will show you how to use Parsec in an Applicative style to parse and evaluate simple expressions. We will make a Calculator in Haskell with Parsec library. Our calculator will support addition, subtraction, multiplication, division, and parentheses with their respective precedences. This article is aimed at showing the power of Parsec and Parsec-like libraries and the elegance of Applicative programming. Read our introductory piece on Applicatives for more information on Applicative Functors.

Imports

We’ll use the following imports for our program.

-- calculator.hs
import Text.Parsec (char, between, digit, many1)
import Text.Parsec.String (Parser)
import Data.Char (digitToInt)
import Control.Applicative (optional, (<|>), many)

Parsing decimals

Parsec does not come with decimal parser out of the box so first let’s define a decimal parser. We simply parse one or more digits and then convert the parsed string to the integer it represents.

-- calculator.hs
decimal :: Parsec String () Int 
decimal = atoi <$> many1 digit

atoi :: [Char] -> Int 
atoi = foldl f 0 where 
    f s x = 10*s + digitToInt x

We use the many1 function from Text.Parsec that parses one or more occurrences of whatever pattern you give it. Here we are using it to parse one or more digits. Next, we map the parsed digits in string format to an integer using atoi function. atoi function folds the digits to produce the integer they represent. For each new digit we shift the current integer to left (multiply by 10) and add the new digit to it.

Calculator Grammar

We’ll use the popular calculator grammar to define our parsing rules later. The snippet below shows the grammar in Backus-Naur form (BNF).

Expr   ::= Term ('+' Term | '-' Term)*
Term   ::= Factor ('*' Factor | '/' Factor)*
Factor ::= ['-'] (Number | '(' Expr ')')
Number ::= Digit+

According to our grammar above, an expression Expr is either a single term Term or multiple terms joined with + or - operators. Addition and Subtraction are handled at Expr level. A Term is either a single Factor or multiple Factors joined with * or / operators. Multiplication and division are handled at Term level. A Factor is either a number or an expression inside a parentheses. Factor can optionally be prefixed with - sign to make it negative. Parentheses are handled at Factor level. Number is defined as one or more digits representing an integer.

Implementing the grammar in Parsec

Now it’s time to write some Haskell to implement the above grammar using Parsec.

Expr

haskell-- calculator.hs expr :: Parser Int expr = pure eval <*> term <*> many (pure (,) <*> (char '+' <|> char '-') <*> term)

First is the expr :: Parser Int Parser that corresponds to Expr symbol in our grammar. Type Parser is imported from Text.Parsec.String module and represents a parser of String type. So Parser Int is a parser of String that produces an Int.

Now consider term <*> many (pure (,) <*> (char '+' <|> char '-') <*> term) part of our parser definition. Here we parse a term (we’ll define it later) that’s followed by zero or more (many) (char '+' <|> char '-') <*> term parts. This is exactly how we defined Expr symbol in our grammar. We use the choice function <|> function from Control.Applicative to tell Parsec to parse either a + or a - character (but not both). We use the <*> function from Control.Applicative to lift a pure function (,) to apply it to the character produced by (char '+' <|> char '-') and the term produced the following term parser to wrap them in a tuple. The type of term as we’ll see later is Parser Int so pure (,) <*> (char '+' <|> char '-') <*> term gives us a parser of type Parser (Char, Int). many function from Applicative module is applied here to tell Parsec to keep parsing (Char, Int) as long as it can. Thus, applying many to Parser (Char, Int) type gives us a parser of type Parser [(Char, Int)].

Next, we need to combine the Parser Int from our first term and Parser [(Char, Int)] into a single Parser Int. We do that by applying a pure function eval :: Int -> [(Char,Int)] -> Int (we’ll define this later) that will fold the parsed integers and operators into a single integer by adding/subtracting the integers as appropriate. Once again we use <*> function to apply eval on values wrapped in Applicatives (Parsers).

Term

-- calculator.hs
term :: Parser Int 
term = pure eval <*> factor <*> many (pure (,) <*> (char '*' <|> char '/') <*> factor)

term parser is very similar to expr just like the Term symbol is similar to Expr symbol in our grammar. Here instead of parsing + and - operators we parse * and / instead. Instead of parsing terms we parse factors as described in our grammar.

-- calculator.hs
eval :: Int -> [(Char,Int)] -> Int 
eval x [] = x 
eval x (('+', x'):xs) = eval (x + x') xs
eval x (('-', x'):xs) = eval (x - x') xs
eval x (('*', x'):xs) = eval (x * x') xs
eval x (('/', x'):xs) = eval (x `div` x') xs

Now we define eval function as shown above. It is a simple folding function that has an aggregator to which it adds/subtracts/multiplies/divides integers from the list depending on what operator they carry with them.

Factor

-- calculator.hs
factor :: Parser Int 
factor = pure f <*> optional (char '-') <*> (decimal <|> between (char '(') (char ')') expr)
    where 
        f Nothing x = x 
        f _ x = negate x

Our final piece is the factor parser. With (decimal <|> between (char '(') (char ')') expr) it parses either a decimal or an expr wrapped in parentheses. It also parses an optional - character before the decimal or expression using the optional function from Control.Applicative module. This is for negation of the decimal or the expression, of course. Finally, we produce a value by applying f function on the optional negation operator and the parsed integer value. f simply negates the parsed integer value if the - operator was parsed by the parser.

Showtime

And that’s it! Let’s give our tiny calculator a go.

-- ghci
λ> :l calculator.hs 
[1 of 1] Compiling Main             ( calculator.hs, interpreted )
Ok, one module loaded.
λ> import Text.Parsec (parse)
λ> parse expr "" "1+1"
Right 2
λ> parse expr "" "1+1-2"
Right 0
λ> parse expr "" "1+2*3*2-2"
Right 11
λ> parse expr "" "1+2*3*(2-2)"
Right 1

Looks like it works! You can try adding support for more operators such as exponentiation, log, square root etc.

Summary

Today we saw some Applicative coding in action for making a Calculator app in Haskell with Parsec. You might have noticed that we used no let declarations or do notations anywhere in our code. This is a typical benefit of Applicative style of coding. <*> is a powerful function that allows us to write compact and succinct code that has a great functional feel. Happy Haskelling!

Appendix - Source code

The complete calculator program is reproduced below.

-- calculator.hs
import Text.Parsec (char, between, digit, many1)
import Text.Parsec.String (Parser)
import Data.Char (digitToInt)
import Control.Applicative (optional, (<|>), many)

atoi :: [Char] -> Int 
atoi = foldl f 0 where 
    f s x = 10*s + digitToInt x

decimal :: Parser Int 
decimal = atoi <$> many1 digit

expr :: Parser Int
expr = pure eval <*> term <*> many (pure (,) <*> (char '+' <|> char '-') <*> term)

term :: Parser Int 
term = pure eval <*> factor <*> many (pure (,) <*> (char '*' <|> char '/') <*> factor)

eval :: Int -> [(Char,Int)] -> Int 
eval x [] = x 
eval x (('+', x'):xs) = eval (x + x') xs
eval x (('-', x'):xs) = eval (x - x') xs
eval x (('*', x'):xs) = eval (x * x') xs
eval x (('/', x'):xs) = eval (x `div` x') xs

factor :: Parser Int 
factor = pure f <*> optional (char '-') <*> (decimal <|> between (char '(') (char ')') expr)
    where 
        f Nothing x = x 
        f _ x = negate x