A data abstraction is a specification of operations on a set of values, for example, stacks have push, pop, peek, etc...
A data structure is an implementation of a data abstraction with a particular representation. For example, ListStack implemented StackSig with 'a list, (::), etc...
Let's build a data abstraction and structure for 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
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
Now we have the sig Set. It is a set of values.
'a t for values of that type (Set.t is the type constructor for sets, parameterized on the type variable 'a).empty is the empty setsize, add, and mem are functions that manipulate sets.