TDA 555
DIT 440
HT 2019

Introduction to Functional Programming
Lab 4A

Lab Assignment 4A: Simplify (2019)


This one-week lab assignment provides some practice with using recursive data types, writing a quickCheck generator for a recursive data type, using an abstract data type, and writing quickCheck properties.


Must be submitted before Monday, October 21 at 12:00 (2019).

The submission instructions are as for Lab 3, but we will not grade orally this time.


The lab builds on the material from weeks 5-6 on recursive data types.

Before you start working:

Note: on Windows it seems that printing Unicode characters does not work out of the box and you will get an exception when tying to show a polynomial. To fix this you need to type chcp 65001 before running ghci.


In this lab you are going to implement a simplifier for symbolic arithmetic expressions involving addition, multiplication and integer exponentiation (xn where n is a non-negative Int)

You will use (but not modify) a haskell module called Poly.hs which exports a type Poly for representing polynomials (expressions like x3 − 3x + 7).

Your simplifier will work by converting expressions to polynomials (Poly), and converting them back again. Since polynomials are represented in a canonical way, this process will do the work of simplifying the expression.


Define a data type Expr to represent arithmetic expressions. Your data type should be able to represent, integers, expressions built using addition and multiplication, and integer powers of a single variable e.g. x2, x9, x10 etc.

All integers here should make use of Haskell’s Int type. For binary operators you should use a single constructor and make use of the helper type BinOp:

data BinOp = AddOp | MulOp

You should not be able to represent exponential explessions which are anything except x raised to some integer power, so for example you should not be able to represent x(1 + 1), 2x, 23, etc.

Similarly, you should not be able to represent expressions with more than one variable, so you should not be able to represent x + y.

Since we are going to work purely with integers then any negative exponents in expressions will be invalid. Define a data type invariant prop_Expr :: Expr -> Bool which checks that exponents anywhere in an expression are not negative.
Make Expr an instance of Show, making sure that you only add brackets where they are needed. Use Haskell notation for exponents e.g. x^2. You should show x1 as just x, but otherwise you should not simplify your expressions in any way before you show them.
Make Expr and instance of Arbitrary and check the data type invariant that you defined in A2 using quickCheck.
Define eval :: Int -> Expr -> Int which takes a value for x and an expression and evaluates it.

The rest of the lab concerns writing a simplifier for expressions. The strategy for simplification is to make use of the Poly library. Every expression (which satisfies the data type invariant) can be converted to a polynomial. Simplification will work just by converting to a polynomial (Poly) and back again!


Define exprToPoly :: Expr -> Poly which converts an expression into a polynomial. Here it is important to think purely recursively: think how to convert a bigger expression by converting its sub-expressions and then combining them in a suitable way.

Now define (and quickCheck) prop_exprToPoly, which checks that evaluating the polynomial you get from exprToPoly gives the same answer as evaluating the expression.


Now define the function going in the other direction, polyToExpr :: Poly -> Expr. Take care to use “smart constructors” see lecture week 6 part II to ensure that you don’t introduce “junk” like multiplication by 1 in your result.

Write (and check) a quickCheck property prop_polyToExpr for this function similar to that for A6.

write a function simplify :: Expr -> Expr which simplifies an expression by converting it to a polynomial and back again (this is easy).
The idea with simplify is that it should end you up with a simplified expression (of course). But this depends exactly how you defined A7. Write a quickCheck property prop_noJunk :: Expr -> Bool that checks that your definition does not contain any “junk”: where junk is defined to be multiplication by one or zero, addition of zero, addition or multiplication of numbers, or x to the power zero. (You may need to fix A7.)

Submission Instructions

You must submit using the Fire system in groups of 3.

You should only submit: your version of Lab4A.hs. Do not upload any other files.

Before you submit your code, spend some time on cleaning up your code; make it simpler, remove unneccessary things, etc. We will reject your solution if it is not clean. Clean code:

Feel free to use the hlint program to help with many of these issues and other haskell style issues. If a the suggestion from hlint looks like it assumes knowledge about things we haven't covered yet in the lectures, you can ignore it (or possibly include it in a comment in your code).

To the Fire System

Good Luck!

Change Log