Homework 12 Haskell Assignment 2 Solution

Instructions for the homework submission:




You must use the literal haskell format (.lhs). You should submit ONE lhs file with all questions answered in the file. Name your file "Hw12.lhs".




As usual, this file should be wrapped in a tar.gz directory with your bmail name e.g. "eway1_Hw12.tar.gz".




Read these instructions:







This assignment has two parts. The first part you should do in lab, and it walks you through some concepts you need to do the rest of the assignment.




You will get credit for doing this part of the assignment by doing the quiz, linked on Blackboard. Each of the 3 questions is worth 5 points.




The second part is linked below, and on Blackboard. This part asks you to define several functions in Haskell.




Please download that file and put your function definitions directly in the file.

This is the file you will submit (wrapped in a .tar.gz).




PART 1 -- Lab




1. Functions of 1 variable -- Curried functions




In the development of functional notations as a model of computation, it has been important to concentrate on functions of one variable




Curry did considerable work in the area. The idea is often used today in mathematics.




Reference: WIKI -- Currying







Edit "Hw12Lab.lhs" again. Add a line with the comment, "Tuple Data Type", surrounded by a blank line . Add the following definition:



prodT (a,b,c) = a * b * c



Save and reload "Hw12Lab.lhs". Evaluate the following expressions: prodT(2,3,4), prodT(2, -3, 4). What is the inferred type of prodT?




Edit "Hw12Lab.lhs" again. Add a line with the comment, "Curried functions", surrounded by a blank line (lines 32-34). Add the following definition (line 35):



prodC a b c = a * b * c



Save and reload "Hw12Lab.lhs". Evaluate the following expressions: prodC 2 3 4. What



is the inferred type of prodC?

(At the prompt type: Hw12Lab :t prodC)




Edit "Hw12Lab.lhs" again. Add the following definition:






prodCx :: Num a = a - (a - (a-a))



prodCx a b c = a * b * c
Save and reload "Hw12Lab". Evaluate the following expression: prodCx 2 3 4.




At the prompt type:




Hw12Lab :t prodCx




to display the type inferred by Haskell. How does this compare to the inferred type of prodC?




Edit "Hw12Lab.lhs" again. Add the following definition:






prodC1 = prodC 1



prodC2 = prodC1 2



prodC3 = prodC2 3



prodC12 = prodC 1 2



Notice that each definition DOES NOT HAVE AN argument! Do you think this is legal or illegal? If the definition is legal, predict the type of each. Now save and reload to verify your hypothesis.




E. Assuming the code added in D is legal evaluate the following expression:







Hw12Lab prodC 1 2 3




Hw12Lab prodC1 2 3




Hw12Lab prodC2 3




Hw12Lab prodC3




prodC1, prodC2, prodC3 and prodC12 all include use partially evalutated functions in their definitions. Can you write similar definitions using prodT? For example are any of the following definitions legal?




prodT1 = prodT 1



prodT2 = prodT(1)



prodT4 = prodT(1,2)



prodT3 = prodT(1,x,y)



As you can see -- so far -- we are doing a lot of function application. Numbers are just constant functions. After completing up to this point, you should be able to figure out the associativity (right or left)of function application. Which parenthesize expression is the definition of F G H? Is it F G H = F ( G H) or is it F G H = ( F G ) H?



Composition : Composition is another way to "glue together" functions.



(References: Composition of Functions: and Function Composition (a deeper discussion))

A. Do this by hand -- Given:




f(x) = 3 - (x * 5)




g(x) = (x -1) * 2




Let h be defined to be (f o g) ( i.e h is f composed with g) . What is the result of h(x) ? Use the definition of f and g above.



Remember (f o g) x is defined to be f ( g(x) ).
Let h2 be defined to be ( g o f )? What is the result of h2(x) ?















What is the value of h(2 )?















d)What is the value of h2 (2 ) ?










Program h and h2 in Haskell



Write a haskell definition of f, g, h and h2. Use the composition operator (.) to define h and h2. Notice that composition operator returns a function and you do not need to include the argument x in your definition of h and h2. i.e. The left hand side of the definition for h (and h2) need only h =.....




Practice with data types:



Given the following types, state (in one sentence for each) what they describe.



Num a = a - a - a



Num a = a - (a - a)



Eq a = a - a - Bool



(a - b) - [a] - [b]



(a - b - a) - a - [b] - a



(a - a) - a - a



(b - c) - (a - b) - a - c



(a - Bool) - [a] - [a]



Given the following partially applied functions (all of which are valid) predict their type. Before jumping to :t, first check the type of the function un-applied. Then, try and figure out what the partially applied function must accept after the first argument is applied in order to type check. For example,



:t (+)




Num a = a - a - a




Then, (+) 1 removes one of the arguments (since it returns a new function). In order to type check, I should "expect" another a.




:t (+) 1




Num a = a - a




(+) 1



(+) 1 2



(.) (\x - x * 2)



(.) (\x - x * 2) abs



(.) (+)



(.) (+) (\m - 10 * m)



(.) (+) (\m - 10 * m) 3
Point is a data type that represents a point in a plane. Add the following definition to Hw12Lab.lhs.

data Point a = Pt a a deriving (Show, Eq)



Using deriving makes the type, Point a, in the Type Class Show and the class Eq using "a natural" implementation.




:t Pt 0 0




Pt 0 0 :: Num a = Point a




:t Pt 'a' 'b'




Pt 'a' 'b' :: Point Char




Pt 3 6 == Pt 6 3 False
Pt 3 6 == Pt 3 6 True



What is the data type name? What is the constructor name? What happens if you do not use deriving in the type declaration when you try to find if two points are equal?




PART 2--




Homework Problems: Hw12S19.lhs




Here is the information for last problem in the homework.




A common way to compute the square root is to use Newton's method of successive approximations. Newton's method says that whenever we have a guess y for the value of the square root of a number x, we can perform a simple manipulation to get a better guess (one closer to the actual square root) by averaging y with x/y. For example, we can compute the square root of 2 as follows. Suppose our initial guess is 1:









Guess Quotient Average
















1






















1.5






















1.4167
















1.4142 ... ...







Continuing this process, we obtain better and better approximations to the square root. " (From Structure and

Interpretation of Computer Programs by Abelson and Sussman).




Using a spreadsheet or calculator apply Newton's method to find the square root of 144 using an initial guess of 1. How do you know when to stop? How many steps did it take you?