Now, let's take our Set abstraction with lists.
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
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
end
module ListSet : 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
end
module ListSet : Set
Now we have a (not particularly efficent) implementation of Set with lists!