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 Extra 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 Assessments/Assignments. If you choose to do Assignment 4 Extra Credit for extra 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. Assignment 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 implements 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 applying the following standard differentiation rules (expressed in Leibniz notation):
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 contains 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 implementations 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” evaluated 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 implements 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 assignment in the Assign 4 Test.hs file in the test folder.
2. Your name, the date, and “Assignment 4 Extra Credit” are in comments 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.