Earlier in the course, we saw how to implement set operations using unordered lists and ordered lists. In this lab, you will implement the same operations using hashes and compare the running times. Hashes are a natural way to implement sets, since the keys of a hash must all be different, so they can represent the elements of a set. The value part of the hash is unimportant here, so just set it to 1. (If we were implementing multisets, we could use the value to indicate how many copies an element were in the multiset.)
printset( %myset ) should just print all the keys of the hash
%myset in some readable format.
member( $item, %myset ) should return true (1) if $item
is in %myset and false (0) if not.
add_element( $item, %myset ) should return a copy of %myset
with $item added to the set.
remove_element( $item, %myset ) should return a copy of %myset
with $item removed from the set.
union( %set1, %set2 ) should return a hash that represents the
union of %set1 and %set2.
Experiment with the running times of your subroutines to see how they compare
to the earlier versions. Another experiment you could do is to rewrite union
so that the arguments are references to the hashes rather than passing the hashes
themselves.