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.

Deadline

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 (xⁿ 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 x³ − 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. x², x⁹, x¹⁰ 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), 2^x, 2³, 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 x¹ 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
• 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

Good Luck!

Change Log

• 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)