Do you ever implement the abstraction function? Usually no, but string representations come really close! We're conveying the same idea!
Let's implement a string function for our Set type:
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
(** [string string_of_elts s] is a representation of [s] as a
string where [string_of_elts e] converts [e] to a string*)
val string : ('a -> string) -> 'a t -> string
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
val string : ('a -> string) -> 'a t -> string
end
Now let's implement it for ListSetDups:
module ListSetDups : Set = struct
(** AF: The list [[a1; ...; an]] represents the set {b1, ..., bm}
where [[b1; ...; bm]] is the same list as [[a1; ...; am]]
but with any duplicates removed.
RI: None: the list may contain duplicates *)
type 'a t = 'a list
(** [dedup lst] removes duplicates from the list [lst]. It also
sorts the list. *)
let dedup lst = lst |> List.sort_uniq Stdlib.compare
let interior string_of_elt h t =
t
|> List.map string_of_elt
|> List.fold_left (fun acc elt -> acc ^ ", " ^ elt) (string_of_elt h)
let string_of_list string_of_elt = function
| [] -> "{}"
| h :: t -> "{" ^ interior string_of_elt h t ^ "}"
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
let string string_of_elt lst = lst |> dedup |> (string_of_list string_of_elt)
end
module ListSetDups : Set
Now let's test our function
ListSetDups.(empty |> add 42 |> add 43 |> add 3110 |> add 3110 |> add 2800 |> string string_of_int)
- : string = "{42, 43, 2800, 3110}"