Latest update Dec. 19, 2022

Exercises

Functional Programming and F#

1. Define a function that converts the characters a, b, and c to capitals. All other characters should be returned unchanged. You are not allowed to use the standard F# method .ToUpper() on strings!

   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 strings. Again, you are not allowed to use the standard F# method .ToUpper() on strings.



2. Define a function squares n, which takes a nonnegative integer as argument and returns a list of the square numbers i*i for i from 1 to n! First write a version using direct recursion, then use F#'s range/sequence expressions.


3. Define a function that finds all matches of a nonempty sublist in a list. The function should return a list of booleans, with true in the positions where the sublist 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 list, and false otherwise.

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



4. List.foldBack and List.fold both require an initial element that is returned when the function is called with the empty list as list argument. If the folded function is a binary operator op, this element is most often a unit element w.r.t. the operator, i.e., an element u such that x op u = u op x = x for all x. Sometimes, however, there is no such natural element. It then makes sense to have versions of List.foldBack and List.fold that work only on nonempty lists. Define such versions of List.foldBack and List.fold!!


5. Consider the sequence, starting with the nonnegative whole number n, which is defined by the following three simple rules:
   • If the current number in the sequence is one, stop
   • If the current number k is odd, then next number is 3*k+1,
   • If the current number k is even, then next number is k/2,
   It is believed that for every n, the sequence eventually reaches one: nobody, however, has been able to prove it. But we can always investigate the validity of this hypothesis experimentally. Thus, define four different functions that test this in different ways:
   • A function that directly computes the next number in the sequence and recursively continues until it returns one.
   • A function that does the same, but in addition has an accumulating argument counting the number of recursive calls made.
   • Ditto, but with a reference cell instead of an accumulating argument for the counter.
   • Like the first function, but computing a list containing the whole sequence from n to 0.


6. 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.


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


8. 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.


9. Define a function sieve n that returns a list of all primes up to n! (Hint: one way to test if an integer i is a prime is to see if some prime less than i divides i evenly. If no such prime exists, then i is a prime. Apply this idea recursively.)


10. Consider the two functions f and g, defined thus:

    let f x y   = x + y
    let g (x,y) = x + y
    

    Explain the difference between f and g!


11. Define a data type for vectors of dimension two, three, four, and five! then define two functions on your new data type:
    1. a function vlen that computes the length of a vector, and
    2. a function vadd that adds two vectors.
    The vadd function should stop with an error message if an attempt is made to add vectors of different dimensionality.


12. For each node in a tree, its fanout is the number of subtrees below it (its number of "sons"). Trees with a fixed fanout, like binary trees, are easy to represent directly by recursive data types. For trees with varying fanout, where an internal node can have an arbitrary number of subtrees, one can use a recursive data type where the subtrees are stored in lists in the internal nodes. Now do the following:
    • Define a polymorphic data type for trees with varying fanout! Elements can be stored both in internal nodes and leaves. The nodes do not have to be sorted in any way.
    • Define a function treeMap f t, which maps the function f over all the nodes of the tree t.
    • Define a function that computes the average fanout of a tree.

Type Inference

1. Find the most general types for the functions f and g in assignment 10 above.


2. Find the most general type for map, defined by:

   let rec map f l =
     match l with
     | []           -> []
     | head :: tail -> f head :: map f tail
   



3. Find the most general type for take, defined by:

   let rec take n l =
     match (n,l) with
     (_,[])    -> failwith "List too short"
     (0,_)     -> []
     (_,x::xs) -> x :: take (n-1) xs
   

Solutions

Suggested solutions are available.