COMPSCI 1JC3 Introduction to Computational Thinking Fall 2020
Assignment 2
Dr. William M. Farmer and Curtis D’Alves McMaster University
Revised: October 29, 2020
The purpose of Assignment 2 is to write a module in Haskell that im- plements standard operations on a Euclidean space. The requirements for Assignment 2 and for Assignment 2 Extra Credit are given below. You are required to do Assignment 2, but Assignment 2 Extra Credit is optional. Please submit Assignment 2 as a single Assign 2.hs file to the Assign- ment 2 folder on Avenue under Assessments/Assignments. If you choose to do Assignment 2 Extra Credit for extra marks, please submit it also as a single Assign 2 ExtraCredit.hs file to the Assignment 2 Extra Credit folder on Avenue in the same place. Both Assignment 2 and Assignment 2 Extra Credit are due Sunday, November 1, 2020 before midnight. Assignment 2 is worth 6% of your final grade, while Assignment 2 Extra Credit is worth 2 extra percentage points.
Late submissions will not be accepted! So it is suggested that you submit a preliminary Assign 2.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 1.
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
A Euclidean space En is an n-dimensional space, used primarily in 2 or 3 dimensions as an abstraction of the physical world. Historically it was not defined formally, rather it was defined only in relation to measurements that could be taken in the physical world. A modern formal definition of n-dimensional Euclidean space treats the points in the Euclidean space as points in the vector space over Rn, using the standard addition and scalar multiplication operations. In set-theoretic terms, the Euclidean space in two dimensions is defined as
E2 = {(x, y)|x, y ∈ R}.
1
A Euclidean space is also an inner product space, i.e., for any elements p,q ∈ En with p = (a1,…,an) and q = (b1,…,bn), there exists an operation ⟨p, q⟩, called the inner product of p and q, such that
n
⟨p, q⟩ = ai ∗ bi.
i=1
Given this definition of the inner product, the notion of distance between
two elements can be defined as d(p, q) = ⟨p − q, p − q⟩.
Having this definition of distance, a Euclidean space also qualifies as a met- ric space. That’s a lot of different spaces in one! If you haven’t noticed yet, a “space” in mathematics is just a set of elements that are defined for some given operators with certain properties (i.e., addition and scalar multiplication for vector spaces, the inner product for inner product spaces, and distance for metric spaces). In mathematics, it’s useful to generalize theorems over spaces, so that proofs in, say, calculus or linear algebra work over many dimensions of real numbers or complex numbers. As you will see, these types of generalizations have a useful analog in computing.
2 Assignment 2
The purpose of this assignment is to create a Haskell module that imple- ments the standard operations on a Euclidean space.
2.1 Requirements
1. Download from Avenue Assign2 Project Template.zip which con- tains the Stack project files for this assignment. Modify the Assign 2.hs in the src folder so that the following requirements are satisfied.
2. Add your name, the date, and “Assignment 2” in the comments at the top of your file. Define macid to be your MacID.
3. The file contains a type definition that can be used to represent any element of a two dimensional Euclidean space
type Euclid2D = (Double,Double).
4. The file contains two functions getX and getY of type Euclid2D -> Double that return the x/y coordinates (first/second parts), respec- tively.
2
5. The file includes a function named scalarMult of type Double -> Euclid2D -> Euclid2D that returns the scalar multiplication of its input, i.e., s · (x, y) = (s ∗ x, s ∗ y).
6. The file includes a function named add of type Euclid2D -> Euclid2D -> Euclid2Dthatperforms2Dvectoraddition,i.e.,(x1,y1)+(x2,y2)= (x1 +x2,y1 +y2).
7. The file includes a function named innerProduct of type Euclid2D -> Euclid2D -> Double that implements the inner product operation for 2D Euclidean space, i.e., ⟨(x1, y1), (x2, y2)⟩ = x1 ∗ x2 + y1 ∗ y2.
8. The file includes a function named distance of type Euclid2D -> Euclid2D -> DoublethatimplementstheEuclideandistancebetween twoelements,i.e.,d(p,q)=⟨p−q,p−q⟩. (Noticethat(x1,y1)− (x2, y2) = (x1, y1) + (−1) · (x2, y2).)
9. The file includes a function named maxDistance of type [Euclid2D] -> Euclid2D that given a list of elements of type Euclid2D returns the element with the largest distance from (0, 0). If given an empty list it simply returns (0,0). In the case of a tie, the element closest to the head of the list is returned.
10. 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 the functions scalarMult, add, innerProduct, distance, and maxDistance. The test plan must include at least three test cases for each function. Each test case should have fol- lowing 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.
The test plan should be at the bottom of your file in a comment region beginning with a {- line and ending with a -} line.
3 Assignment 2 Extra Credit
The purpose of this assignment is to create a Haskell module for types that represent the elements in a Euclidean space.
3
3.1 Requirements
1. Add the Extra Credit functions to the Assign 2 ExtraCredit.hs file in the src folder (not Assign 2.hs). Modify this file so that the following requirements are satisfied.
2. Your name, the date, and “Assignment 2 Extra Credit” are in com- ments at the top of your file. macid is defined to be your MacID.
3. The file contains the following type definitions and type class defini- tion:
data Vector2D a = Vector2D (a,a)
deriving (Show,Eq)
class VectorSpace v where
vecZero :: Fractional a => v a
vecAdd :: Fractional a => v a -> v a -> v a
vecScalarMult :: Fractional a => a -> v a -> v a
innerProduct :: Fractional a => v a -> v a -> a
(A more accurate name for this type class is InnerProductSpace since a vector space does not need to include an inner product.)
4. Include a type class instance for VectorSpace Vector2D.
5. Import the Data.Complex module and include a type class instance
for VectorSpace Complex.
6. The file includes a function named distance of type (Floating a, VectorSpace v) => v a -> v a -> athatimplementstheEuclidean distance.
7. The file includes a function named maxDistance of type (Floating a, Ord a, VectorSpace v) => [v a] -> v a that given a list of type (Floating a, Ord a, VectorSpace v) => v a) returns the element with the largest distance from vecZero. If given an empty list it simply returns vecZero. In the case of a tie, the element closest to the head of the list is returned.
8. Your file successfully loads into GHCi and all of your functions perform correctly.
3.2 Testing
Include in your file a test plan (as described above) for the functions vecAdd, vecScalarMult, innerProduct, distance, and maxDistance. The test plan must include at least three test cases for each function.
4