CMSC 330, Spring 2016
Organization of Programming Languages
Project 2b – OCaml higher order functions, and data
Update:
- Feb 21: .submit file is updated.
- reachable function is not extra credit. Deadline extended by one day.
Introduction
The goal of this project is to increase you familiar with programming in OCaml using higher order functions and user-defined types. You will have to write a total of 15 small functions, each of whose specification is given below. Some of them start out as code we provide you. In our reference solution, each function typically requires writing or modifying 5-8 lines of code, except for the last function, reachable, which is more involved.
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. Doing so will also prepare you for the quiz this Friday, and surely for the exam in just under two weeks’ time.
Getting Started
Download the following archive file p2b.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 – data.ml
- Extra functions you can use – funs.ml
- Test utilities – testUtils.ml
- Public tests
- Expected outputs for public tests
- Ruby script to run public tests- goTest.rb. Note that you will need to comment out line 20 and uncomment out either line 21 or 22 in this file, depending on which platform you are developing your code.
You may want to use functions from testUtils.ml for printing debugging messages, but your actual submission in data.ml should 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 testHigherOrder0.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. Versions of fold, fold_right, and map, as discussed in class, are in the file funs.ml.
Part 1: Higher order functions
Write the following functions using map, fold, or fold_right, as defined in the file funs.ml.
Name | Type | Return value | Example |
count_x x y | ‘a -> ‘a list -> int | how many times x occurs in y | count_x 3 [1;3;1;1;3] = 2 count_x “hello” [“there”;”ralph”] = 0 |
div_by_x x y | int -> int list -> bool list | a list of booleans, each one indicating whether the correponding element in y is divisible by x | div_by_x 2 [1;3;4;8;0] = [false;false;true;true;true] |
div_by_first y | int list -> bool list | a list of booleans, each one indicating whether the correponding element in y is divisible by the first element of y | div_by_first [2;3;4;8;0] = [true;false;true;true;true] div_by_first [] = [] |
pair_up x y | ‘a list -> ‘a list -> ‘a list list | a list of lists, where each element of x paired with each element of y | pairup [] [] = [] pairup [1;2] [3;4;5]= [[1; 3]; [1; 4]; [1; 5]; [2; 3]; [2; 4]; [2; 5]] |
concat_lists x | ‘a list list -> ‘a list | a list consisting of the lists in x concatenated together note just top level of lists is concatenated, unlike List.flatten |
concat_lists [[1;2];[7];[5;4;3]] = [1;2;7;5;4;3] concat_lists [[[1;2;3];[2]];[[7]]] = [[1;2;3];[2];[7]] |
Part 2: Binary trees using user-defined types
In this part, we provide you the starting point of an implementation on binary search trees whose nodes contain integers. First, we provide the type int_tree. According to its definition, an int_tree is either empty (just a leaf), or it is a node containing an integer, a left subtree, and a right subtree.
type int_tree = IntLeaf | IntNode of int * int_tree * int_tree
An empty tree is simply a leaf:
let empty_int_tree = IntLeaf
Binary trees are purely functional — just like lists, we never change a tree once we have created it. Rather, to “insert” an element into a tree, we create a new tree that is the same as the old one but for the added element. The insertion routine follows the standard algorithm for binary search trees.
Inserting x into tree t:
- if the tree is empty, then adding x produces a single-node tree
- if x is greater than the value at the current node, return a tree whose right subtree is replaced by the tree produced by inserting x into the current right subtree
- if x is already in the tree, then return the tree unchanged
- if x is less than the value at the current node, do the opposite of when x was greater (i.e., insert in the left subtree)
let rec int_insert x t = match t with IntLeaf -> IntNode(x,IntLeaf,IntLeaf) | IntNode (y,l,r) when x > y -> IntNode (y,l,int_insert x r) | IntNode (y,l,r) when x = y -> t | IntNode (y,l,r) -> IntNode(y,int_insert x l,r)
Checking whether an element is in a tree follows the same sort of procedure as insertion, but returns true if x is in the tree and false otherwise (rather than returning a different tree)
let rec int_mem x t = match t with IntLeaf -> false | IntNode (y,l,r) when x > y -> int_mem x r | IntNode (y,l,r) when x = y -> true | IntNode (y,l,r) -> int_mem x l
Note that we will use binary search trees to implement sets in part C of the project.
Implement the following functions, operating on trees:
Name | Type | Return value | Example |
int_size t | int_tree -> int | how many nodes are in the tree | int_size empty_int_tree = 0 int_size (int_insert 1 (int_insert 2 empty_int_tree)) = 2 |
int_to_list t | int_tree -> int list | a list of all values in the tree, resulting from an in-order traversal | int_to_list (int_insert 2 (int_insert 1 empty_int_tree)) = [1;2] int_to_list (int_insert 2 (int_insert 2 (int_insert 3 empty_int_tree))) = [2;3] |
int_insert_all xs t | int list -> int_tree -> int_tree | a tree t’ that is the same as t but has all integers in xs added to it | int_to_list (int_insert_all [1;2;3] empty_int_tree) = [1;2;3] Note: Try to use fold to implement this function on one line |
max_elem t | int_tree -> int | the maximum element in the tree or throws exception Failure "max_elem" for an empty tree |
max_elem (int_insert_all [1;2;3] empty_int_tree) = 3 Note: This should take time O(height of the tree) |
common t x y | int_tree -> int -> int -> int | the closest common ancestor of x and y in the int_tree. throws exception Failure "common" for an empty tree, or x,y does not exists | let t = int_insert_all [6;1;8;5;10;13;9;4] empty_int_tree;; common t 1 10 = 6 common t 8 9 = 8 |
The type int_tree only can contain integers. But we should be able to define a binary tree over any kind of data, as long as it is totally ordered. We capture this idea with the following data type definitions.
First we define the type 'a atree. Its definition is the same as int_tree but is polymorphic, since the node may contain a value of any type ‘a, not just ints.
type 'a atree = Leaf | Node of 'a * 'a atree * 'a atree
Since a tree may contain values of any type, we need a way to compare those values. For this purpose, we define the type of comparison functions: such functions take two values of type ‘a and return an int. If the returned value is negative, then the first value is less than the second; if positive, then the first is greater; if 0, then the two values are equal.
type 'a compfn = 'a -> 'a -> int
Finally: here is our definition of a polymorphic binary tree: This definition bundles the tree with its comparison function so that the latter can be used when needed by the tree’s functions, pinsert and pmem, below.
type 'a ptree = 'a compfn * 'a atree
Now, to define an empty tree you must also provide a comparison function.
let empty_ptree f : 'a ptree = (f,Leaf)
Now implement the following two functions. Start out by using the code from the insert and mem functions from int_trees but then modify it to use the ptree‘s bundled comparison function instead.
Name | Type | Return value | Example |
pinsert x t | ‘a -> ‘a ptree -> ‘a ptree | a tree t’ that is the same as t but has x added to it | See below |
pmem x t | ‘a -> ‘a ptree -> bool | whether x appears in tree t | See below |
Here is an example use of these two functions, together
let int_comp x y = if x < y then -1 else if x > y then 1 else 0;; let t0 = empty_ptree int_comp;; let t1 = pinsert 1 (pinsert 8 (pinsert 5 t0));; pmem 5 t0 = false;; pmem 5 t1 = true;; pmem 1 t1 = true;; pmem 2 t1 = false;;
You might find it useful to write a printing function for trees.
Part 3: Using Records to program graphs
The last part of the project asks that you implement some functions on graphs. We provide the data definition for a graph, which in part uses OCaml records.
Here are the type definitions. Here a graph is record with two fields; the first nodes keeps a a set of nodes, represented as an int_tree, and the second field edges keeps a list of edges. A node is represented as an int, and an edge is a record identifying its source and destination nodes.
type node = int;; type edge = { src: node; dst: node; };; type graph = { nodes: int_tree; edges: edge list };;
An empty graph has no nodes (i.e., the empty integer tree) and has no edges (the empty list).
let empty_graph = {nodes = empty_int_tree; edges = [] }
The function add_edge adds an edge to a graph. Its type is edge -> graph -> graph. Given an edge e and a graph g, it returns a new graph that is the same as g, but with e added. Note that this routine makes no attempt to eliminate duplicate edges; these could add some inefficiency but should not harm correctness.
let add_edge ({ src = s; dst = d } as e) { nodes = ns; edges = es } = let ns' = int_insert s ns in let ns'' = int_insert d ns' in let es' = e::es in { nodes = ns''; edges = es' }
Notice in the code above that the record pattern matching is taking place in the arguments of add_edge, rather than as a match statement. Also notice the pattern for the first argument, ({ src = s; dst = d } as e). This gives name e to that argument, and simultaneously matches it against the pattern { src = s; dst = d }, also binding variables s and d. As such, e, s, and d are all usable within the body of the function.
We also provide a function add_edges to add multiple edges at once.
Here are the functions you must implement:
Name | Type | Return value | Example |
is_empty g | graph -> bool | whether the graph g is empty | is_empty (add_edge { src = 1; dst = 2 } empty_graph) = false is_empty empty_graph = true |
num_nodes g | graph -> int | the number of nodes that appear in g | num_nodes (add_edge { src = 1; dst = 2 } empty_graph) = 2 num_nodes (add_edge { src = 1; dst = 1 } empty_graph) = 1 |
is_dst x e | node -> edge -> bool | true if x is the destination of the given edge | is_dst 1 { src = 1; dst = 2 } = false is_dst 2 { src = 1; dst = 2 } = true |
src_edges x e | node -> graph -> edge list | those edges in g whose source node is x | src_edges 1 (add_edges [{src=1;dst=2}; {src=1;dst=3}; {src=2;dst=2}] empty_graph) = [{src=1;dst=2}; {src=1;dst=3}] |
reachable n g | node -> graph -> int_tree | a set of nodes reachable from n, in g, where the set is represented as an int_tree | See below. |
Here are two examples for the operation of reachable:
int_to_list (reachable 1 (add_edges [{src=1;dst=2}; {src=1;dst=3}; {src=2;dst=2}] empty_graph)) = [1;2;3];; int_to_list (reachable 3 (add_edges [{src=1;dst=2}; {src=1;dst=3}; {src=2;dst=2}] empty_graph)) = [3];;
Submission
You can submit your project in two ways:
- Submit your data.ml file directly to the submit server by clicking on the submit link in the column “web submission”.
Next, use the submit dialog to submit your data.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 Jar or Zip file. Some students have mentioned problems with using Internet Explorer, because submissions being extracted in directories (e.g., “C:\My Documents\330\data.ml”) where the submit server could not find them. The problems went away when switching to the Mozilla Firefox browser.
- Submit directly by executing a Java program on a computer with Java and network access. Use the submit.jar file from the archive p2b.zip. To submit, go to the directory containing your project, then either execute submit.rb or type the following command directly:
java -jar submit.jar You will be asked to enter your class account and password, then all files in the directory (and its subdirectories) will be put in a jar file and submitted to the submit server. If your submission is successful you will see the message:Successful submission # received for project 2b