Lab 3: Parsing Party - Simple Infix Calculator

Posted on October 21, 2019

Building a Simple Haskell Calculator

Later in the course you will consider monadic parsing, but in this lab we will focus on the simple parsing problem of constructing a calculator. The goal is to gain some experience with handling strings and input.

The calculator should work as follows:

$ ./Main
> 1 + 1
> 2 * 6
> (1 + 3) * (5 + 1)
> (1 + 02 + 3 * 2 + 6)
> (1 + (2 + ((4 + 2) * 6)))
> 5 +-6    -- This should be parsed as 5 + (-6)

where user-input is indicated by a prepended >.

In this lab you will:

Skeleton Program

Pull your repository, in the lab3 folder you should see three files, Main.hs, Lab3.hs, and Tests.hs. You will modify and turn in all three files.

Most of your code will be written in Lab3.hs.

The main file will import Lab3 to perform the main I/O loop.

Write tests in Tests.hs to drive your development.

$ ghci Tests.hs
*Tests> showFailures


In Lab3.hs, define the ArithExp Data Type. Recursion is the name of the game.

This data type should represent:

The abstract ArithExp form for (2+3)*(3+2) would be

(Mult (Plus (Number 2) (Number 3)) (Plus (Number 3) (Number 2)))

Evaluating an ArithExp

Again, use recursion. eval should be a function that takes ArithExp and outputs a number. This is the first thing to get working. For division, use the quot function. Check that your eval works by ensuring that you get the right outputs for:

(Number (-3))
(Mult (Plus (Number 2) (Number (-6))) (Plus (Number 3) (Number 2)))
(Div (Number 13) (Number 6))
(Plus (Mult (Number 2) (Number 3)) (Div (Number 13) (Number (-6))))

and some other expressions. Generate your own simple ones and make sure that things work. Add any new cases to Tests.hs.

Parsing a String to ArithExp

The input will be *, -, +, [0-9], (, ), and /. Also, any - will always precede a number [0-9]. You do not have to handle bad input.

Here’s everything you’ll have to do:

Work incrementally. Begin by tokenizing and parsing simple expressions:

1 + 20
1 * -2

Then get order of operations working correctly:

1 + 2 * 3 + 4
1 * 2 + 3 + 4

Then tokenize and parse parentheses enclosing an entire expression:

 ( -2 )
 (1 + 2 )
(1 * 2 + 3)

Finally, work out how to recursively handle nested parentheses:

(-10 + 2) * 5
5 * (-10 + (2 + 4) * 3)
5 * (-10 + (2 + 4) * 3) * (3 + 2)

Handling parenthetical expressions is probably the trickiest part of the lab. You may choose to do it as part of tokenize or as part of parse.

Possibly Helpful Functions

In Data.Char:

In Data.List:

In Control.Applicative:


Debug.Trace will help you debug. Start with traceShowId.


A skeleton Tests.hs file has been provided for you, which you can run in GHCi.

$ ghci Tests.hs
*Tests> showFailures

A few tests for eval have been provided for you. You are expected to fill out tests for tokenize and parse, but you may want to test helper functions as well.

We will not look too closely at your tests, but their presence and success are part of your grade. You should practice test-driven development (TDD) for this lab:

  1. Write a test.
  2. Watch it fail.
  3. Write code to make it pass.
  4. Repeat.

When the tests have convinced you that your code is correct, you are done.


Make sure your code is pushed to your repository by Thursday October 31 before 11:59pm.

Your submission should include changes in all three files.

Be sure ghc Main.hs does not error.

Be sure ghci Tests.hs does not error and asking for results in GHCi does not error.

Grading breakdown:

You are primarily evaluated on whether you correctly implement the calculator.

Extra Credit

For extra credit, instead implement the eval function and main loop such that your program calculates and operates on rational numbers instead of integers. For example, instead of (15 / 6) evaluating to 2, your program would instead output 5 / 2. Ensure that the rational numbers in the output are in lowest terms. Whole number outputs can be displayed either as whole numbers or fractions (both 4 or 4 / 1 are acceptable). You can expect that your program will still only receive integers in the input.

Do the above in your original lab files (do not turn in separate files). But, you should commit before attempting the extra credit in case you can’t get it to work and need to revert back before the submission deadline.

This extra credit is worth at most 10%.