Project 2A: OCaml Warmup
CMSC 330, Fall 2017 Due Friday, September 22nd, 2017
Ground Rules
This is NOT a pair project. You must work on this project alone as with most other CS projects. See the Academic Integrity section for more information.
In your code, you may only use library functions found in the Pervasives
module . You may not use any imperative structures of OCaml such as references. The @ operator is NOT allowed.
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 which is specified in three sections below. In our reference solution, each functions implementation is typically 3-6 lines of code, requiring no use of inner let bindings.
This project is due in one week! We recommend you get started right away, going from top to bottom. The problems get increasingly more challenging, and in many cases later problems can take advantage of earlier solutions.
Project Files
To begin this project, you will need to commit any uncommitted changes to your local branch and pull updates from the git repository. Click here for directions on working with the Git repository. The following are the relevant files:
<! TODO add the real files to the document and ensure that theyre correct >
- OCaml Files
- basics.ml : This is where you will write your code for all parts of the project.
- basics.mli : This file is used to describe the signature of all the functions in the module. Dont worry about this file, but make sure it exists or your code will not compile.
- public.ml : This file contains all of the public test cases.
- Submission Scripts and Other Files
- submit.rb : Execute this script to submit your project to the submit server.
- submit.jar and .submit : Dont worry about these files, but make sure you have them.
- Makefile : This is used to build the public tests by simply running the command
make
, just as in 216.
Notes on P2A and OCaml
OCaml is a lot different than languages youre likely used to working with, and wed like to point out a few quirks here that may help you work your way out of common issues with the language. <!TODO flesh out this section >
- This project is additive in many ways your solutions to earlier functions can be used to aid in writing later functions.
- Unlike most other languages, = in OCaml is the operator for structural equality whereas == is the operator for physical equality. All functions in this project (and in this class, unless ever specified otherwise) are concerned with structural equality.
- The subtraction operator (-) also doubles as the negative symbol for
int
s andfloat
s in OCaml. As a result, the parser has trouble identifying the difference between subtraction and a negative number. When writing negative numbers, surround them in parentheses. (i.e.some_function 5 (-10)
works, butsome_function 5 -10
will give an error)
In order to compile your project, simply run the make
command and our Makefile
will handle the compilation process for you, just as in 216. After compiling your code, the public tests can be run by running public.native
(i.e. ./public.native
; think of this just like with a.out in C)
Part 1: Simple Functions
Implement the following simple functions. No recursion is needed.
mult_of_y x y
- Type :
int -> int -> bool
- Description : Returns
true
ifx
is a multiple ofy
,false
otherwise. - Examples:
mult_of_y 5 10 = false mult_of_y 0 10 = truemult_of_y 15 0 = falsemult_of_y 10 10 = truemult_of_y 20 10 = true
head_divisor lst
- Type :
int list -> bool
- Description : Returns true if the second element of
lst
divides the head oflst
, false otherwise. - Examples:
head_divisor [] = falsehead_divisor [1] = falsehead_divisor [10; 5] = truehead_divisor [4; 2; 7] = truehead_divisor [9; 18] = false
second_element lst
- Type :
int list -> int
- Description : Returns the second element of
lst
, or -1 iflst
has less than 2 elements. - Examples:
second_element [] = -1second_element [1] = -1second_element [4; 2] = 2second_element [4; 6; 9] = 6
sum_first_three lst
- Type :
int list -> int
- Description : Returns the sum of the first three elements of
lst
, or the sum of all elements iflst
has less than 3 elements. - Examples:
sum_first_three [] = 0sum_first_three [5] = 5sum_first_three [5; 6] = 11sum_first_three [4; -3; 0] = 1sum_first_three [1; 1; 1; 7] = 3
Part 2: Recursive List Functions
The following list functions will require recursion to complete. Include the rec
keyword in your function definition to make use of recursion or you will get an unbound value error.
get_val i lst
- Type :
int -> int list -> int
- Description : Returns the element at index
i
(0-indexed) oflst
, or -1 ifi
is not a valid index forlst
. - Examples:
get_val 1 [5;6;7;3] = 6 get_val 4 [5;6;7;3] = -1get_val (-1) [6;5;7;8] = -1
get_vals is lst
- Type :
int list -> int list -> int list
- Description : Returns a list where the values correspond to the items found at each index of
lst
listed inis
, or -1 for each out of bound index. - Examples:
get_vals [2;0] [5;6;7;3] = [7;5] get_vals [2;4] [5;6;7;3] = [7;-1]get_vals [] [5;6;7;3] = []
list_swap_val lst x y
- Type :
'a list -> 'a -> 'a -> 'a list
- Description : Returns
lst
but with each instance ofx
replaced withy
and vice versa. - Examples:
list_swap_val ['a';'a';'b';'c';'d'] 'a' 'd' = ['d';'d';'b';'c';'a']list_swap_val [5;6;3] 7 5 = [7;6;3]list_swap_val [3;2;1] 8 9 = [3;2;1]list_swap_val [] 5 7 = []
unzip lst
- Type :
('a * 'b) list -> 'a list * 'b list
- Description : Given a list of pairs, returns a pair of lists with the elements in the same order.
- Examples:
unzip [(1,2);(3,4)] = ([1;3], [2;4])unzip [] = ([], [])
index x lst
- Type :
'a -> 'a list -> int
- Description : Returns the leftmost index (0-indexed) of element
x
inlst
, or -1 if no occurrence is found. - Examples:
index 1 [1;2] = 0 index "bat" ["apple";"bat";"bat";"door"] = 1index 5 [1;2;3] = -1
Part 3: Set Implementation using Lists
For this part of the project, you will get some real-world practice implementing one part of the OCaml standard library sets! In practice, sets are implemented using data structures like balanced binary trees or hash tables. However, your implementation must represent sets using lists. While lists dont lend themselves to the most efficient possible implementation, they are much easier to work with.
For this project, we assume that sets are unordered, homogeneous collections of objects without duplicates. The homogeneity condition ensures that sets can be represented by OCaml lists, which are homogeneous. The only further assumptions we make about your implementation are that the empty list represents the empty set, and that it obeys the standard laws of set theory. For example, if we insert an element x
into a set a
, then ask whether x
is an element of a
, your implementation should answer affirmatively. If we take the intersection of two disjoint sets a
and b
, then ask whether any member of a
or b
is a member of the intersection, your implementation should answer negatively.
Finally, note the difference between a collection and its implementation. Although sets are unordered and contain no duplicates, your implementation may be ordered or contain duplicates. However, there should be no observable difference between an implementation that maintains uniqueness of elements and one that does not; or an implementation that maintains elements in sorted order and one that does not.
insert x a
- Type :
'a -> 'a list -> 'a list
- Description : Inserts
x
into the seta
. - Examples:
insert 2 []insert 3 (insert 2 [])insert 3 (insert 3 (insert 2 []))
eq a b
- Type :
'a list -> 'a list -> bool
- Description : Returns true iff
a
andb
are equal as sets i.e.,x
is an element ofa
iffx
is an element ofb
. - Examples:
eq [] (insert 2 []) = falseeq (insert 2 (insert 3 [])) (insert 3 []) = falseeq (insert 3 (insert 2 [])) (insert 2 (insert 3 [])) = true
card a
- Type :
'a list -> int
- Description : Returns the cardinality of the set
a
i.e., the number of elements in the set. - Examples:
card [] = 0card (insert 2 (insert 2 [])) = 1card (insert 2 (insert 3 [])) = 2
elem x a
- Type :
'a -> 'a list -> bool
- Description : Returns true iff
x
is an element of the seta
. - Examples:
elem 2 [] = falseelem 3 (insert 5 (insert 3 (insert 2 []))) = trueelem 4 (insert 3 (insert 2 (insert 5 []))) = false
remove x a
- Type :
'a -> 'a list -> 'a list
- Description : Removes
x
from the seta
. - Examples:
card (remove 3 (insert 5 (insert 3 []))) = 1elem 3 (remove 3 (insert 2 (insert 3 []))) = falseeq (remove 3 (insert 5 (insert 3 []))) (insert 5 []) = true
union a b
- Type :
'a list -> 'a list -> 'a list
- Description : Returns the union of the sets
a
andb
i.e.,x
is an element ofunion a b
iffx
is an element ofa
orx
is an element ofb
. - Examples:
eq (union [] (insert 2 (insert 3 []))) (insert 3 (insert 2 [])) = trueeq (union (insert 5 (insert 2 [])) (insert 2 (insert 5 (insert 3 [])))) (insert 3 (insert 2 (insert 5 []))) = trueeq (union (insert 2 (insert 7 [])) (insert 3 (insert 5 []))) (insert 5 (insert 3 (insert 7 (insert 2 [])))) = true
intersection a b
- Type :
'a list -> 'a list -> 'a list
- Description : Returns the intersection of sets
a
andb
i.e.,x
is an element ofintersection a b
iffx
is an element ofa
andx
is an element ofb
. - Examples:
eq (intersection (insert 3 (insert 5 (insert 2 []))) []) [] = trueeq (intersection (insert 5 (insert 7 (insert 3 (insert 2 [])))) (insert 6 (insert 4 []))) [] = trueeq (intersection (insert 3 (insert 5 (insert 2 []))) (insert 4 (insert 3 (insert 5 [])))) (insert 5 (insert 3 [])) = true
subset a b
- Type :
'a list -> 'a list -> bool
- Description : Return true iff
a
is a subset ofb
i.e.,x
is an element ofa
impliesx
is an element ofb
. - Examples:
subset (insert 2 (insert 4 [])) [] = falsesubset (insert 5 (insert 3 [])) (insert 3 (insert 5 (insert 2 []))) = truesubset (insert 5 (insert 3 (insert 2 []))) (insert 5 (insert 3 [])) = false
Project Submission
<! TODO add filename > You should submit a file basics.ml
containing your solution. You may submit other files, but they will be ignored during grading. We will run your solution as individual OUnit tests just as in the provided public test file.
Be sure to follow the project description exactly! Your solution will be graded automatically, so any deviation from the specification will result in lost points.
You can submit your project in two ways:
- Submit your
basics.ml
file directly to the submit serverby clicking on the submit link in the column web submission. Then, use the submit dialog to submit yourbasics.ml
file directly. Select your file using the Browse button, then press the Submit project! button. You do not need to put it in a zip file. - Submit directly by executing a the submission script on a computer with Java and network access. Included in this project are the submission scripts and related files listed under Project Files . These files should be in the directory containing your project. From there you can either execute submit.rb or run the command
java -jar submit.jar
directly (this is all submit.rb does).
No matter how you choose to submit your project, make sure that your submission is received by checking the submit server after submitting.
Academic Integrity
Please carefully read the academic honesty section of the course syllabus. Any evidence of impermissible cooperation on projects, use of disallowed materials or resources, or unauthorized use of computer accounts, will be submitted to the Student Honor Council, which could result in an XF for the course, or suspension or expulsion from the University. Be sure you understand what you are and what you are not permitted to do in regards to academic integrity when it comes to project assignments. These policies apply to all students, and the Student Honor Council does not consider lack of knowledge of the policies to be a defense for violating them. Full information is found in the course syllabus, which you should review before starting.
<! Link References >
<! These should always be left alone or at least updated >
Reviews
There are no reviews yet.