Introduction to Functional Programming – Lab 4A “Simplify” | TDA555 / DIT440, LP1 2018 |
Home | Schedule | Labs | Lectures | Exercises | Exam | About | FAQ | Fire | WaitList | Slack | TimeEdit | YouTube | Links |
Introduction to Functional Programming – Lab 4A “Simplify” | TDA555 / DIT440, LP1 2018 |
Home | Schedule | Labs | Lectures | Exercises | Exam | About | FAQ | Fire | WaitList | Slack | TimeEdit | YouTube | Links |
In 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.
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
. Poly.hs
provides the following:
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).
Update: 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 simply by converting expressions to polynomials (Poly), and converting them back again. Since polynomials are represented in a canonical way then 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.
prop_Expr :: Expr -> Bool
which checks that exponents anywhere in an expression are not negative.
x^2
. You should show x1 as just x, but otherwise you should not simplify your expressions in any way before you show them.
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)[https://www.youtube.com/watch?v=98e1L4CVXP4] 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.
simplify :: Expr -> Expr
which simplifies an expression by converting it to a polynomial and back again (this is easy).
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 A07)
You must submit using the Fire system preferably in groups of 3.
You should only submit: your version of Lab4A.hs
. Do not upload any other files.
Before you submit your code, Clean It Up! Remember, submitting clean code is Really Important, and simply the polite thing to do. After you feel you are done, spend some time on cleaning your code; make it simpler, remove unneccessary things, etc. We will reject your solution if it is not clean. Clean code:
We expect you to run the hlint
command on your program and follow the advice given. If you do not understand the advice you should include your original code in comments in your submission. (You are welcome to use it for part I, but unless you have read about higher-order functions you probably won’t understand the advice.)