Basics

1 atHome

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

2 inClass

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.

3 atHome

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)?

4 atHome

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.

5 inClass

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)

6 inClass

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

7 inClass

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))

8 atHome

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

9 inClass

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 (i.e. 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

10 atHome

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

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

11 atHome

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

12 atHome

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])?

13 inClass

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?

14 atHome

How can you query the interpreter (ghci) for the type of an expression?

15 atHome

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

16 atHome

Verify the types of the above expressions with the interpreter. If your answers differ, write down why you think that is the case. Discuss the answers with your class mates or with your TA.

17 inClass challenging

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)