Introduction
The goal of this project is to get you familiar with programming in OCaml. You will have to write a number of small functions, each of whose specification is given below. In our reference solution, each function’s implementation is typically 3-6 lines of code; in a couple of cases you will want to write a helper function which will add another 3-6 lines.
This project is due in one week! We recommend you get started right away, going from top to bottom, and the problems get increasingly more challenging.
Getting Started
Download the following archive file p2a.zip and extract its contents.
Along with files used to make direct submissions to the submit server (submit.jar, .submit, submit.rb), you will find the following project files:
- Your OCaml program – basics.ml
- Ruby script to run public tests- test_all.rb. To run a specific test, read README.
You may want to use functions from testUtils.ml for printing debugging messages, but your actual submission in basics.mlshould not print any output nor should it depend on the testUtils.ml file in any way.
To run an individual test, you can type commands like ocaml testRecursion1.ml. The output from the test will be printed to the console. You should compare it to the corresponding .out to see if it is correct (this is what goTest.rb does).
Note that you must implement your functions with the exact parameter and return type specified, or else the submit server tests will fail.
For this project the only OCaml libraries you are allowed to use are those defined in the Pervasives module loaded by default. You are not allowed to use library functions found in any other modules, particularly List and Array.
Part 1: Simple functions
Write the following functions:
| Name | Type | Return value | Example |
| head_divisor l | int list -> bool | true if the head of the list divides the second element of the list false otherwise |
head_divisor [1;2] = true head_divisor [2;5] = false |
| tuple_addr t | int * int * int -> int | the sum of the tuple’s elements | tuple_addr (1,2,3) = 6 tuple_addr (-10,50,30) = 70 |
| caddr_int | int list -> int | the second element of the list -1 if the list has 0 or 1 elements |
caddr_int [1;2;3] = 2 caddr_int [1] = -1 |
Part 2: Simple Curried Functions
A curried function is one that takes multiple arguments “one at a time”. For example, the following function sub takes two arguments and computes their difference:
let sub x y = x - y
The type of this function is int -> int -> int. Technically, this says that sub is a function that takes an int and returns a function that takes another int and finally returns the answer, also an int. In other words, we could write
sub 2 1
and this will produce the answer 1. But we could also do something like this:
let f = sub 2 in f 1
and this will also produce 1. Notice how we call sub with only one argument, so it returns a function f that takes the second argument. In general, you can think of a function f of the type
t1 -> t2 -> t3 -> ... -> tn
as a function that takes n-1 arguments of types t1, t2, t3, …, tn-1 and produces a result of type tn. Such functions are written with OCaml syntax
let f a1 a2 a3 ... = body
where a1 has type t1, a2 has type t2, etc.Implement the following simple, curried functions:
| Name | Type | Return value | Example |
| mult_of_n x y | int -> int -> bool | whether x is a multiple of y | mult_of_n 5 5 = true mult_of_n 2 3 = false |
| triple_it x y z | ‘a -> ‘b -> ‘c -> ‘a*’b*’c | a tuple containing the three arguments, in order | triple_it 5 5 5 = (5,5,5) triple_it “hello” “b” “a” = (“hello”,”b”,”a”) |
| maxpair (x,y) (m,n) | ‘a*’b -> ‘a*’b -> ‘a*’b | (x,y) if it is larger than (m,n), according to lexicographic ordering (m,n) otherwise (see note about comparison functions below) |
maxpair (1,2) (3,4) = (3,4) maxpair (1,2) (1,3) = (1,3) |
The OCaml comparison functions (=,<=,>=,<, and >) are polymorphic, so you can give them any two arguments of the same type.
Part 3: Recursive Functions
The rest of the project asks that you implement a number of recursive functions, many of which compute on lists.
| Name | Type | Return value | Example |
| power_of x y | int -> int -> bool | returns true if y is a power of x false otherwise |
power_of 2 8 = true power_of 0 5 = false |
| prod l | int list -> int | the product of all elements in l 1 if l is empty |
prod [5;6] = 30 prod [0;5;3] = 0 |
| unzip l | (‘a*’b) list -> (‘a list)*(‘b list) | a pair of lists consisting of the all first and second elements, respectively, of the pairs in l | unzip [(1,2);(3,4)] = ([1;3],[2;4]) unzip [(3,7);(4,5);(6,9)] = ([3;4;6],[7;5;9]) |
| maxpairall l | (int*int) list -> int*int | the largest pair in input list l, according to lexicographic ordering (0,0) if l is empty |
maxpairall [(1,2);(3,4)] = (3,4) maxpairall [(1,2);(1,3);(0,0)] = (1,3) |
| addTail l x | ‘a list -> ‘a -> ‘a list | a new list where x is appended to the end of l | addTail [1;2] 3 = [1;2;3] |
| get_val x n | int list -> int -> int | element of list x at index n (indexes start at 0) -1 if n is outside the bounds of the list |
get_val [5;6;7;3] 1 = 6 get_val [5;6;7;3] 4 = -1 |
| get_vals x y | int list -> int list -> int list | list of elements of list x at indexes in list y, -1 for any indexes in y are outside the bounds of x (as with get_vals) elements must be returned in order listed in y |
get_vals [5;6;7;3] [2;0] = [7;5] get_vals [5;6;7;3] [2;4] = [7;-1] |
| list_swap_val b u v | ‘a list -> ‘a -> ‘a -> ‘a list | list b with values u,v swapped change value of multiple occurrences of u and/or v, if found change value for u even if v not found in list, and vice versa |
list_swap_val [5;6;7;3] 7 5 = [7;6;5;3] list_swap_val [5;6;3] 7 5 = [7;6;3] |
| index x v | ‘a list -> ‘a -> int | index of rightmost occurrence of value v in list x (indexes start at 0) -1 if not found |
index [1;2;2] 1 = 0 index [1;2;2;3] 2 = 2 index [1;2;3] 5 = -1 |
| distinct l | ‘a list -> ‘a list | a new list that contains the distinct elements of l, in the same order they appear in l | distinct [1;2;2] = [1;2] distinct [2;1;2;2;3] = [2;1;3] |
| find_new x y | ‘a list -> ‘a list -> ‘a list | list of members of list x not found in list y maintain relative order of elements in result |
find_new [4;3;7] [5;6;5;3] = [4;7] find_new [5;6;5;3] [4;3;7] = [5;6;5] |
| power_list l | int list -> bool | true if each consecutive element is a power of the previous, false otherwise return true for [] |
power_list [3;9;81] = true power_list [9;7;5] = false |
Submission
You can submit your project in two ways:
- Submit your basics.ml file directly to the submit server by clicking on the submit link in the column “web submission”.