COMPSCI 1JC3 C01 Introduction to Computational Thinking Fall 2020
Assignment 5
Dr. William M. Farmer and Curtis D’Alves McMaster University
Revised: December 2, 2020
The purpose of Assignment 5 is implement a practical higher-order func- tion. The requirements for Assignment 5 and for Assignment 5 Extra Credit are given below. You are required to do Assignment 5, but Assignment 5 Ex- tra Credit is optional. Please submit Assignment 5 as two files, Assign 5.hs and Assign 5 Test.hs, to the Assignment 5 folder on Avenue under Assess- ments/Assignments. If you choose to do Assignment 5 Extra Credit for ex- tra marks, please submit it also as two files, Assign 5 ExtraCredit.hs and Assign 5 Test ExtraCredit.hs, to the Assignment 5 Extra Credit folder on Avenue in the same place. Both Assignment 5 and Assignment 5 Extra Credit is due December 13, 2020 before midnight. Assignment 5 is worth 4% of your final grade, while Assignment 5 Extra Credit is worth 2 extra percentage points.
Late submissions will not be accepted! So it is suggested that you submit preliminary Assign 5.hs and Assign 5 Test.hs files well before the deadline so that your mark is not zero if, e.g., your computer fails at 11:50 PM on December 13.
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 Background
Using the trapezoidal rule, the value of a definite integral b
f(x)dx a
can be approximated by the summation
n f(xi−1)+f(xi) ∗ b−a i=1 2 n
1
where
a=x0
such that
definiteIntegral a b g n
computes an approximation to the definite integral
b
f(x)dx
a
using the trapezoidal rule with n partitions and using g to represent the function f : R → R.
4. The file includes a function arcsin1 of type Integer -> Double such that arcsin1 n computes the definite integral of
1 1 − x2dx = arcsin(1) = π −1 2
using the definiteIntegral function with n partitions. 2
5. The file includes a function piApprox of type Double -> Double that uses arcsin1 to approximate π where piApprox tol returns a value pi’ such that
|pi’ − pi| ≤ tol
for the built-in Haskell approximation pi (this should be manageable
for tol ≥ 10−5).
6. The file includes a function logApprox of type Double -> Double -> Double such that logApprox x tol ap- proximates the value of log x by exploiting its definition as a definite integral, i.e.,
x1
log(x) =
Use the definiteIntegral function, and return the approximation
that uses the smallest number of partitions n such that |(definiteIntegral 1 x g n)−(definiteIntegral 1 x g (n-1))| ≤ tol.
7. Your file can be imported into GHCi and all of your functions perform correctly.
2.2 Testing
Include in your file a test plan for all four functions mentioned above. The test plan must include at least three test cases for each function. Each test case should have following form:
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 four functions. 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 5 Test.hs file in the test folder.
1
t dt
3
3 Background Extra Credit
Monte-Carlo Integration is a technique for computing approximations of definite integrals relying on random number generation. Recall, a definite integral
b
f(x)dx
a
is the area between the curve of f(x) and the x-axis over the domain a ≤ x ≤ b. Monte-Carlo Integration relies on approximating this area as a ratio of the area of the smallest rectangle that can encapsulate the curve over the given domain. Approximating the ratio of this rectangle is done by generating random sampling points within the rectangle, and counting the number of points inside the curve (hits) vs the number of points outside of the curve (misses).
More formally, given a hit function H(x,y), a number of samples N and a set of randomly generated samples {(xi,yi) · i ← {1..N}}, one can approximate a function f(x) with
b 1N
f (x) ≈ ( N H (xi , yi )) × ((b − a) × (maxa,b (f ) − mina,b (f )))
a i=N
Figure 1: Example Sampling of a Quarter Unit Circle
As an example, consider computing the area of the unit circle (circle of radius 1). To simplify the problem, we’ll compute only the positive/upper- right quadrant. Given the circle has radius 1, the area of the encapsulating rectangle is 1 × 1 = 1. The hit function is given by
1 if x2 + y2 ≤ 1 H(x,y) = 0 else
Figure 1 shows an example sampling of the unit circle, where hits/misses are denoted by red/black dots respectively. After simplifying the area of the
4
rectangle to 1, and multiplying by 4, we can apply the above equation to compute the full area of the unit circle
N
11−x2dx≈4∗ 1 H(xi,yi)
o N i=N
Generally, a uniform distribution is the simplest distribution to sam- ple from. However sometimes a different distribution such as the normal distribution is more appropriate. The Box-Muller transform can be used to take two uniform distribution samples U1 and U2 on the unit interval (0, 1) and return a point (Z1, Z2) from a standard normal distribution, where
Z0 = Rcos(θ) = −2lnU1cos(2πU2) Z1 = Rsin(θ) = −2lnU1sin(2πU2)
4 Assignment 5 Extra Credit
The purpose of this assignment is to create a Haskell module for approxi- mating the definite integral of a function f : R → R in
4.1 Requirements
1. Download from Avenue Assign5 Project Template.zip which con- tains the Stack project files for this assignment. Modify the Assign 5.hs file in the src folder so that the following requirements are satisfied. Also put your testing code for this assignment in the Assign 5 Test.hs file in the test folder.
2. Your name, the date, and “Assignment 5” are in comments at the top of your file. macid is defined to be your MacID.
3. The file includes a function uniformSample2D of type (Random a,Floating a) => IO (a,a)
that returns a random uniformly distributed point in the IO monad over the unit interval (0, 1). Hint: the function randomRIO from the System.Random library returns a single uniformly distributed ran- dom sample. See documentation for System.Random here http:// hackage.haskell.org/package/random-1.1/docs/System-Random. html)
4. The file includes a function uniformToNorm of type Floating a => a -> a -> (a,a)
that takes two uniformly distributed samples and transforms them to a normally distributed sample point using the Box Muller transform
5
5. The file includes a function normalSample2D of type (Random a, Floating a) => IO (a,a)
that returns a random normally distributed point in the IO monad voer the unit interval (0, 1)
6. The file includes a function genSamples of type
(Random a, Floating a) => IO (a,a) -> Int -> IO [(a,a)]
that takes a sampling function (i.e uniformSample2D or normalSample2D), an Integer N and generates a list of N randomly generated samples in the IO monad
7. The file includes a function monteCarlo2D of type
Floating a => a -> a -> [(a,a)] -> ((a,a) -> Bool) -> a
that (assuming your working in the upper-right positive quadrant of a coordinate plane) takes xMax such that the domain of the definite integral is (0,xMax), a value yMax that’s assumed to be the maxi- mum value of the function over the domain it’s being integrated, a list of samples and a boolean hit function and returns the Monte-Carlo Integration approximation.
8. The file includes a function unitCircleHit of type (Floating a,Ord a) => (a,a) -> Bool
that is the hit function for the unit circle (Hint: H(x,y) as defined in Section Background)
9. The file includes a function estimatePi of type
IO (Double,Double) -> Int -> IO Double
that uses Monte-Carlo Integration to estimate the value of pi. It takes a sampling function (i.e uniformSample2D or normalSample2D) and an Integer N of number of samples to take.Note: the value of pie is the area of the unit circle (or 4 times the area of the first quadrant of the unit circle). A uniform distribution should yield a good guess of π at a sufficiently high N. Interestingly, a normal distribution will generally half the number hits in the first quadrant, giving a good guess for π
2
10. Your file can be imported into GHCi and all of your functions perform correctly.
6
4.2 Testing
Include in your file a test plan for uniformSample2D, uniformToNorm, normalSample2D, genSamples, unitCircleHit. The test plan must should thoroughly cover critical all critical cases per function. Functions returning random values need not have specific output listed (i.e can specify range, property like normally distributed in Expected Output). Each test case should have following form:
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 uniformToNorm and unitCircleHit. 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 5 Test.hs file in the test folder.
7