As we were implementing Set, there were two questions we needed to answer:
Q: How do we interpret the representation type as the data abstraction?
A: Abstraction Function
Q: How do we determine which values of representation type are meaningful?
A: Representation Invariant
We had a comment before at the beginning of ListSetDups:
(** The list [[a1; ...; an]] represents the set {a1, ..., an}
[[]] represents the empty set.
The list may contain duplicates *)
That's not a great comment. What if we had the list [1;2;2;3]? What set would that represent? {1,2,2,3} isn't a set, it's a bag). Let's improve it!
(** 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 *)
(AF stands for abstraction function and RI stands for representation invariant)
The abstraction function tells us how to understand the data structure from the client's perspective.
TIP: Write the abstraction function first!