module hw3p1. import lists. type eq_sets list A -> list A -> o. type eq_msets list A -> list A -> o. type example int -> list int -> o. Place code for these predicates here. This module fragment is only a guide. example 0 nil. example 1 (1::nil). example 2 (1::3::nil). example 3 (1::3::1::nil). example 4 (1::3::1::3::nil). example 5 (3::3::1::1::nil). example 6 (2::4::nil) example 7 (2::2::4::4::2::4::nil).
kind utree type. type ut utree -> utree -> utree. type root int -> utree. type example int -> utree -> o. example 1 (root 5). example 2 (ut (root 1) (root 2)). example 3 (ut (ut (ut (root 7) (ut (root 8) (root 2))) (ut (root 3) (root 3))) (ut (root 5) (root 7))). example 4 (ut (ut (root 7) (ut (root 8) (root 2))) (ut (root 3) (ut (root 3) (ut (root 5) (root 7))))). example 5 (ut (ut (root 7) (ut (root 8) (root 2))) (ut (root 3) (ut (root 5) (ut (root 5) (root 7))))).With such a data structure, integers are only used to label the roots of the tree. Write a program to specify the predicate
type eq_frontier utree -> utree -> o.that checks if the frontiers of two trees are equal as lists. One way to do this is to compute the two frontiers and then compare them for equality. This is inefficient since the two frontiers might differ in some early stage and a failure can be returned without having to compute the entire frontiers. Use the associative property or the binary tree constructor to reorganize the trees incrementally when necessary. That is, the two trees
(ut (ut T1 T2) T3) (ut T1 (ut T2 T3))have the same frontier, so it is possible to reorganize such trees without changing their frontier. For full credit on this problem: Do not compute the entire frontier if this is not necessary.