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

Write the following functions using map, fold, or fold_right, as defined in the file funs.ml.

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:

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

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.jarYou 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