CSE 428: Home Assignments 6

Spring 2002, CSE 428: Assignment 6

Distributed: 12 April 2002
Due: 23 April in class.
Total maximum score: 100 points.

The purpose of this assignment is to provide experience with basic programming in Standard ML. Each of these problems is illustrated by examples in the file A6_example.html: if you load that file after loading your solution to these questions, you should get the answers in A6_answers.html.

Exercise 1 [Points 25]

Consider the following definition for a polymorphic binary tree.

datatype 'a btree = Leaf of 'a | Node of 'a btree * 'a * 'a btree;

Such trees have both their internal nodes and their leafs labeled. Write a function

inorderlevel : 'a btree -> int btree

that when given a tree, outputs a tree containing integers and being of the same shape. The nodes and leafs will be numbered in the order in which they appear in the inorder transversal of the tree. For example, given a tree t of the following shape

then the result of (inorderlevel t) should be the tree

A single recursion over the tree structure can compute this output tree.

Exercise 2 [Points 20]

Write the code for two higher-order functions, called filter and map2. Their type should be as follows.


filter : ('a -> bool) -> 'a list -> 'a list
map2   : ('a -> 'b -> 'c) -> 'a list -> 'b list -> 'c list

The function filter takes a predicate (first argument) and a list (second argument) and returns the sublist of that list which contains all the elements of the original list for which the predicate is true. The function map2 takes a function of two arguments as its first argument and two lists and returns one list containing the result of applying the function to corresponding elements in the given two input lists. If one input list is shorter than the other input list, the output list has the length of the shorter input list.

Exercise 3 [Points 25]

Consider the following implementation of calendar dates in SML.

    
datatype month = Jan | Feb | Mar | Apr | May | Jun | Jul 
                     | Aug | Sep | Oct | Nov | Dec;

datatype date = dt of int * month * int;

For this assignment, assume that a leapyear is exactly those years which are divisible by 4. (This is not exactly true but it is what we are looking for in this assignment.) Define the two functions using dates.

Define the function valid_date : date -> bool such that returns true if and only if the year part of the date is between 1900 and 2100 inclusively and the day part is in the correct range of the month (make sure to account for leap years).
Define the function days_since_1900 = fn : date -> int that returns the number of days from a valid date since 1 January 1900. You can assume that only valid dates are given to this function: no need to check this assumption.

Exercise 4 [Points 30]

Consider the following datatype and two functions.

datatype tree = Lf of int | Nod of tree * tree;

fun frontier (Lf n) = [n]
  | frontier (Nod(left, right)) = (frontier left) @ (frontier right);

fun equal_frontier (tree1, tree2) = (frontier tree1 = frontier tree2);

The function equal_frontier returns true if and only if the frontiers of its two arguments are equal. This function is unnecessarily inefficient since it computes the entire frontiers for the two tree, even if it might be easy to tell that the frontiers of two trees are different just from checking small parts of the trees. For example, the two trees

     Nod(Lf 8, tree1)   Nod(Lf 5, tree2)

are different no matter what trees are tree1 and tree2: their frontier does not need to be computed.

Write an improved version of this latter function, call it eq_frontier, that computes the same values, but does so more efficiently (that is, without computing the entire frontier for all its arguments). One observation might be useful in writing this function: for any trees t1, t2, and t3, the frontiers of the trees

  Nod(Nod(t1, t2), t3)     and     Nod(t1, Nod(t2, t3))

are the same.

Format of the solution

Your solution to these exercises should be assembled into one file, called solution.sml: this includes all function definitions and associated datatype declarations. It should be possible for the graders to read your file and, by the use of comments, tell what is your solution to the individual problems. The graders should be able to load your solution file directly into SML without getting errors. After load your code, they should then be able to run your solution on their own test data.

Please give a hard copy of the source program to the instructor by the due date. Furthermore, you should also email your sources to cg428@cse.psu.edu by the due date, so to allow us to check that they run correctly. Please send the file solution.sml as attachment, not by "cut-and-paste". Please write in the subject of the email your section, your name, and your student id.