Introduction

In this coursework assignment, you will implement a simplifier for symbolic arithmetic expressions involving addition, multiplication and integer exponentiation (xn  where nis a non-negative integer).

Downloading the skeleton code

1.  Download the skeleton code zip file by going to this link.

2.  Extract the contents of the zip to wherever you want to save it

•  How to extract zip files on Windows

•  How to extract zip files on Ubuntu

•  How to extract zip files on Mac

Compiling and running tests

If your code passes all the tests, you get all the marks! It’s therefore essential that you can compile and run the tests. To do this:

1.  In VSCode (in WSL mode if you’re on Windows), open the folder containing the skeleton code

2.  Open an integrated terminal in the VSCode window,  either  by  using the  menu  bar (”Terminal ->  New Terminal”) or by using the shortcut (Ctrl + Shift + ‘).

3.  Run cabal update (this will update your package list for Haskell libraries)

4.  Run cabal build (this will build your project and the tests, which may take a little while the first time)

5.  Run cabal test (this will run the tests)

When you run this on the skeleton code all the tests should fail, because nothing has been implemented yet.

Every time you make a change, run cabal test to test it!  You can also load your code in GHCi/interactive mode using cabal repl

Write all your code in Simplify.hs, but don’t change the name or type of the functions and don’tchange any other files. You are free to write any helper functions you like, as long as you write them in Simplify.hs.

Calculating your mark

Your mark will be based on the percentage of tasks you implement correctly.   This is not the same as the percentage of passing tests.  Instead, to get the marks for a task, you must pass every test for that task.  This means all tasks are worth an equal number of marks, even if they have a different number of tests.

Submitting your coursework

Submit your work via Blackboard.  You should submit only Simplify.hs.  Do not rename Simplify.hs.   Do not submit any other files.  Do not submit a zip file.

You are responsible for early submission, therefore you should submit at least an hour before the deadline to ensure there are no upload problems. The university systems will automatically apply harsh penalties if the coursework is late by even a second.

The Expr Type

Expr is a data type which represents a subset of symbolic arithmetic expressions. It is defined in Expr.hs as:

data Expr

= Op BinOp Expr Expr

| NumLit Int

| ExpX Int

deriving (Eq, Show)

data BinOp = AddOp | MulOp

deriving (Eq, Show)

It can represent:

•  Integers, e.g.

–  NumLit 3 represents 3

•  Addition, e.g.

–  Op AddOp (NumLit 2) (NumLit 3) represents 2 + 3

•  Multiplication, e.g.

–  Op MulOp (NumLit 2) (NumLit 3) represents 2 * 3

•  Non-negative integer powers of a single variable x, e.g.

–  ExpX 2 represents x2

–  ExpX 9 represents x9

–  ExpX 0 represents x0

–  ExpX (−2) does not cause a type error, but we consider it to be invalid because it contains a negative power.  The tests will not generate any negative powers in an Expr and your functions should not

introduce any.

•  Combinations of these terms, e.g.

–  Op MulOp (NumLit 1) (Op AddOp (ExpX 4) (NumLit 3)) represents 1 * (x4  + 3)

Expr.hs also exports two functions.

eval

eval :: Int → Expr → Int

eval evaluates an expression using the given a value for x, e.g.

eval 2 (ExpX 3) == 8

prettyExpr

prettyExpr :: Expr → String

prettyExpr takes an Expr and shows it in a prettier format than the default Show instance, e.g.

prettyExpr (NumLit 4) == "4"

prettyExpr (ExpX 2) == "x^2"

prettyExpr (ExpX 1) == "x"

prettyExpr (Op AddOp (NumLit 1) (ExpX 2)) == "1 + x^2"

This function isn’t needed for the tasks or the tests, but you may find it useful while writing/debugging your code.

‘Junk’

In the following tasks you’ll have to make sure you don’t introduce ‘junk’ into your expressions. Junk is defined to be:

•  addition of zero

•  addition or multiplication of number literals

•  xn  + xn  (should be simplified to 2 * xn )

•  multiplication by one or zero

•  xn  * xm  (should be simplified to xn+m, e.g. x2  * x3  is junk because it should be simplified to x5 )

•  x0  (should be 1)

Anything else is not considered ‘junk’, and therefore you don’t need to worry about those cases (though you could if you wanted to). For example, 2x2 + 3x2  could be simplified to 5x2 , but you will neither be penalised nor rewarded for doing this.

Task 1

Define a function add :: Expr → Expr → Expr, which adds 2 expressions together without introducing any ‘junk’, e.g.

•  adding 1 and x4  should result in 1 + x4

•  adding 0 and x4  should result in x4

•  adding 1 and 2 should result in 3

Task 2

Define a function mul :: Expr → Expr → Expr, which multiplies 2 expressions together without introducing any ‘junk’, e.g.

•  multiplying 2 and x4  should result in 2 * x4

•  multiplying 0 and x4  should result in 0

•  multiplying 1 and x4  should result in x4

Task 3

Define a function addAll :: [Expr]  → Expr, which adds a list of expressions together into a single expression without introducing any ‘junk’.

Hint: You might want to reuse your add function.

Task 4

Define a function mulAll :: [Expr] → Expr, which multiplies a list of expressions together into a single expression without introducing any ‘junk’.

Hint: You might want to reuse your mul function.