|
The Lab 8 template contains 4 definitions for each of the following
procedures: empty?
, element-of-set?
,
count
, adjoin
, union
,
intersection
, difference
, and
symmetric-difference
. One for each of the following three
representations of sets - unordered lists with duplicates, ordered
lists without duplicates, and binary search trees, and one definition
you must complete that will work with any of the data types.
For each of data sets all of the operations are already implemented
except for the ones you had to write for the last lab. Copy and paste
these in from the last lab before you do anything else. These are
adjoin
and union
for ordered list
representation, and union
and intersection
for binary search trees. You may also need to copy your definition of
tree->set
.
Your goal for the lab is to get all of the test cases provided in the template to work while maintaining distinct data types in the system (i.e. you may not just convert all data to one type and your code must maintain distinct representations). The book presents three possible solutions: tagging, message passing, and data directed programming. You may pick one of these and modify the existing code accordingly. If you come up with a different approach feel free to use it as long as it maintains the three distinct set representations underneath.
You may assume the procedures that take in two sets such as union will only be passed two sets in a given call if they are in the same representation. For instance, union will never be sent a binary search tree for the first argument and an ordered list as the second, but union should work for two binary search trees or two ordered lists.
Be sure that your system maintains consistency in representations. For instance, if union takes in two binary search trees be sure to return a binary search tree representing the union of these two trees. If you are representing your data with tags, be sure that the generic union operation returns data that is properly tagged. Likewise if you are implementing your data as message passing procedures, be sure the generic union procedure returns a message passing representation. In either case the sample files below provide examples of how you can do this. Be sure adjoin, intersection, difference, and symmetric-difference are consistent also.
Examples for unordered lists have been worked out by the TAs for each of the three methods, you may feel free to use these for inspiration:
If you implement a message passing scheme test your code with the second set of test cases and implement a message 'data that returns the actual list data of your representation. This way the test cases will show your the actual set generated by operations such as union and intersection, and not just a representation for the procedure returned. You may also find this useful for implementing union, intersection, etc. See the example in the message passing file above.
Hintsunordered-list?
,ordered-list?
, and
binary-search-tree?
. The sample file above may provide
some inspiration.