Project 2b - OCaml higher order functions, and data

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

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
  • testHigherOrder0.ml
  • testHigherOrder1.ml
  • testIntTree.ml
  • testpTree.ml
  • testCommon1.ml
  • testCommon2.ml
  • testGraph1.ml
  • testGraph2.ml
  • testReachable.ml
• Expected outputs for public tests
  • testHigherOrder0.out
  • testHigherOrder1.out
  • testIntTree.out
  • testpTree.out
  • testCommon1.out
  • testCommon2.out
  • testGraph1.out
  • testGraph2.out
  • testReachable.out
• 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

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)

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;;

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

• 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

Academic Integrity

The 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 syllabus---please review it at this time.