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:
Download the file
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
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
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
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.
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.
Expr and instance of
Arbitrary and check the data type invariant that you defined in A2 using
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!
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.)
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
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).
- 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
- Has good comments
- Has no junk (junk is unused code, commented code, unneccessary comments)
- Has no overly complicated function definitions
- Does not contain any repetitive code (copy-and-paste programming)
To the Fire System
- 2019-10-05 Fixed a couple of typos (Thomas H)
- 2018-10-15 Fix added for unicode in windows. Minor edits.
- 2018-10-13 First version (Dave Sands)