Project - OCaml basics
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.
Part A: Simple functions
Write the following functions:
|
Name
|
Type
|
Return value
|
Example
|
|
mult_of_five x
|
int -> bool
|
true if x is a multiple of 5
false otherwise
|
mult_of_five 5 = true
mult_of_five 1 = false
|
|
sum_upto_three ls
|
int list -> int
|
the sum of the list's elements up to the first three
|
sum_upto_three [1] = 1
sum_upto_three [1;2;3] = 6
sum_upto_three [1;2;3;4;5] = 6
|
|
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 B: 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 C: 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
|
|
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]
|
|
is_sorted x
|
'a list -> bool
|
true if elements in x are in sorted order, false otherwise
return true for []
|
is_sorted [5;5;7;9] = true
is_sorted [9;7;5] = false
|
Attachment:- OCaml basics.rar