Description
Q1 (a). [10 points] In this question you will write a program that takes two lists of the same
length and returns a single list with the items paired together. This will be used in later
questions in this assignment; we will need it with floating point items but your code should
be polymorphic. The snippet below shows the function name, which you must use, and
the type returned by the OCaml system. Your code must have this type.
# let rec pairlists twolists = …
val pairlists : ’a list * ’b list -> (’a * ’b) list =
We will forbid the use of the List.combine library function that does the same thing. Test
inputs are two int lists of the same length and we will check that you have handled the case
of empty input lists. Here is an example showing the right way and the wrong way to use
pairlists.
# let l1 = [1;2;3];;
val l1 : int list = [1; 2; 3]
# let l2 = [’a’;’b’;’c’];;
val l2 : char list = [’a’; ’b’; ’c’]
# let p1 = pairlists (l1,l2);;
val p1 : (int * char) list = [(1, ’a’); (2, ’b’); (3, ’c’)]
# let e1 = pairlists l1 l2;;
Characters 9-18:
let e1 = pairlists l1 l2;;
^^^^^^^^^
Error: This function has type ’a list * ’b list -> (’a * ’b) list
It is applied to too many arguments; maybe you forgot a ‘;’.
1
Q1 (b). [20 points] If (wi) is a sequence of weights and (vi) is a sequence of values we define
the weighted mean or average by the formula
mean =
P
P
i wi ∗ vi
i wi
.
In this question you are given two lists of floats as input. The first list is a list of weights and
the second is the list of values. Implement a function wmean which calculates the weighted
mean of the values with the given weights. Here is the declaration and the type that we
expect and an example of using it. Note the type and the way that the function is used.
# let wmean weights data = ….
val wmean : float list -> float list -> float =
# wmean [1.0;1.5;2.5;0.5;1.5] [10.3;11.7;2.0;5.0;6.5];;
– : float = 6.44285714285714217
In order to do this you are required to use your pairlists function from Q1(a) and the
sumlist function that we have provided. In this exercise we want you to learn to use the
List.map function from the library; you are not allowed to use let rec in this exercise.
We guarantee that we will not give you empty lists as test cases.
Q2. [20 points] This question involves two simple exercises in list manipulation. In the first
one you are given a pair: the first member of the pair is an item and the second member
is a list of items of the same type as the first member. The output is a boolean that says
whether the item is in the list or not. The second function takes a pair of an item and a
list and returns a list with the item removed. If the item is not in the list then the same
list is returned. You can use the first function in implementing the second but we are not
requiring you to do so.
Here are the declarations and types.
# let rec memberof pair = …
val memberof : ’a * ’a list -> bool =
# let rec remove(item, lst) = …
val remove : ’a * ’a list -> ’a list =
# remove (3, [1;6;3;2;6;1;7;2;3;5]);;
– : int list = [1; 6; 2; 6; 1; 7; 2; 5]
The lists may contain duplicates; all copies should be removed. Make sure that you deal
with empty lists. Here is an important style remark: never write if foo then true else
false; this should just be foo.
Q3. [20 points] In this question we want you to find the largest item in a list of integers. You
can assume that the lists are nonempty. The top level declaration is nonrecursive because
there is an internal recursive function.
2
# let find_max l = …
val find_max : ’a list -> ’a =
# find_max [1;6;3;2;6;1;7;2;3;5];;
– : int = 7
Q4. [30 points] In this question we want you to use find_max and remove to implement a
selection sort algorithm. You can assume that the list contains no duplicates.
# let rec selsort l =
val selsort : ’a list -> ’a list =
# selsort [1;4;2;5;3;9;6;8;7];;
– : int list = [9; 8; 7; 6; 5; 4; 3; 2; 1]
You are not allowed to use built-in sorting functions.
3
