ocaml

Set Implementation using Lists

For this part of the project, you will implement sets. In practice, sets are implemented using data structures like balanced binary trees or hash tables. However, your implementation must represent sets using lists. While lists dont lend themselves to the most efficient possible implementation, they are much easier to work with.

For this project, we assume that sets are unordered, homogeneous collections of objects without duplicates. The homogeneity condition ensures that sets can be represented by OCaml lists, which are homogeneous. The only further assumptions we make about your implementation are that the empty list represents the empty set, and that it obeys the standard laws of set theory. For example, if we insert an element x into a set a, then ask whether x is an element of a, your implementation should answer affirmatively.

Finally, note the difference between a collection and its implementation. Although sets are unordered and contain no duplicates, your implementation using lists will obviously store elements in a certain order and may even contain duplicates. However, there should be no observable difference between an implementation that maintains uniqueness of elements and one that does not; or an implementation that maintains elements in sorted order and one that does not.

If you do not feel so comfortable with sets see the Set Wikipedia Page) and/or this Set Operations Calculator.

We provide some example code.

elem : 'a -> 'a list -> bool

elem x a returns true iff x is an element of the set a. For example, elem 5 [2;3;5;7;9] = true.

In [ ]:

let rec elem x a =

match a with

| [] -> false

| h::t -> if h = x then true else elem x t

subset: 'a list -> 'a list -> bool

subset a b returns true iff a is a subset of b. For example, subset [5] [2;3;5;7;9] = true.

In [ ]:

let rec subset a b =

match a with

| [] -> true

| h::t -> if elem h b then subset t b else false

eq: 'a list -> 'a list -> bool

eq a b returns true iff a and b are equal as sets. For example, eq [5;3;2;9;7] [2;3;5;7;9] = true.

In [ ]:

let rec eq a b =

(subset a b) && (subset b a)

You need to implement the following three functions:

remove: 'a -> 'a list -> 'a list

remove x a removes x from the set a. For example, eq (remove 5 [2;3;5;7;9]) [2;3;9;7] = true.

In [ ]:

let rec remove x a =

(* YOUR CODE HERE *)

In [ ]:

assert (eq (remove 5 []) []);

assert (eq (remove 5 [2;3;5;7;9]) [2;3;9;7]);

assert (eq (remove 4 [2;3;5;7;9]) [2;3;5;9;7]);

union: 'a list -> 'a list -> 'a list

union a b returns the union of the sets a and b. For example, eq (union [5;2] [3;7;9]) [2;3;5;7;9] = true.

In [ ]:

let rec union a b =

(* YOUR CODE HERE *)

In [ ]:

assert (eq (union [2;3;5] []) [2;3;5]);

assert (eq (union [5;2] [3;7;9]) [2;3;5;9;7]);

assert (eq (union [2;3;9] [2;7;9]) [2;3;9;7]);

diff: 'a list -> 'a list -> 'a list

diff a b returns the difference of sets a and b in a. For example, eq (diff [1;3;2] [2;3]) [1] = true.

In [ ]:

let rec diff a b =

(* YOUR CODE HERE *)

In [ ]:

assert (eq (diff [1;3;2] [2;3]) [1]);

assert (eq (diff ['a';'b';'c';'d'] ['a';'e';'i';'o';'u']) ['b';'c';'d']);

assert (eq (diff ["hello";"ocaml"] ["hi";"python"]) ["hello";"ocaml"]);