Let's bring in our implementation of Set from earlier. Let's add a union operator too that combines two sets.
module type Set = sig
(** ['a t] is the type of a set whose elements have type 'a *)
type 'a t
(** [empty] is the empty set *)
val empty : 'a t
(** [size s] is the number of elements in [s]
[size empty] is [0]. *)
val size : 'a t -> int
(** [add x s] is a set containing all the elements of [s], as
well as element [x].*)
val add : 'a -> 'a t -> 'a t
(** [mam x s] returns true iff [x] is a member of [s]. *)
val mem : 'a -> 'a t -> bool
(** [union s1 s2] is the set containing both the elemnts of
[s1] and the elements of [s2]. *)
val union : 'a t -> 'a t -> 'a t
end
module type Set =
sig
type 'a t
val empty : 'a t
val size : 'a t -> int
val add : 'a -> 'a t -> 'a t
val mem : 'a -> 'a t -> bool
val union : 'a t -> 'a t -> 'a t
end
What if we allowed the list to contain duplicates?
module ListSet : Set = struct
(** The list [[a1; ...; an]] represents the set {a1, ..., an}
[[]] represents the empty set.
The list may contain duplicates *)
type 'a t = 'a list
let empty = []
(** sort_uniq uses O(n log n) time. *)
let rec size s =
s |> List.sort_uniq Stdlib.compare |> List.length
let add = List.cons
let mem = List.mem
let union = ( @ )
end
module ListSet : Set
Now let's implement union for our ListSet module (without duplicates).
module ListSetDups : Set = struct
(** The list [[a1; ...; an]] represents the set {a1, ..., an}
[[]] represents the empty set.
The list may not contain duplicates *)
type 'a t = 'a list
let empty = []
let size = List.length
let add x s = if List.mem x s then s else x :: s
let mem = List.mem
let union s1 s2 = s1 @ s2 |> List.sort_uniq Stdlib.compare
end
module ListSetDups : Set