TDA 555
DIT 440
HT 2019

# Lab Assignment 4A: Simplify (2019)

## Purpose

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.

## Preparations

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

Before you start working:

• Download the file `Poly.hs`. `Poly.hs` provides the following:

• An abstract type `Poly` which is the type of polynomial expressions. (“abstract” here just means that the constructors for `Poly` are hidden - so you can only build elements of this type using the functions provided by the module)
• `fromList :: [Int] -> Poly` for converting a list of numbers into a polynomial.
• `toList :: Poly -> [Int]` for converting in the other direction.
• `evalPoly :: Int -> Poly -> Int` for evaluating a polynomial.
• Download a template solution file `Lab4A.hs`

• Watch this short video introducing `Poly.hs`. (You don’t need to look at the definition of this module, but feel free to do so if you are curious, as the Haskell code in it does not contain anything that you have not seen in the course).

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`.

### Overview

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.

A1

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.

A2
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.
A3
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.
A4
Make `Expr` and instance of `Arbitrary` and check the data type invariant that you defined in A2 using `quickCheck`.
A5
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!

A6

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.

A7

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.

A8
write a function `simplify :: Expr -> Expr` which simplifies an expression by converting it to a polynomial and back again (this is easy).
A9
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:

• Does not have long lines (< 78 characters)
• Has a consistent layout (avoid using TAB characters in your code)
• Has type signatures for all top-level functions that you are asked to write