Homework 13 Haskell Assignment 3 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 "Hw13S19.lhs" or you can add to this file."Hw13S19.lhs". As usual, this file should be wrapped in a tar.gz directory with your bmail name e.g.




"eway1_Hw13S19.tar.gz".




Define a data type Point that represents a point in a plane and the coordinate values should be polymorphic. The constructor for Point should be Pt. You should include "deriving (Show, Eq)" in your data type definition. What is the purpose of including "deriving"?



Write a Haskell function "inside point r " which returns true if and only if the point lies inside a circle of radius r and false otherwise.



"inside" can be defined as:




inside r point (x, y) is true if and only if x*x + y*y < r*r where x and y are the coordinates of the point.




Your Haskell code should not be using tuples. If your constructor for Point is Pt, then to execute you type:




... inside 10.0 (Pt 3.0 2.5)




True




... inside 10.0 (Pt (-1) (-2))




True




... inside 2.0 (Pt 3.0 2.5)




False







This problem are related to tail recursion. power is a function which raises a number n to the power p. Here is a very simple implementation.



power :: Integer - Integer - Integer



power n 0 = 1



power n p = a * power n (p-1)



Show the steps in the evaluation of the expression power 2 5, making sure not to reduce any subexpression prematurely. How do the time and maximum space required by the evaluation of power n k depend on n and p? What is the time complexity of power?



Because of lazy evaluation, the definition of power accumulates of pending multiplications. It is inherent in the way power is defined— each multiplication has to wait until its right argument has been evaluated. One way to eliminate the multiplication delay is to convert the function’s definition to a tail-recursive implementation:



powerT :: Integer - Integer - Integer



powerT n p = trp p 1



where



trp p' acc = if (p' == 0) then acc else trp (p'-1) (n*acc)



Show the steps in the evaluation of the expression powerT 2 5, making sure not to reduce any subexpression prematurely. What is the time complexity of powerT?

C Here is an algorithm that improves time and space




turboPower a 0 = 1



turboPower a b



| even b = turboPower (a*a) (b `div` 2)



| otherwise = a * turboPower a (b-1)



Instead of merely decrementing its first argument, this algorithm halves it whenever it is even, thereby reaching termination much more quickly. What is the complexity of this algorithm?




Convert turboPower to a tail recursive version -- call you new version turboPowerT. You can follow the pattern used in part b. What is the complexity of this algorithm?



The Tree data type defined below is used to build a binary tree.



data Tree a = Nil



| Node a (Tree a) (Tree a) deriving Eq




Below is an is an implementation of a pretty Tree print .







instance Show a = Show (Tree a) where



show t = show' t 0



where



show' Nil ind = replicate ind ' ' ++ "Nil"



show' (Node v l r) ind =



replicate ind ' ' ++ "(Node " ++ show v ++ "\n" ++



show' l (ind+1) ++ "\n" ++



show' r (ind+1) ++ "\n" ++



replicate ind ' ' ++ ")"









What are Tree, Nil and Node?




I have also provided a few default binary trees so you do not need to keep entering them into ghci. You may simply type tree1 at the prompt and you will get a pretty print of tree1. Note these 3 examples are in fact binary search trees.




tree1 = Node 5 (Node 10 Nil (Node 12 Nil Nil) ) Nil



tree2 = (Node 5 (Node 2 (Node 1 Nil Nil) (Node 3 Nil Nil)) (Node 7 Nil (Node



9 Nil Nil)))




tree3 = (Node 5 (Node 2 (Node 1 Nil Nil) Nil) (Node 7 Nil (Node 9 Nil Nil)))









Define "flatten t" which converts a tree to a list. You should do an inorder traversal of the tree. You may use "++" operator. What are your assumptions? Can you predict type inferred of flatten ?







... flatten tree1



[10,12,5]










5. The harmonic series is the following infinite series:




1
1
1
1
1
1 + - + - + - + - + ... + ...
- ...
2
3
4
5
i
(http://en.wikipedia.org/wiki/Harmonic_series_(mathematics))




Write a function sumHarmonic such that sumHarmonic i is the sum of the first in




terms of this series. For example, sumHarmonic 4 ~ 1 + 1/2 + 1/3 + 1/4 ~ 2.08333...




Your definition should use a simple recursive style.




(from Thue-Morse sequence )



"In mathematics, the Thue-Morse sequence, or Prouhet-Thue-Morse sequence, is a binary sequence that begins:




0 01 0110 01101001 0110100110010110 01101001100101101001011001101001 ...




(or if the sequence started with 1...)




1 10 1001 10010110 1001011001101001 ...




"Characterization using bitwise negation




The Thue–Morse sequence in the form given above, as a sequence of bits, can be defined recursively using the operation of bitwise negation. So, the first element is 0.




Then once the first 2n elements have been specified, forming a string s, then the next 2n elements must form the bitwise negation of s. Now we have defined the first 2n+1 elements, and we recurse.




Spelling out the first few steps in detail:




We start with 0.



The bitwise negation of 0 is 1.



Combining these, the first 2 elements are 01.



The bitwise negation of 01 is 10.



Combining these, the first 4 elements are 0110.



The bitwise negation of 0110 is 1001.



Combining these, the first 8 elements are 01101001.



And so on.



T0 = 0



T1 = 01



T2 = 0110



...




Define a primitive recursive function 'thue' given the nth thue element returns the next thue element. The elements will be represented as a list of 0s and 1s.

Example:




... thue [0,1,1,0]

[0,1,1,0,1,0,0,1]




Define a function replicate' which given a list of numbers returns a



list with each number duplicated its value. The ' is not a typo - this is to avoid the existing replicate.




Use primitive recursion in your definition. You may use a nested helper definition. Example:




... replicate' [2, 4, 1] [2,2,4,4,4,4,1]