[SOLVED] Haskell math COMPSCI 1JC3 Introduction to Computational Thinking Fall 2019

COMPSCI 1JC3 Introduction to Computational Thinking Fall 2019
Assignment 2
Curtis DAlves / Dr. William M. Farmer McMaster University
Revised: September 28, 2019
The purpose of Assignment 2 is to write a module in Haskell that im- plements standard operations over the Gaussian integers. 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 Assignment 2 folder on Avenue under Assessments/Assignments. If you choose to do As- signment 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 Monday, October 21, 2018 before midnight. Assign- ment 2 is worth 4% 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 October 21.
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 Gaussian integer is simply a complex number with coefficients restricted to be integers. Stated formally, they are the set Z[i] such that
Z[i] = {a + bi | a, b Z}
where i2 = 1.
Integer arithmetic is distinct from real arithmetic particularly concerning
division. Integer division chooses to disregard the remainder of a division. A fan of precision might ask why not round rather than throw away the remainder. Recall in Haskell two separate division operators exist / and div, each operating on their own distinct type classes. Given some thought,
1

one may wonder why not make a single division operator that is a mem- ber of the Num type class like + and *. This is because the Integer type needs its own distinct version of division. To understand why consider the following problem: A room has a ceiling of 105 cm and you wish to stack 10 cm boxes in it. How many boxes can you stack? This is an example of discrete problem that requires integer arithmetic. Gaussian integers combine complex arithmetic and integer arithmetic.
Historical note: The Gaussian integers were introduced by the great mathematician Carl Friedrich Gauss in 1832.
2 Assignment 2
The purpose of this assignment is to create a Haskell module that imple- ments the standard operations over the Gaussian integers.
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 Gaussian integer a + bi
type GaussianInt = (Integer,Integer).
4. The file contains two functions gaussReal and gaussImag of type GaussianInt -> Integer that return the real/imaginary (first/second) parts, respectively.
5. The file includes a function named gaussConj of type GaussianInt -> GaussianInt that returns the conjugate of its input. The conjugate of a complex number a+bi is abi
6. The file includes a function named gaussAdd of type GaussianInt -> GaussianInt -> GaussianInt that adds two Gaussian integers. The addition of two Gaussian integers (a0 + b0i) and (a1 + b1i) is (a0 +a1)+(b0 +b1)i
7. The file includes a function named gaussMult of type GuassianInt -> GaussianInt -> GaussianInt that multiplies two Gaussian integers. The multiplication of two Gaussian integers (a0 + b0i) and (a1 + b1i) is a0a1 b0b1 + (a0b1 + b0a1)i
2

8. The file includes a function named gaussNorm of type GaussianInt -> GaussianInt -> Integer that implements the norm. The norm of a Gaussian integer is the multiplication of it with its conjugate, i.e., (a + bi) (a bi) = a2 + b2. Note: You could define this function using just the previous two functions.
9. The file includes a function named maxGaussNorm of type [GaussianInt] -> GaussianInt that given a list of type GaussianInt returns the Gaussian integer with the largest norm. If given an empty list it simply returns 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 gaussConj, gaussAdd, gaussMult, gaussNorm, and maxGaussNorm. 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.
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 Gaussian integers.
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:
3

data GaussianInt a = a :@ a
deriving (Show,Eq)
class GaussianIntegral g where
gaussZero :: Integral a => g a
gaussReal :: Integral a => g a -> a gaussImag :: Integral a => g a -> a gaussConj :: Integral a => g a -> g a gaussAdd ::Integrala=>ga->ga->ga gaussMult :: Integral a => g a -> g a -> g a
4. Include a type class instance for GaussianIntegral GuassianInt
5. Import the Data.Complex module and include a type class instance
for GaussianIntegral Complex
6. The file includes a function named gaussNorm of type (Integral a, GaussianIntegral g) => g a -> a that implements the norm for any instance of GaussianIntegral.
7. The file includes a function named maxGaussNorm of type (Integral a, GaussianIntegral g) => [g a] -> [a] with the following defi- nition:
maxGaussNorm :: (Integral a, GaussianIntegral g)
=> [g a] -> g a
maxGaussNorm gs = foldr max gaussZero gs
8. The above definition will not compile without proper instances of Ord and Eq, so the file must contain them as well. (The implementations should be designed such that maxGaussNorm will behave semantically the same as the non-bonus portion.)
9. 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 gaussConj, gaussAdd, gaussMult, gaussNorm, and maxGaussNorm. The test plan must include at least three test cases for each function.
4