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.

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

a / \ b c / \ d e / \ g hthen the result of

6 / \ 2 7 / \ 1 4 / \ 3 5A single recursion over the tree structure can compute this output tree.

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

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.

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

Nod(Lf 8, tree1) Nod(Lf 5, tree2)are different no matter what trees are

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.

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.