COMPSCI 1JC3 C01

Introduction to Computational Thinking

Fall 2020

Assignment 4

Dr. William M. Farmer

McMaster University

Revised: November 23, 2020

The requirements for Assignment 4 and for Assignment 4 Extra Credit

are given below. You are required to do Assignment 4, but Assignment 4 Ex￾tra Credit is optional. Please submit Assignment 4 as two files, Assign 4.hs

and Assign 4 Test.hs, to the Assignment 4 folder on Avenue under Assess￾ments/Assignments. If you choose to do Assignment 4 Extra Credit for ex￾tra marks, please submit it also as two files, Assign 4 ExtraCredit.hs and

Assign 4 Test ExtraCredit.hs, to the Assignment 4 Extra Credit folder

on Avenue in the same place. Both Assignment 4 and Assignment 4 Extra

Credit are due Sunday, November 29, 2020 before midnight. Assign￾ment 4 is worth 6% of your final grade, while Assignment 4 Extra Credit is

worth 2 extra percentage points.

Late submissions will not be accepted! So it is suggested that you

submit a preliminary Assign 4.hs file well before the deadline so that your

mark is not zero if, e.g., your computer fails at 11:50 PM on November 17.

Although you are allowed to receive help from the instructional

staff and other students, your submitted program must be your

own work. Copying will be treated as academic dishonesty!

1 Assignment 4

The purpose of this assignment is to create a Haskell module that imple￾ments a derivative calculator that performs minor simplification and does

no domain analysis. Derivative calculators on the web usually do major

simplification but completely ignore domain analysis.

1.1 Background

For the purposes of this assignment, let a mathematical expression be an

expression that is constructed from an indeterminant x and members of R

by applying addition (+), multiplication (∗), power (^), cosine (cos), sine

(sin), and absolute value (abs). Let M be a set of mathematical expressions.

1

The value of a mathematical expression u ∈ M at r ∈ R is the result of

replacing the indeterminant x in u with r. For example, the value of

(x + 1) ∗ (x x 1)

5 ∗ x

at 3 is

(3 + 1) ∗ (3 3 1)

5 ∗ 3 = 8

15

.

It is usually advantageous to simplify, when possible, a mathematical

expression u to another mathematical expression v such that u and v have

the same values for all r ∈ R. The following rules show, for example, how

mathematical expressions can be simplified:

1. 0 + u = u + 0 = u.

2. 0 ∗ u = u ∗ 0 = 0.

3. 1 ∗ u = u ∗ 1 = u.

4. u + (v + w) = (u + v) + w.

5. u ∗ (v ∗ w) = (u ∗ v) ∗ w.

6. u ∗ (v + w) = u ∗ v + u ∗ w.

7. (u + v) ∗ w = u ∗ w + v ∗ w.

8. u0 = 1.

9. abs(abs(x)) = abs(x).

A mathematical expression can be symbolically differentiated by apply￾ing the following standard differentiation rules (expressed in Leibniz nota￾tion):

Variable Rule

d

dx(x) = 1

Constant Rule

d

dx(r) = 0 where r ∈ R

Sum Rule

d

dx(u + v) = d

dx(u) + d

dx(v) 2

Product Rule

d

dx(u ∗ v) = d

dx(u) ∗ v + u ∗ d

dx(v)

Power Rule

d

dx(un

) = n ∗ unn1 ∗ d

dx(u)

Cosine Rule

d

dx(cos(u)) = =sin(u) ∗ d

dx(u)

Sine Rule

d

dx(sin(u)) = cos(u) ∗ d

dx(u)

Absolute Value Rule

d

dx|u| = u|u| ∗ d

dx(u)

Derivative calculators on the web usually assume that whenever u is

a mathematical expression, the derivative of a function f(x) = u is the

function f0(x) = d

dx (u). This is not always the case: For example, if f(x) =

u = |x|, then d

dx (u) = x|x|

but f0(x) = x|x|

only if x = 0 and f0(x) is undefined

if x = 0. For this reason, a proper derivative calculator should do domain

analysis and thus, given a mathematical expression u as input, return:

1. d

dx (u) in simplified form.

2. The domain D ⊆ R on which the derivative is defined.

So for our example, given |x| as input, a derivative calculator should return:

1.

x|x|.

2. {x ∈ R | x = 0}.

1.2 Requirements

1. Download from Avenue Assign4 Project Template.zip which con￾tains the Stack project files for this assignment. Modify the

Assign 4.hs file in the src folder so that the following requirements

are satisfied. Also put your testing code for this assignment in the

Assign 4 Test.hs file in the test folder.

2. Your name, the date, and “Assignment 4” are in comments at the top

of your file. macid is defined to be your MacID.

3

