Exercises

You're recommended to try out the following exercises using ghci, and building up a file e.g. lab.hs.

1. Give Haskell expressions to
   1. multiply 3.1416 and 4.7

   2. concatenate ``Hello '' and ``World''

   3. list the integers from -1000 to 24000

2. 1. Write a Haskell function sumTill :: Int -> Int, so that sumTill n calculates the sum of the numbers between 1 and (positive) n, e.g.

        sumTill 4  
      = 1 + 2 + 3 + 4
      = 10
      

   2. Show how sumTill 3 reduces to 6

3. Write a Haskell function fib :: Int -> Int, so that fib n calculates the fibonacci number for n. fib of 0 or 1 is 1, otherwise fib n = fib (n-1) + fib (n-2). Your function does not need to be efficient.

4. 1. Write a Haskell function prod:: [Int] -> Int, so that prod [x1, x2, .. xn] returns the product of the elements of the list: x1 * x2 * .. * xn

   2. Show how prod [3 .. 5] reduces to 60.

   3. Use a higher order function to write prodH, with the same semantics as prod.

   4. prod and prodH can only be applied to lists of Int. Write a function prodG (for Generic) to calculate products of lists of any numeric type. Hint: Num is the root of the numeric type class.

5. Write a Haskell function positive:: Int -> Bool, so that positive n is true if n is greater than 0, and false otherwise.

6. elem :: Eq a => a -> [a] -> Bool is a prelude function such that elem x xs is true if x occurs in the list xs, and false otherwise. Use elem and a list comprehension to write a Haskell function intersect :: Eq a => [a] -> [a] -> [a], so that intersect xs ys returns a list containing only those elements of xs that also appear in ys.

7. 1. Write a Haskell function powers:: Int -> [Int], so that powers n returns an infinite list $[n^{1},n^{2},n^{3}, ...]$
   2. Write a Haskell expression to return the first 5 powers of 3

8. The highest common factor (hcf), or greatest common divisor (gcd), of two numbers is the largest number that exactly divides them, e.g. the hcf of 60 and 84 is 12. Euclid proposed an algorithm for finding the hcf of two numbers big and small:

   if small exactly divides big
     return small
   else
     return hcf small (remainder of big/small)
   

   For example

     hcf 56 12
   = hcf 12 (rem 56 12)
   = hcf 12 8
   = hcf 8  4
   = 4
   

   Write a Haskell hcf :: Integer -> Integer -> Integer function.

9. Two numbers are relatively prime is their hcf is 1, e.g. 8 and 9 are relatively prime, but 6 and 9 are not. Write a Haskell function relprime :: Integer -> Integer -> Bool, that is true if it's arguments are relatively prime, but false otherwise.

10. The Euler totient (or phi) function euler n is a count of how many numbers less than n are relatively prime to n, e.g. euler 6 is 2 because 1 and 5 are relatively prime to 6. Write a Haskell function euler :: Integer -> Int that calculates the totient of it's argument.

11. Write a Haskell function sumTotient :: Integer -> Integer -> Int, so that sumTotient lower upper calculates the sum of the totients between lower and upper.

12. 1. Show that Java is a referentially opaque notation.
    2. Is the French language referentially transparent or opaque? Justify your answer.
    3. It is relatively easy to reason about referentially transparent notations like Haskell. Prove that in Haskell, if f x = x + 1, then
       2 * (f x) = (f x) + (f x)