(* CS 251 Set ADT exercises.
Complete two implementations of a set ADT with the SET signature:
a list-based representation and a function-based representation.
You may ignore "Warning: calling polyEqual" in this exercise. *)
(* Placeholder during development. *)
exception Unimplemented
(* SET describes operations over set values of type ''a t, where set
elements are of type ''a. Recall that the double-quote type
variable ''a means that values of the type ''a can be compared
using the = operation.
Naming the type of the ADT t is a common idiom for signatures
defining an ADT. This means that for particular implementations
(e.g., ListSet or FunSet), ADT values have type ListSet.t or
FunSet.t, rather than the more verbose ListSet.set or FunSet.set.
If a signature defines multiple types (especially if there's not
one main type and other supporting types), this idiom is less
commonly used. *)
signature SET =
sig
(* The type of sets *)
type ''a t
(* An empty set *)
val empty : ''a t
(* Construct a single-element set from that element. *)
val singleton : ''a -> ''a t
(* Construct a set from a list of elements.
Do not assume the list elements are unique. *)
val fromList : ''a list -> ''a t
(* Convert a set to a list. *)
val toList : ''a t -> ''a list
(* Construct a set from a predicate function:
the resulting set should contain all elements for which
this predicate function returns true.
This acts like math notation for sets. For example:
{ x | x mod 3 = 0 }
would be written:
fromPred (fn x => x mod 3 = 0)
*)
val fromPred : (''a -> bool) -> ''a t
(* Convert a set to a predicate function. *)
val toPred : ''a t -> ''a -> bool
(* Convert a set to a string representation, given a function
that converts a set element into a string representation. *)
val toString : (''a -> string) -> ''a t -> string
(* Check if a set is empty. *)
val isEmpty : ''a t -> bool
(* Check if a given element is a member of the given set. *)
val member : ''a -> ''a t -> bool
(* Construct a set containing the given element and all elements
of the given set. *)
val insert : ''a -> ''a t -> ''a t
(* Construct a set containing all elements of the given set
except for the given element. *)
val delete : ''a -> ''a t -> ''a t
(* Construct the union of two sets. *)
val union : ''a t -> ''a t -> ''a t
(* Construct the intersection of two sets. *)
val intersection : ''a t -> ''a t -> ''a t
(* Construct the symmetric difference of two sets. *)
val difference : ''a t -> ''a t -> ''a t
end
(* Implement a SET ADT using lists to represent sets. *)
structure ListSet :> SET = struct
(* Sets are represented by lists. *)
type ''a t = ''a list
(* The empty set is the empty list. *)
val empty = []
(* complete this structure by replacing "raise Unimplemented"
with implementations of each function *)
fun singleton _ = raise Unimplemented
fun fromList _ = raise Unimplemented
fun toList _ = raise Unimplemented
fun fromPred _ = raise Unimplemented (* impossible to implement *)
fun toPred _ = raise Unimplemented
fun toString _ = raise Unimplemented
fun isEmpty _ = raise Unimplemented
fun member _ = raise Unimplemented
fun insert _ = raise Unimplemented
fun delete _ = raise Unimplemented
fun union _ = raise Unimplemented
fun intersection _ = raise Unimplemented
fun difference _ = raise Unimplemented
end
(* Tests Cases -- add more of your own *)
(*
val test = ListSet.union
(ListSet.fromList [1,2,3])
(ListSet.fromList [3,4,5])
val str = ListSet.toString Int.toString test
val mem0 = ListSet.member 0 test
val mem1 = ListSet.member 1 test
val mem2 = ListSet.member 2 test
val mem3 = ListSet.member 3 test
val mem4 = ListSet.member 4 test
val mem5 = ListSet.member 5 test
val mem6 = ListSet.member 6 test
val ints = ListSet.toString Int.toString
(ListSet.intersection
(ListSet.fromList [1,2,3])
(ListSet.fromList [3,4,5]))
val diff = ListSet.toString Int.toString
(ListSet.difference
(ListSet.fromList [1,2,3])
(ListSet.fromList [3,4,5]))
*)
(* Implement a SET ADT representing sets by predicate functions. *)
structure FunSet :> SET = struct
(* Sets are represented by functions that return true if the
given element is in the set and false if it is not. *)
type ''a t = ''a -> bool
(* The empty set is a function that returns false on
all arguments. *)
fun empty _ = false
(* The singleton set is a function that checks to see if
its argument is the one element of the set. *)
fun singleton x = fn y => y=x
(* complete this structure by implementing the rest of the
functions. Leave raise Unimplemented in the body of any
function that cannot be implemented for this representation *)
fun fromList _ = raise Unimplemented
fun toList _ = raise Unimplemented
fun fromPred _ = raise Unimplemented
fun toPred _ = raise Unimplemented
fun toString _ = raise Unimplemented
fun isEmpty _ = raise Unimplemented
fun member _ = raise Unimplemented
fun insert _ = raise Unimplemented
fun delete _ = raise Unimplemented
fun union _ = raise Unimplemented
fun intersection _ = raise Unimplemented
fun difference _ = raise Unimplemented
end
(* Test Cases -- add more of your own *)
(*
val test = FunSet.union
(FunSet.fromList [1,2,3])
(FunSet.fromList [3,4,5])
val mem0 = FunSet.member 0 test
val mem1 = FunSet.member 1 test
val mem2 = FunSet.member 2 test
val mem3 = FunSet.member 3 test
val mem4 = FunSet.member 4 test
val mem5 = FunSet.member 5 test
val mem6 = FunSet.member 6 test
val ints = FunSet.intersection
(FunSet.fromList [1,2,3])
(FunSet.fromList [3,4,5])
val mem0 = FunSet.member 0 ints
val mem1 = FunSet.member 1 ints
val mem2 = FunSet.member 2 ints
val mem3 = FunSet.member 3 ints
val mem4 = FunSet.member 4 ints
val mem5 = FunSet.member 5 ints
val mem6 = FunSet.member 6 ints
val diff = FunSet.difference
(FunSet.fromList [1,2,3])
(FunSet.fromList [3,4,5])
val mem0 = FunSet.member 0 diff
val mem1 = FunSet.member 1 diff
val mem2 = FunSet.member 2 diff
val mem3 = FunSet.member 3 diff
val mem4 = FunSet.member 4 diff
val mem5 = FunSet.member 5 diff
val mem6 = FunSet.member 6 diff
*)