- Sets are data structures in which the order and multiplicity of
elements is not important. Multisets are data structures where order
is not important but multiplicity is. Finally, list (which are built
into many programming languages) are data structures in which order
and multiplicity are important. We know a couple ways to test if two
lists are equal. For this problem, write two predicates to test that
two list are
*equal as multisets*and to test that two list are*equal as sets*. Below is a fragment of a module that you should use to start this problem.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). - Consider the following definition of unlabeled binary trees.
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 predicatetype 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.

Lectures / Modules / Homeworks / Syllabus