Filename: set.sml (10 points each)
A set is a collection of distinct elements with some implicit
ordering. Using the following datatype declaration: datatype ''a set = set of ''a list * (''a * ''a ->
bool);
a set can be created, as follows: set([1,2,3], op <);
Write the following functions that work with sets:
insert(e, s) : fn ''a * ''a set -> ''a set
member(e, s) : fn ''a * ''a set -> bool
intersection(s1, s2) : fn ''a set * ''a set -> ''a set
union(s1, s2) : fn ''a set * ''a set -> ''a set
difference(s1, s2) : fn ''a set * ''a set -> ''a set
Solutions for insert, intersection, union, and difference, must
preserve the ordering and must be O(n). Since the lists are kept
sorted a O(n) solution is possible.
Filename: dup.cl(10 points each)
Text, exercise 10.4, in Common Lisp. Use these fuction names:
a: remove-dups
b: non-dups
c: remove-all-dups
d: dup-count
Filename: leaves.cl (20 points, 10 + 10)
Exercise 10.10 in Sethi, pg. 420 implemented in Common Lisp
Name the first function, same-leaves and the second
same-leaves-lazy