CSE 360 Homework 3

1. 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).
   

2. 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 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.