COMP 302 Programming Languages and Paradigms

Assignment 2

This assignment contains 4 questions; please do them all.

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 = <fun

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 = <fun

# 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 = <fun

# let rec remove(item, lst) = …

val remove : ’a * ’a list – ’a list = <fun

# 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 = <fun

# 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 = <fun

# 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