Skip to content
Tutorials Center
My learning

Topics

Lesson 48 of 57 ยท Real-world Haskell

Project: Expression Calculator

Build an arithmetic calculator in Haskell in three stages: a tokenizer, a parser into an expression tree, and an evaluator with Either errors, plus tests.

In this project you will build a calculator that reads "2 * (3 + 4) - 5" and prints 9. It is small, but it is the same pipeline used by real compilers and interpreters: text โ†’ tokens โ†’ syntax tree โ†’ result. Each stage is a pure function, which makes every stage easy to test on its own.

You will use algebraic data types, recursive types, Either for errors, and the parsing ideas from Parsing with Parser Combinators. Here we write a hand-rolled recursive-descent parser instead of combinators, so you see the mechanism clearly.

Real Haskell is not installed on this site, so Haskell blocks are read-only. Each stage has a runnable JavaScript stand-in with the same design and the same results.

The plan

Three pure stages

Tokenize Text into numbers and symbols.
Parse Tokens into an expression tree.
Evaluate Tree into a number or an error.

Every stage returns Either, so errors flow through.

1 / 2

Stage 1: types

Start with the types. They document the whole design:

HASKELL
data Token
  = TNum Double
  | TPlus | TMinus | TStar | TSlash
  | TLParen | TRParen
  deriving (Show, Eq)

data Expr
  = Num Double
  | Neg Expr
  | BinOp Op Expr Expr
  deriving (Show, Eq)

data Op = Add | Sub | Mul | Div
  deriving (Show, Eq)

data CalcError
  = BadChar Char
  | UnexpectedToken Token
  | UnexpectedEnd
  | DivideByZero
  deriving (Show, Eq)

A separate CalcError type, instead of a String, means callers can pattern match on what went wrong and tests can compare errors exactly.

Stage 2: the tokenizer

The tokenizer walks the characters and produces tokens, skipping spaces. A number is a run of digits with an optional decimal point, grabbed with span:

HASKELL
tokenize :: String -> Either CalcError [Token]
tokenize [] = Right []
tokenize (c : cs)
  | isSpace c = tokenize cs
  | c == '+'  = (TPlus :)   <$> tokenize cs
  | c == '-'  = (TMinus :)  <$> tokenize cs
  | c == '*'  = (TStar :)   <$> tokenize cs
  | c == '/'  = (TSlash :)  <$> tokenize cs
  | c == '('  = (TLParen :) <$> tokenize cs
  | c == ')'  = (TRParen :) <$> tokenize cs
  | isDigit c || c == '.' =
      let (numText, rest) = span (\x -> isDigit x || x == '.') (c : cs)
      in  ((TNum (read numText) :) <$> tokenize rest)
  | otherwise = Left (BadChar c)

The <$> maps over the Either: if the rest fails, the failure passes straight through; if it succeeds, we put our token on the front. (read would crash on malformed text like 1.2.3; a production version would use readMaybe, which is a good exercise.)

JS Stage 1: the tokenizer

Press Run (or Ctrl + Enter) to see the console output here.

No output.

Stage 3: the parser

The grammar is the one from the parsing lesson, now with unary minus:

TEXT
expr   = term   (("+" | "-") term)*
term   = factor (("*" | "/") factor)*
factor = number | "-" factor | "(" expr ")"

A recursive-descent parser has one function per rule. Each takes the remaining tokens and returns the tree and the tokens still unused:

HASKELL
type Parse a = [Token] -> Either CalcError (a, [Token])

