Basics

Recommended: Writing functions 2-4, 6 Challenging: Implementing (an approximate) Square Root

Syntax

How do x = 3 and x == 3 differ in meaning?

Evaluation

1. Given the following definitions:

   thrice x = [x, x, x]
   
   sums (x : y : ys) = x : sums (x + y : ys)
   sums xs           = xs

   What does the expression map thrice (sums [0 .. 4]) evaluate to? Write down the intermediate steps of your computation.

2. A recursive function is only sensible if the value(s) of its parameters becomes simpler in each recursive application. Consider the following definition of the factorial function:

   fac n | n == 0 = 1
         | otherwise = n * fac (n − 1)

   What happens if you evaluate fac (−3)?

Writing Functions

1. Write a function noOfSol that, for some \(a\), \(b\), and \(c\), determines the number of solutions of the equation \(ax^2 + bx + c = 0\), using case distinction.

2. Write a function pow2 :: Int -> Int that takes an Int \(n\) computes \(2^n\) using direct recursion.

   pow2   :: Int -> Int
   pow2 0 = 1
   pow2 n = 2 * pow2 (n - 1)

3. Write a recursive function pow that takes two Ints, \(x\) and \(n\), and computes \(x^n\).

4. For any number \(x\), and any even number \(n\) it holds that \(x^n = (x^{n/2})^2\). Use this to speed up the implementation of the pow function.

   pow       :: Int -> Int -> Int
   x `pow` 0 = 1
   x `pow` n | even n    = let y = x `pow` (n `div` 2) in y * y
             | otherwise = x  * (x `pow` (n-1))

5. Which intermediate results are being computed for the computation of 2 `pow` 10 in the old and the new definition?

6. A predicate p :: Int -> Bool is monotonic if, for any Int i for which the predicate holds (p i == True) the predicate also holds for any index j larger than i (p j is also True).

   Given:

   • a monotonic predicate p,
   • a lowerbound l :: Int for which p l == False, and
   • an upperbound u :: Int for which p u == True,

   implement a function binarySearch that can find the smallest Int i for which p i is True in \(O(\log (u - l))\) steps.

   Also give the type of your function.

   binarySearch                    :: (Int -> Bool) -> Int -> Int -> Int
   binarySearch p l u | u - l == 1 = u
                      | p h        = binarySearch p l h
                      | otherwise  = binarySearch p h u
     where
       h = (l + u) `div` 2
   

7. Give the most general type for the function binarySearch you defined above.

   binarySearch                    :: Integral i => (i -> Bool) -> i -> i -> i

Basic Types

1. Determine the types of 3, even, and even 3. How can you figure out the latter?

2. Determine also the type of head, [1,2,3], and head [1,2,3]. What happens when applying a polymorphic function (like head) to monomorphic arguments (like [1,2,3])?

3. Write down what you think the type of the following functions is. Do not use the interpreter (yet): tail, length, noOfSol, pow2, div, (/), and sqrt?

4. How can you query the interpreter for the type of an expression?

5. How can you explicitly specify the types of functions in your program?

6. Verify the types of the above expressions with the interpreter. If your answers differ, write down why you think that is the case.

Implementing (an approximate) Square Root

In this (set of) exercises we will write our own implementation of the square root function. More precisely, we write a function approxSqrt that can approximate \(\sqrt x\) for any value \(x\).

Consider the following two facts about the square root:

1. if \(y\) is a good approximation of \(\sqrt{x}\) then \((1/2)(y+x/y)\) is a better approximation.
2. \(1\) is a (not-so) good approximation of \(\sqrt{x}\)

We will say that the approximation of \(\sqrt{x}\) is good enough when \(y^2\) is close to \(x\). More specifically, when \(|y^2 - x|\) is at most some threshold \(\varepsilon\).

1. Use the above two facts to implement a function approxSqrt :: Double -> Double -> Double so that approxSqrt eps x returns a value \(y\) that is a good enough (with respect to the given threshold eps).

   Hint: use an recursive helper function.

   approxSqrt       :: Double -> Double -> Double
   approxSqrt eps x = go 1
     where
       go y = let y' = 0.5 * (y + x/y)
              in if goodEnough y then y' else go y'
   
       goodEnough y = abs (y*y - x) < eps

2. write an alternative implementation of approxSqrt using the following function until :: (a -> Bool) -> (a -> a) -> a -> a which takes care of the actual iteration/recursion.

   until stop f s | stop s    = s
                  | otherwise = until stop f (f s)

   Starting with the value s, until stop f s repeatedly applies the function f to get some new value until the predicate stop returns True. Here are some examples:

   >>> let double x = 2*x in until (>1000) double 1
   1024
   >>> let double x = 2*x in until (>0) double 1
   1

   approxSqrt       :: Double -> Double -> Double
   approxSqrt eps x = until goodEnough refine 1
     where
       goodEnough y = abs (y*y - x) < eps
       refine y     = 0.5 * (y + x/y)

3. Maybe we don’t know in advance yet when the approximation is “good enough”, and instead we just want a list of ever more precise approximations of \(\sqrt{x}\). Write a function approxSqrts :: Double -> [Double] that produces such a list.

   approxSqrts   :: Double -> [Double]
   approxSqrts x = go 1
     where
       go y = y : go (0.5 * (y + x/y))
   
   -- or using the prelude function 'iterate':
   approxSqrts'   :: Double -> [Double]
   approxSqrts' x = iterate refine 1
     where
       refine y = 0.5 * (y + x/y)