3. The file contains the following algebraic data type definition:

data MathExpr a =

X

| Coef a

| Sum ( MathExpr a ) ( MathExpr a )

| Prod ( MathExpr a ) ( MathExpr a )

| Power ( MathExpr a ) Int

| Cos ( MathExpr a )

| Sin ( MathExpr a )

| Abs ( MathExpr a )

deriving ( Eq , Show , Read )

4. The file includes a function named eval of type

(Floating a, Eq a) => MathExpr a -> a -> a

such that, if e is an expression of type (MathExpr a) and v is a floating

point number, eval e v is the value of e at v (i.e. subbing v for X

and evaluating).

5. The file includes an instance Num a => Num (MathExpr a) with im￾plementations for the following methods (leave the other class methods

undefined, i.e. produce an error).

(+) :: Num a => a -> a -> a

(*) :: Num a => a -> a -> a

negate :: Num a => a -> a

abs :: Num a => a -> a

fromInteger :: Num a => Integer -> a

6. The file includes an instance Fractional a => Fractional (MathExpr

a) with implementations for the following methods (leave the other

class methods undefined, i.e. produce an error).

recip :: Fractional a => a -> a

fromRational :: Fractional a => Rational -> a

7. The file includes an instance Floating a => Floating (MathExpr

a) with implementations for the following methods (leave the other

class methods undefined, i.e. produce an error).

pi :: Floating a => a

sin :: Floating a => a -> a

cos :: Floating a => a -> a

4

8. The file includes a function named diff of type

(Floating a, Eq a) => MathExpr a -> MathExpr a

such that, if u is an expression of type (MathExpr a), diff u is the

result of symbolically differentiating u using the differential rules given

above.

9. The file includes a function named pretty of type

(Show a) => MathExpr a -> String

such that, if u is an expression of type (MathExpr a), pretty u will

create a String representation of u. Each constructor will result in

the following String representations:

X "X"

Coef c "c"

Sum u0 u1 "(u0 + u1)"

Prod u0 u1 "(u0 * u1)"

Power u0 d "(u0 ^^ d)"

Cos u0 "cos(u0)"

Sin u0 "sin(u0)"

Abs u0 "abs(u0)"

Here u0 and u1 are subexpressions that also need to be “pretty” evalu￾ated and c and d are Num and Int values, respectively, that are turned

into a String value with show and then, when necessary, enclosed in

parentheses. Note: You should be able to copy the output of pretty

and “re-enter” it into GHCi, for example:

*Assign_4> pretty (X + 2 * X)

"(X + (2 * X))"

*Assign_4> (X + (2 * X))

Sum X (Prod (Coef 2) X)

10. Your file can be imported into GHCi and all of your functions perform

correctly.

1.3 Testing

Include in your file a test plan for the functions eval, diff, and pretty.The

test plan must include at least three test cases for each function. Each test

case should have following form:

5

Function: Name of the function being tested.

Test Case Number: The number of the test case.

Input: Inputs for function.

Expected Output: Expected output for the function.

Actual Output: Actual output for the function.

In addition, your test plan must include at least one QuickCheck case for

each of the functions eval, and diff. Each QuickCheck case should have

following form:

Function: Name of the function being tested.

Property: Code defining the property to be tested by QuickCheck.

Actual Test Result: Pass or Fail.

The test plan should be at the bottom of your file in a comment region

beginning with a {- line and ending with a -} line. Put your testing code

for this assignment in the Assign 4 Test.hs file in the test folder.

2 Assignment 4 Extra Credit

The purpose of this assignment is to create a Haskell module that imple￾ments a derivative calculator that performs major simplification.

2.1 Requirements

1. Modify the Assign 4.hs file in the src folder so that the following

requirements are satisfied. Also put your testing code for this assign￾ment in the Assign 4 Test.hs file in the test folder.

2. Your name, the date, and “Assignment 4 Extra Credit” are in com￾ments at the top of your file. macid is defined to be your MacID.

3. Include in your file the required components of Assignment 4.

4. The file includes a function named simp of type

(Floating a, Eq a) => MathExpr a -> MathExpr a

such that, if u is an expression of type (MathExpr a), simp u is the

result of simplifying u by applying the simplification rules listed in the

background section. It should fully simplify to a normal formal, i.e.

∀e ∈ MathExpr, simp(e) = simp(simp(e))

5. Your file successfully loads into GHCi and all of your functions perform

correctly.

6

2.2 Testing

Include in your file a test plan for the simp function. The test plan must

include at least three test cases and at least one QuickCheck case. The test

plan should be at the bottom of your file in a comment region beginning

with a {- line and ending with a -} line. Put your testing code for this

assignment in the Assign 4 Test ExtraCredit.hs file in the test folder.