75 Points
Due: Wednesday, 11/29/00 at 5:00PM

Problem: Rooted Trees in SML

In this programming assignment, you will implement a data type for rooted trees in SML, as well as some associated functions. Recall that, mathematically, a rooted tree T is a directed graph, with a distinguished node r, such that every node in T is reachable from the root by a unique path. You are to define an SML data type rooted_tree to represent a rooted tree. In addition to representing a rooted tree, the rooted_tree data type must be a parameterized type in which every node in the tree must have a label 'a of the same type. If a node in a rooted tree has 2 or more children, then its children must have a fixed order from left-to-right. You are also to implement the following SML functions:

• singleton(label)

  val singleton = fn : 'a -> 'a rooted_tree

  This function returns a rooted tree with a single node, which must bear the label label.

• join_trees(T1,T2)

  val join_trees = fn : 'a rooted_tree * 'a rooted_tree -> 'a rooted_tree

  This function returns a rooted tree that is a "join" of two rooted trees. This figure illustrates the function.

  The second tree is inserted as a subtree of the first tree. In particular, the root of the second tree is always the rightmost child of the root of the returned tree. The root of the returned tree is always the root of the first tree.

• root(T)

  val root = fn : 'a rooted_tree -> 'a

  This function returns the root of the tree T.

• subtrees(T)

  val subtrees = fn : 'a rooted_tree -> 'a rooted_tree list

  This function returns the list of subtrees of T that are rooted at the children of the root of T.

• member_of(T,e)

  val member_of = fn : 'a rooted_tree * 'a -> bool

  This function returns true if there is a node in tree T that is labeled e; otherwise, it returns false.

• depthof(T,e)

  val depthof = fn : 'a rooted_tree * 'a -> int

  This function returns the depth of the label e in tree T, if there is a node with the labele in the tree; otherwise, return -1. Note that the root is at depth 0.

• sizeof(T)

  val sizeof = fn : 'a rooted_tree -> int

  This function returns the number of nodes in the tree T.

• same_as(T1,T2)

  val same_as = fn : 'a rooted_tree * 'a rooted_tree -> bool

  This function returns true if T1 and T2 are identical, both in structure and in labels; it returns false otherwise.

Implementation Language

For this assignment, your program must be written in SML.

Your solution will consist of a file of SML datatype and function definitions.

If your program is in the file bob.sml, then you can load it at the SML prompt as follows:

- use "bob.sml";

SML comments are enclosed by (* and *).

Input and Output Formats

As your SML program will be tested with the SML interpreter, you do not specifically have to be concerned with an input or output format; the interpreter takes care of that.

Testing Your Program

Before submitting your SML program file, you must test it thoroughly. To do this, you should devise a set of tests of your own that you believe exhaustively test your SML program.

Here is a small set of tests that you may start with, and here are the results for the function calls, starting with member_of(tree5,5). Please be certain that your SML program passes at least the above tests before submitting it.

Submitting Your Program

Your SML program must be in a single file named <pid>.sml, where <pid> must be replaced by your Virginia Tech PID. That file and any auxiliary files, such as test results, must be packaged as a zip file (or tar file) named <pid>_project4.zip, which is attached to email sent to the class account, cs3304@courses.cs.vt.edu. The subject of the mail must be "Program assignment 4" - without quotes.

For example, the GTA's submission will be a SML file: derao.sml along with the input file containing the test cases and their output, packaged in a zip file: derao_project4.zip. Further, derao_project4.zip will be mailed to cs3304@courses.cs.vt.edu with subject Program assignment 4.

Your SML implementation is to be organized in a single file. The comments at the beginning of the file should identify the assignment and should give your name. Every SML predicate should be preceded by comments explaining its purpose and implementation.

Be sure to follow the Program Submission Guidelines in preparing your report to turn in. In accordance with these guidelines, you will need to develop a set of test cases for your program that tests both positive and negative cases. For test cases that you are unable to run, be sure to indicate "Unable to perform test" in the corresponding test result within your report.

NOTE: Failure to follow the submission guidelines may result in a grade penalty.

Home  |   Notes  |   Languages  |   Programs  |   Homework