parseExpr :: Parse Expr
parseExpr ts = do
  (lhs, rest) <- parseTerm ts
  loop lhs rest
  where
    loop lhs (TPlus  : rest) = next Add lhs rest
    loop lhs (TMinus : rest) = next Sub lhs rest
    loop lhs rest            = Right (lhs, rest)
    next op lhs rest = do
      (rhs, rest') <- parseTerm rest
      loop (BinOp op lhs rhs) rest'

parseTerm :: Parse Expr
parseTerm ts = do
  (lhs, rest) <- parseFactor ts
  loop lhs rest
  where
    loop lhs (TStar  : rest) = next Mul lhs rest
    loop lhs (TSlash : rest) = next Div lhs rest
    loop lhs rest            = Right (lhs, rest)
    next op lhs rest = do
      (rhs, rest') <- parseFactor rest
      loop (BinOp op lhs rhs) rest'

parseFactor :: Parse Expr
parseFactor (TNum n : rest) = Right (Num n, rest)
parseFactor (TMinus : rest) = do
  (e, rest') <- parseFactor rest
  Right (Neg e, rest')
parseFactor (TLParen : rest) = do
  (e, rest') <- parseExpr rest
  case rest' of
    (TRParen : rest'') -> Right (e, rest'')
    (t : _)            -> Left (UnexpectedToken t)
    []                 -> Left UnexpectedEnd
parseFactor (t : _) = Left (UnexpectedToken t)
parseFactor []      = Left UnexpectedEnd

parse :: [Token] -> Either CalcError Expr
parse ts = do
  (e, rest) <- parseExpr ts
  case rest of
    []      -> Right e
    (t : _) -> Left (UnexpectedToken t)

The loop helpers build left-nested trees, so 10 - 3 - 2 becomes BinOp Sub (BinOp Sub 10 3) 2. The do blocks use the Either monad: the first Left aborts the rest, exactly like the Maybe chains in do-Notation Demystified.

JS Stage 2: the parser

Press Run (or Ctrl + Enter) to see the console output here.

No output.

Stage 4: the evaluator

The evaluator is a plain fold over the tree. Division is the only operation that can fail:

HASKELL
eval :: Expr -> Either CalcError Double
eval (Num n)   = Right n
eval (Neg e)   = negate <$> eval e
eval (BinOp op l r) = do
  a <- eval l
  b <- eval r
  apply op a b

apply :: Op -> Double -> Double -> Either CalcError Double
apply Add a b = Right (a + b)
apply Sub a b = Right (a - b)
apply Mul a b = Right (a * b)
apply Div _ 0 = Left DivideByZero
apply Div a b = Right (a / b)

And one function ties the three stages together with the Either monad:

HASKELL
calculate :: String -> Either CalcError Double
calculate input = tokenize input >>= parse >>= eval

main :: IO ()
main = do
  line <- getLine
  putStrLn $ case calculate line of
    Left err -> "error: " ++ show err
    Right x  -> show x

calculate is the whole program in one line, and it never throws.

JS The complete calculator

Press Run (or Ctrl + Enter) to see the console output here.

No output.

Stage 5: tests

Because everything is pure, tests are one-liners. With Hspec (see Testing: HUnit, Hspec and QuickCheck):

HASKELL
import Test.Hspec

main :: IO ()
main = hspec $ do
  describe "calculate" $ do
    it "respects precedence" $
      calculate "1 + 2 * 3" `shouldBe` Right 7
    it "is left-associative" $
      calculate "10 - 3 - 2" `shouldBe` Right 5
    it "handles unary minus" $
      calculate "-(4 + 1) * 2" `shouldBe` Right (-10)
    it "reports division by zero" $
      calculate "1 / (3 - 3)" `shouldBe` Left DivideByZero
    it "reports unknown characters" $
      calculate "2 $ 3" `shouldBe` Left (BadChar '$')
    it "reports a missing bracket" $
      calculate "(1 + 2" `shouldBe` Left UnexpectedEnd

A QuickCheck property can go further: render a random Expr back to text, then check that parsing and evaluating the text gives the same answer as evaluating the tree directly.

Ideas to extend it

  • Replace read with readMaybe and add a BadNumber error.
  • Add ^ for powers (right-associative) and a % operator.
  • Add variables and a let x = 5 command with a Map String Double environment; the State monad can thread it.
  • Report the position of an error by storing an offset in each token.
  • Rewrite the parser with megaparsec and compare the error messages.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Why does calculate use Either rather than throwing exceptions?

    Each stage returns Either CalcError, and >>= stops at the first Left, so the program stays pure and never crashes.
  2. 2. How is operator precedence achieved in the parser?

    term is parsed inside expr, so * and / bind more tightly than + and -.
  3. 3. What tree does 10 - 3 - 2 produce?

    The loop folds to the left, so subtraction is left-associative and the result is 5.
  4. 4. Which stage can produce DivideByZero?

    Only the evaluator performs arithmetic; the earlier stages deal with text and structure.

Summary

  • The calculator is a pipeline of pure functions: tokenize, parse, evaluate.
  • Algebraic data types describe tokens, the expression tree and errors.
  • A recursive-descent parser has one function per grammar rule; looping builds left-associative trees.
  • Either and >>= propagate the first error automatically, so calculate is one line.
  • Pure stages make testing simple with Hspec and QuickCheck.

Next: Project: Command-Line Todo App.