Exercises

These exercises are to provide you with some training for the written exam. Questions on the exam can be expected to be quite similar to these (but there will be fewer of them).

Functional Programming and Haskell

Define a function that converts the letters a, b, and c to capitals. All other characters should be returned unchanged. You are not allowed to use the standard Haskell function toUpper.

Then, write a function to convert all occurrences of a, b, and c in a string to capitals! Write both a version that uses direct recursion, and a version that uses some appropriate higher-order function on lists.

Define a function that finds all matches of a nonempty substring in a string. The function should return a list of booleans, with True in the positions where the substring starts and False in all other positions. Also give the type signature of the function.

Then define a function that returns True if any match is found anywhere in the string, and False otherwise.

You don't have to use any sophisticated string matching algorithm, a straightforward one suffices.

Define a function to calculate the square root of a number, to some given accuracy, using Newton-Raphson's method. For the square root function, this method replaces a guess x of the square root of a with 0.5*(x + a/x). Break the iteration when the difference between two successive iterates is less than the specified accuracy.

Now write a higher order function, which given a function f, its derivative f', initial guess, and accuracy, computes a numerical solution to the equation f(x) = 0 by the general version of Newton-Raphson's method, which computes a new guess x(n+1) from old guess x(n) according to x(n+1) = x(n) - f(x(n))/f'(x(n)).

Now abstract out the underlying computing structure even more: write a general, higher-order function for iterative algorithms that iterates a solution by applying a function until a convergence criterion is fulfilled. The convergence criterion should also be a parameter. Reimplement Newton-Raphson's method by calling this function with appropriate parameters.

Are the following two expressions equivalent? Motivate your answer!
1. foldr (\ x y -> f x + y) 0 xs
2. foldr ((+) . f) 0 xs

Define the infinite list of all primes! (Hint: implement a version of Erathosthenes' sieve, that traverses the positive integers from one and up and for every new prime checks, for each larger integer, whether it is a multiple of that prime or not. An integer that is not the multiple of any prime is a prime itself.)

Give a definition of a multiplication function mult :: Int -> Int -> Int such that mult 0 bot evaluates to 0, where bot is defined as
```
bot = bot
```
What is mult bot 0? Explain why it is so.

What would the result of mult 0 bot be in an eager language? Explain why.

Undefined values in a type a can be represented by the element Nothing in Maybe a. For instance, we can use this for numerical types to let errors propagate through the computation without interrupting the calculation. To do this conveniently, one must overload the numerical operators so they work also on values of type Maybe a, provided they are defined over a. Provide an instance declaration for Num that accomplishes this!

Consider the two functions f and g, defined thus:
```
f x y   = x + y
g (x,y) = x + y
```
Explain the difference between f and g!

Define a class Point with a method distance, returning the distance between two points as a floating-point number. Then define a type Point2 a for two-dimensional points with coordinate type Float and make it an instance of Point, where its instance of distance yields the Euclidean distance between two points in 2D space.

Define a class Measurable with a method size, that gives a reasonable estimate of the size of a datum of the instance type. Define a number of instances, ranging from simple type (Bool, Int,Integer,...) to more complex and polymorphic types such as [a], (a,b) etc.

Lambda Calculus and Type Inference

Find the most general type for length, defined by:
```
length []     = 0
length (_:xs) = 1 + length xs
```
You don't have to worry about type classes: assume that the constants have type Integer, and that + operates on values of this type as well. Also, you don't have to make a fully formal derivation using the Hindley-Milner inference rules, but your solution should be systematic enough to display that you have a basic understanding of type inference.

Reduce the lambda expression (in Haskell syntax)
```
(\z->(\x->(z x) z)) (x \x->(x x))
```
in all ways possible! Will all reductions terminate? What results do you get for the terminating reductions?

Exercises

Functional Programming and Haskell

Lambda Calculus and Type Inference

Solutions