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.zipand extract its contents.
Along with files used to make direct submissions to the submit server (submit.jar, .submitsubmit.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.mlfor printing debugging messages, but your actual submission in data.mlshould not print any output nor should it depend on the testUtils.mlfile 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 .outto see if it is correct (this is what goTest.rbdoes).
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 Pervasivesmodule loaded by default. You are not allowed to use library functions found in any other modules, particularly Listand 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_treeis 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 withIntLeaf -> 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 withIntLeaf -> 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_treeonly 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_treebut 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 insertand memfunctions from int_treesbut 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 graphis record with two fields; the first nodeskeeps a a set of nodes, represented as an int_tree, and the second field edgeskeeps 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_edgeadds 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 inlet ns'' = int_insert d ns' inlet 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 matchstatement. 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_edgesto 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];;
Reviews
There are no reviews yet.