Latest update Dec 8, 2009
To prevent spambots from collecting mail addresses, all mail addresses on
this page have the "@" replaced by "#".
Functional Programming and F#
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.
- 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.
- 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.
- 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!!
- Consider the sequence, starting with the nonnegative whole
number n, which is defined by the following three simple rules:
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:
- If the current number in the sequence is one, stop
- If the current number k is odd, then next number
- If the current number k is even, then next number
- 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 reciursive 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.
- 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
- 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
- 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
- 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!
- Define a data type for vectors of dimension two, three, four, and five!
then define two functions on your new data type:
The vadd function should stop with an error message if an attempt
is made to add vectors of different dimensionality.
- a function vlen that computes the length of a vector,
- a function vadd that adds two vectors.
- 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.
Find the most general types for the functions f and g in
assignment 10 above.
- Find the most general type for map, defined by:
let rec map f l =
match l with
|  -> 
| head :: tail -> f head :: map f tail
- 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
Suggested solutions are