
CMSC 330, fall 2016Organization of Programming LanguagesProject 2b  OCaml higher order functions, and data
IntroductionThe goal of this project is to increase you familiar with programming in OCaml using higher order functions and userdefined 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 58 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 StartedDownload 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:
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 functionsWrite the following functions using map, fold, or fold_right, as defined in the file funs.ml.
Part 2: Binary trees using userdefined typesIn 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:
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:
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.
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 graphsThe 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:
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];; SubmissionYou can submit your project in two ways:
Academic IntegrityThe Campus Senate has adopted a policy asking students to include the following statement on each assignment in every course: "I pledge on my honor that I have not given or received any unauthorized assistance on this assignment." Consequently your program is requested to contain this pledge in a comment near the top. 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 syllabusplease review it at this time. 